Graphe

[bidoune]

Bonjour a tous,
cela fait quelque jour que je cherche:
combien y a t il de graphes de sommet {1,2,3,4,5} à 2 composantes connexes?

Si quelque sait comment faire, ca serait gentil de m'expliquer...

[bruce.ml]

Salut,

il y en a une infinité.
En revanche, si tu veux parler de graphes dans lesquels au plus une arrête relie 2 sommets, il n'y en a qu'un nombre fini, est-ce bien cela ?

[bidoune]

Oui je voulais parler de cela...

[ThSQ]

Intéressant ! Une tentative. J'ai vérifié à la main sur les petits nombres ça a l'air bon.

Je compte les graphes non orientés et simples.

U(n) = nombre de graphes avec une seule composante connexe.
D(n) = nombre de graphes avec deux composantes connexes.

U(1) = U(2) = 1 et U(n+1) = U(n) * 2^n-1 (on a le choix de brancher 1 à n nouveaux fils dans un graphe existant).

: on crée deux paquets de 1 à n-1 éléments et on crée des graphes à une composante pour chaque paquet. Diviser par 2 car on compte tout 2 fois ((1,n-1) pareil que (n-1,1) par ex.)

Ca donne pour U : 1, 1, 3, 21, 315, 9765
Et pour V : 0, 1, 3, 15, 135, 2295

Le nombre de graphes à 5 sommets et avec deux composantes connexes est : 135

[ThSQ]

Un petit up au cas où bidoune serait assez gentil pour nous donner la solution officielle !