théorie des graphes

[hamzawhy]

Bonjour,
j'ai un problème avec un exercice,en fait je ne sais pas d'où je peut commencer et quel théorème je peut utiliser:
voici l'exercice:

Soit G un graphe simple d'ordre n ayant k composantes connexes,Montrer que le nombre maximum d'arrêtes est (n-k)*(n-k+1)/2.
est ce qu'on utilise la règle qu'un graphe connexe d'ordre n possède au moins (n-1) arrêtes ou la règle de n*(n-1)/2
et merci pour tout aide.

[IP_Steph]

Ca part du principe que chaque composante connexe du graphe peut être vue comme graphe complet et qu'un graphe à n sommets possède au plus n*(n-1)/2 arêtes.

Il suffit alors de considérer deux composantes C(i) et C(j) qui ont respectivement n(i) et n(j) sommets. Et pour fixer les idées, on peut poser par exemple que n(i)>=n(j)>1.

Si on remplace C(i) par un graphe de n(i)+1 sommets et C(j) par un graphe de n(j)-1 sommets, le nombre de sommets et de composantes de G n'aura pas changé bien sûr. Par contre le nombre d'arêtes aura augmenté de :

Code :

delta = n(i)*(n(i)+1)/2 - n(i)*(n(i)-1)/2 + (n(j)-1)*(n(j)-2)/2 - n(j)*(n(j)-1)/2

c'est à dire

Code :

2*delta = n(i)² + n(i) - n(i)² + n(i) + n(j)² - 3*n(j) + 2 - n(j)² + n(j) = 2*n(i) - 2*n(j) + 2

ou encore

Code :

delta = n(i) - n(j) + 1

Maintenant, dans quelles conditions delta serait maximal ?

Ce sera le cas lorsque le graphe G n'aura plus qu'une seule composante connexe avec au plus un sommet, donc lorsqu'il y aura k-1 sommets isolés donnant ainsi un graphe à n-k+1 sommets (un peu compliqué a priori mais facile à visualiser)

On utilise encore la formule du nombre d'arêtes maximum d'un graphe. Lorsque celui-ci possède n-k+1 sommets, on retrouve bien le produit (n-k+1)*(n-k)/2.

Steph

[hamzawhy]

merci IP_Steph pour l'explication c'est gentil de ta part!!