Composantes connexes d'un graphe

[nadia]

Bonjour,
Je bloque sur une question qui est la suivante :
soit G un graphe avec G=(V,E) avec cardV=n et cardE=m et m strictement supérieur à n-1 .
quel est le nombre maximal ainsi que le nombre minimal de composantes connexes de G.
Merci d'avance.

[Ben314]

Salut,
Si tu part d'un graphe avec sommets et sans arrêtes, il a donc composantes connexes.
Et à chaque fois que tu ajoute une nouvelle arrête, si elle relie deux composante connexes distinctes et ça diminue de 1 le nombre de composants connexes, et sinon, ben le nombre de composante connexe reste le même.
Avec ça, tu trouve trivialement quel est le minimum du nombre de composantes connexe lorsqu'il y a arrêtes.

Pour le max, ça me semble un peu plus compliqué. Le truc qui me vient à l'esprit c'est ça :
Montre que, si tu as deux composantes connexes distinctes non réduite à un sommet, alors, en gardant les mêmes sommets (des deux composantes) mais en plaçant les arrêtes différemment tu peut avoir une seule composante non réduite à un sommet et au moins une (voire plus) composante réduite à un sommet.
Déduit en que pour avoir le max. de composantes connexe, il suffit de regarder les cas où il y a une seule composante connexe non réduite à un sommet.

P.S. : Je suppose que tu parle de graphes non orientés, sans boucle et sans arête multiple (mais ça serait évidement pas con de le préciser...)

[pascal16]

pour le nombre minimal.
cas n=1 à traiter à part. m n'existe pas
n sommets m arêtes avec m>=n
soit la chaîne 1->2->3->.. n->1 : du moment qu'on a au moins n arrêtes, on peut tout grouper en 1 seul graphe connexe.
On peut rajouter des chaines... jusqu'à ce que le graphe soit complet
donc il y a une condition sur m, m <= n(n-1)/2

finalement, sous la condition m <= n(n-1)/2 (qui traite le cas n=1 au passage); le mini, c'est 1

pour le max, on peut passer par une étape de sous-graphe complet, le plus petit a tel que a(a-1)/2 <= n, puis un dénombrement de la façon dont on peut ajouter des arêtes mais c'est pas simple.

[nadia]

Merci , je vois très clair pour le minimum, mais je ne vois du tout pas comment faire pour le maximum.

[pascal16]

"un maximum" en supposant que :
-> étant donné que le graphe complet maximise le nombre d'arêtes utilisées
-> la max recherché est atteint en partant d'un sous graphe complet auquel on adjoint des arêtes ce qui laisse un maximum de sommets isolés, donc de sous graphes.


sous condition que m <= n(n-1)/2
Soit M1 tel qu'il soit le plus grand x tel que x(x-1)/2 <= m
M1 est le nombre de sommets du plus grand sous graphe complet qui a M1(M1-1)/2 arêtes

Si on part de ce sous-graphe + les points isolés.
tu as 1 sous graphe + m-M1 points isolés soit m-M1+1 sous-graphes
depuis le premier point isolé, tu peux rajouter M1 aretes vers le graphe complet pour (m-M1+1)-1 sous graphes au total
depuis le second point isolé, tu peux rajouter M1+1 aretes vers le graphe complet pour (m-M1+1)-2 sous graphes au total
depuis le troisième point isolé, tu peux rajouter M1+2 aretes vers le graphe complet pour (m-M1+1)-3 sous graphes au total
...
quand on a somme(M1+k) < m<= somme(M1+k+1), on a la réponse

C'est cette partie qui est facile à écrire, mais pas à dénombrer, il faut passer sans doute passer par la somme des termes d'une suite arithmétique

[nadia]

Rebonjour,
Est ce que la condition m supérieur strictement à n-1 va jouer un rôle pour trouver le maximum?, car je ne vois pas cela dans votre proposition . Merci d'avance.

[pascal16]

m>n-1 a été utile dans la cas du min

Pur le max, c'est pas une vraie démo, juste une forte intuition

en me relisant :
sous condition que m <= n(n-1)/2
Soit M1 tel qu'il soit le plus grand x tel que x(x-1)/2 <= m
M1 est le nombre de sommets du plus grand sous graphe complet qui a M1(M1-1)/2 arêtes

Si on part de ce sous-graphe + les points isolés.
tu as 1 sous graphe + m-M1 points isolés soit m-M1+1 sous-graphes
depuis le premier point isolé, tu peux rajouter M1 aretes vers le graphe complet pour (m-M1+1)-1 sous graphes au total
vu qu'on obtient un graphe complet, par définition de M1, on est sur d'avoir plus de m arêtes.
reste à mettre en forme

[Ben314]

Salut,
Ça :

-> étant donné que le graphe complet maximise le nombre d'arêtes utilisées

Pris texto, il me semble bien que... ça veut absolument rien dire, non ?

Donc à mon avis, c'est à remplacer avantageusement par... ce que j'ai mis dans mon premier post, à savoir que lorsque tu as deux composantes alors en plaçant différemment les arrêtes, tu peut avoir une seule composante connexe non réduite à un sommet et qu'en procédant de la sorte, ça ne peut que augmenter (au sens large) le nombre de composante.
Preuve : Soit et le nombre de sommets/arrêtes des deux composantes (avec )
On a donc (=nombre maximal d’arêtes dans un graphe à sommets).
Si on pose alors on a
Donc
Ce qui signifie qu'on peut placer les arrêtes dans une seule composante ayant sommets et qu'il restera donc au moins un point isolé -> on aura de nouveau au moins deux composantes connexes.
Et j'ai pas l'impression qu'on puisse s'en sortir avec juste du "on voit bien que" sans faire le calcul marqué en bleu (ou un autre équivalent)

Ensuite, effectivement c'est trivial vu que le résultat ci dessus dit que pour minimiser le nombre de composantes, ça ne coûte rien de considérer qu'on a une seule composante non réduite à un point.