Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

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
Ulmiere
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
Endetresse
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
Ulmiere
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

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

Par (n-1)(n-2)/2 pardon

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

Super, y a deux méthodes en plus!
merci beaucoup



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1673 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !