Théorie des graphes

[inviteb4cef08e]

Bonjour,

Actuellement en Terminale S, j'aimerais quelques pistes de recherche ou de solutions pour ce type de problème, il me semble très intéressant mais je sèche dès la première question!
Merci bien

arbre.PNG
abre 2.PNG
arbre 3.PNG
-----

[minushabens]

allez je t'aide pour la question 1.a. : un arbre ayant plus d'un sommet a nécessairement un sommet "terminal" c'est-à-dire qui appartient à une unique arête (en fait il en a au moins deux). Si tu coupes l'arbre sur l'arête adjacente à un sommet terminal, cette arête portera le nombre 1. Donc 1 appartient à tout ensemble de coupes, dès que n>1. Dans l'exercice n est supposé fixé mais on ne dit pas à quelle valeur. Il te faut discuter les cas n=0 et n=1, et si n>1 alors on a nécessairement k=1.

[inviteb4cef08e]

Tu ne peux simplement pas faire d'abre avec n=0 et n=1 ^^', (il te faut au moins deux points hein!)
Donc j'imagine que pour la question 1.b c'est vrai pour tout k entier.
vu que cet arbre avec C(1;k) est composé uniquement d’arêtes de coupe k o 1.
Il a donc forcément une arête de coupe k. Une coupe selon cette arête donne deux arbres T' et T", le plus petit comportant k sommets, qui sont obligatoirement liés deux à deux par des arêtes de coupe 1. La seule possibilité c'est que toutes les arêtes de coupe 1 aient un sommet en commun (sinon on aurait forcément une arrête avec une coupe >1). Il existe donc k-1 arêtes de coupes 1 qui les relient. Ce sommet commun est nécessairement d’extrémité initiale de l’arête de coupe k (propiété 3).


Ainsi, en faisant un arbre symétrique comportant une ligne principale de coupe ket aux deux extrémités de cette droite créer k-1 branches relliées uniquement aux extrémités de cet arbre c'est possible.

Idée pour la suite?

Merci!

[minushabens]

Tu ne peux simplement pas faire d'abre avec n=0 et n=1 ^^', (il te faut au moins deux points hein!)

la définition ne dit pas qu'il faut au moins deux points.

[A voir en vidéo sur Futura]

[inviteb4cef08e]

On a n>1 (énoncé)
Et ça me paraît difficile de faire un graphe avec 1 ou 0 points!
J'ai bien avancé le problème Mais n'arrive pas à trouver les variations de la suite!
Pourriez-vous y jeter un coup d'oeil?

[inviteb4cef08e]

On a n>1 (énoncé)
Et ça me paraît difficile de faire un graphe avec 1 ou 0 points!
J'ai bien avancé le problème Mais n'arrive pas à trouver les variations de la suite!
Pourriez-vous y jeter un coup d'oeil? (4)
Aussi, j'ai quelques idées pour des conditions nécessaires et suffisantes en auriez vous ? (3)

Aussi, pourrais-je vous contacter par mp? j'ai une requête assez spéciale à vous exposer!
Merci

[minushabens]

ton analyse du cas {1,k} n'est pas mal mais pas tout-à-fait juste: le graphe doit avoir deux sommets intérieurs séparés par une arête, mais ensuite l'un des sommets doit avoir k-1 autres voisins et l'autre doit en avoir au moins k-1, mais peut en avoir plus.

[inviteb4cef08e]

ah merci, effectivement sa marche! Merci beaucoup de ton aide!
Pour la question 2, le cardinal maximal.

Quand on cherche le cardinal maximal d’un sous ensemble cela est pareil que chercher une possibilité selon laquelle le nombre de sommet est minimale et la multiplicité des valeurs des coupes est maximale. Or si le ss ensemble A a pour valeur max K alors l'arbre avec C(T) = A a au moins une arrête de coupe k, et au minimupmm 1. Donc d'un côte relié à k-1 sommets et de l'autre au moins k-1 et au minium k-1. Donc la multiplicité des valeurs des coupes est max quand A = {1,2....k}

Sauf qu'avec la question précendente j'avais trouvé que dans cette configuration il y a 2k sommets. Donc card(A) = (n+1)/2 quand n impair et n/2 quand n pair? ou juste card(A) = k?