Bonjour à toutes et à tous,

J'ai trouvé un pdf dans lequel on arrive à calculer le nombre total de graphes connexes d'ordre N.

"http://www.pierreaudibert.fr/tra/GRAPHESNS.pdf" 

Néanmoins j'aimerais savoir comment on pourrait calculer le nombre de graphes connexes d'un graphe d'ordre N en utilisant seulement N-1 arêtes ?

J'ai essayé une petit démo par récurrence sur l'ordre du graphe sauf qu'enlever un somment pour se ramener à l'hypothèse de récurrence ne fonctionne pas étant donné que l'on finit par compter plusieurs fois un même graphe  !

A moins que vous sachiez combien de fois exactement on compte une configuration connexe possible plusieurs fois ?

Merci de m'avoir lu !

Salut,

Ce n'est peut-être pas exactement ce que tu cherches ( je ne suis pas sûr d'avoir bien compris   ) mais on peut établir une récurrence permettant de calculer le nombre total de graphes connexes d'ordre n:

\(n2^{\frac{n(n-1)}{n}}= \sum_{k=1}^n C_n^k k d_k 2^{\frac{(n-k)(n-k-1}{2}}\), 

où \(d_k\) est le nombre de graphes connexes d'ordre \(k\).

L'application pour les petits \(n\) donne \(d_1=1,d_2=1, d_3=4, d_4 =38\). Tu peux vérifier sur ton lien qu'il y a bien 38 graphes connexes pour 4 sommets.  

Le nombre augmente très rapidement au-delà mais il est facile de programmer cette récurrence.

L'établissement de la récurrence découle   d'une application des fonctions génératrices et séries formelles trouvée dans ce lien:

  https://www.math.upenn.edu/~wilf/gfology2.pdf  ... ce n'est pas trivial!  

( j'ai trouvé ce lien   sur le site les-mathématiques.net  où une question voisine a été posée)

-
Edité par Sennacherib 17 mai 2018 à 10:35:52

Bonjour, 

suppose que tu as un graphe d'ordre k qui satisfait la propriété requise cad connexe et k-1 arêtes. Si tu ajoutes un sommet, comment obtenir un graphe d'ordre k+1, connexe avec k arêtes. Clairement la connexité exige que tu rattaches le nouveau sommet à un ancien via une arête. Vu qu'il y a k anciens sommets, il y k façon de faire cela pour chaque graphe d'ordre k connexe avec k-1 arêtes. Mais attention, si on veut un comptage à isomorphisme près, il faut éliminer certains. Par exemple si on a 3 sommets alignés reliés par deux arêtes et qu'on ajoute un sommet et une arête à l'extrémité gauche ou droite, on obtient des graphes isomorphes...Fais les dessins (un peu comme dans le lien que tu cites)...

Plus Tony que Sosa a écrit:

Merci pour ta réponse mais effectivement, je cherche uniquement le nombre de graphes connexes d'ordre N ayant exactement N-1 arêtes, ni plus, ni moins !

OK là il y a une formule très simple c'est \(n^{n-2}\). Pour \(n=4\), c'est donc 16 ce que on peut vérifier directement sur ton lien .Il y a plusieurs démonstrations possibles mais un peu plus compliquées qu'une récurrence immédiate.
   C'est connu sous le nom de formule de Cayley  que on trouve dans Wiki  avec des indications vers plusieurs preuves 

https://fr.wikipedia.org/wiki/Formule_de_Cayley

plus généralement un graphe connexe aura un nombre d'arêtes k tel que \(n-1 \leq k \leq \frac{n(n-1)}{2}\)

 Je ne sais pas si on peut exprimer  explicitement   le dénombrement avec exactement \(k\) pour tout \(k\), en tout cas,  je n'ai rien trouvé sur le net. 

-
Edité par Sennacherib 18 mai 2018 à 14:29:17

Suite au lien de Sennacherib, j'étais un peu déçu de voir que ça ne marchait que pour les graphes où les noeuds avaient des étiquettes (ou des couleurs) ; je me demandais ce qu'il en était quand les noeuds n'avaient pas d'étiquette.

Sauf erreur de ma part, les graphes connexes à n-1 arêtes sont les cycles et les arbres. J'ai donc fini par trouver ma réponse dans l'OEIS (forcément). La formule Mathematica donnée est moche, mais en regardant de plus près elle s'obtient facilement depuis la suite A000055, pour laquelle l'OEIS a une série génératrice. Edit : oui mais en fait la série génératrice est super moche aussi.

-
Edité par melepe 21 mai 2018 à 13:21:51