Niveau LicenceMaths 2e/3e a

Theorie des graphes

Posté par
Endetresse 21-10-23 à 14:20

Bonjour,

On veut montrer que si $G$ un graphe (non orienté) de n sommets et m arêtes et $m > \frac{(n-1)(n-2)}{2}$ $G$ est connexe.

Merci

Posté par re : Theorie des graphes 21-10-23 à 14:27

As-tu essayé de montrer la contraposée ?
Si G n'est pas connexe, ton graphe a plusieurs composantes connexes. Quel est le cardinal maximal d'une composante connexe de G ?

Posté par re : Theorie des graphes 21-10-23 à 14:37

Ah oui!!!
Le cardinal maximal!
Le nombre des sommets sont n-1 d'une composante maximal, donc
Le cardinal est 1/2 la somme des degrés maximaux qui valent n-2, et leur somme vaut (n-1)(n-2), et on divise par deux.

Merci

Posté par re : Theorie des graphes 21-10-23 à 14:41

De rien
Sinon, sans parler de degré, choisir une arête, c'est choisir deux points parmi une composante connexe, et les connecter.
Donc le nombre d'arêtes est majoré par le nombre de choix possibles de deux points dans la plus grosse composante connexe : $\binom{M}{2} = \dfrac{M(M-1)}{2}$ , où M est le cardinal de la plus grande composante connexe.
C'est une fonction croissante de M, et on a dit que $M \leqslant n-1$ , donc m est majoré par n(n-1)/2.
C'est plus long à écrire qu'à comprendre