Discussion :

[yaris20]

Bonjour.
Je bloque sur un exercice de graphes censé être simple dont voici l'énoncé :
pour tous entiers p, s, t on note P(p, s, t) la proposition vraie si dans tout groupe de p personnes, il existe au moins s personnes qui se connaissent deux à deux ou au moins t personnes qui ne se connaissent pas deux à deux.
1) Reformuler cette définition en utilisant des graphes
J'ai pensé utiliser des graphes simples, non orientés et sans boucles où chaque sommet représente une personne et chaque arête relie deux personnes qui se connaissent.
P(p,s,t) est vraie s'il existe un graphe défini comme précédemment à p sommets avec au moins s arêtes ou si il faudrait lui ajouter t arêtes pour le rendre complet.
Je bloque à partir des questions suivantes :
2) Démontrer que pour tous entiers p et s, P(p,s,2) (sans mauvais jeu de mots) est vraie si seulement p >= s.
3) Est-ce que P(5,3,3) est vrai ? Preuve attendue.
4) Est-ce que P(6,3,3) est vrai ? Preuve attendue.
Je ne suis pas certain de ma modélisation.
Merci.

[gui80]

Bonjour,

2) Démontrer que pour tous entiers p et s, P(p,s,2) (sans mauvais jeu de mots) est vraie si seulement p >= s.

Quelque chose me semble étrange. p>=s -> VRAIE dans tous les cas dans un graphe non orienté. Tu as bien recopié cette question ?
Sinon, faut-il écrire des choses de ce genre :
s : nb de sommets
a : nb d'arêtes
1sommet [0;s-1]
s * (s-1) : nb max de sommets d'un graphe orienté
(s * (s-1))/2 : nb max de sommets d'un graphe non orienté

donc nb_sommets est tjrs >= (s * (s-1))/2 arêtes

[benDelphic]

'ai pensé utiliser des graphes simples, non orientés et sans boucles où chaque sommet représente une personne et chaque arête relie deux personnes qui se connaissent.

la construction est juste ... mais il fallait prendre la peine de voir la première question et de la résoudre avant de voir les suivantes .
sur ce graphe , pour que t personnes ne se connaissseent pas il suffit de trouver un stable de cardinalité au moins t ...ou qu'il existe un sous graphe d'ordre s de degré minimum non nul.
ce qui répond à la deuxième question ... p>=s est une condition necessaire car on ne peut trouver 100 personnes parmi 10 ???? donc il te reste juste de demontrer que pour t = 2 et p >=s P est vraie ..