Théorie des graphes : cas d'école

[dedibox]

Bonjour,

Je cherche à savoir s'il existe une méthode pour répondre à une question du type :

Existe t-il des graphes avec les listes de degrés suivantes ?
a) (3,3,3,3)

De tête je vois bien qu'un graphe complet à 4 sommets mais pour des cas plus durs, par exemple : (4,4,4,2,2) y aurait-il une méthode ou un algo pour répondre oui/non facilement ?

Merci d'avance pour votre aide,

[buzard]

Bonjour,

tu peux essayer de construire la matrice d'adjacence (j'imagine que tu ne peux pas dupliquer les arêtes entre les sommets et que tu cherche des graphes non orientés), tu obtient alors un système linéaire qui admet une infinité de solution, le problème et de savoir si parmis elles au moins une est formé de 0 ou 1.

[dedibox]

Oui voilà ça c'est la méthode que j'applique mais je le fais plus ou moins au hasard de tête sans appliquer une méthode précise. Ça peut être assez long quand en plus on doit chercher le nombre de graphes réalisables (à isomorphisme près).

S'il existe un algo formel qui permet de passer d'une liste de degrés à une liste d'adjacence je suis preneur.

C'est bien de graphes non orientés dont il s'agit.

[buzard]

si tu doit faire du dénombrement en plus je pense qu'une méthode de construction directe est plus efficace, quoique les nouveaux algo de PLNE (programmation lineaire en nombre entier) sont plutot efficace.
par contre le denombrement à isomorphisme pres n'est pas evident du tout.

[dedibox]

Donc je dois m'entraîner ! Je te remercie pour tes conseils :++:

[Ben314]

Salut,
S'il y a sommets et que tu note la liste des degrés avec , des conditions nécéssaires (et je pense suffisantes) sont :
- Il faut que (évident)
- La somme doit être paire vu que le nombre total d'arrêtes vérifie
- Pour tout on doit avoir où est le nombre d'arrêtes (en fait, il suffit de vérifier cette inégalité pour le plus grand indice tel que )

Cette dernière condition vient du fait que, si on groupe les sommets en deux : et alors de chaque sommet , il part au plus arrêtes allant à un autre sommet de donc il part au moins arrêtes vers des sommets de .
Il y a donc au moins arrêtes de vers .
Or, des arrêtes arrivant dans , il y en a au maximum
On doit donc avoir , c'est à dire .

Par exemple, pour (4,4,4,2,2), le max des tels que est 3 et on a donc la configuration est impossible.

A mon avis, ces conditions sont suffisantes : je pense qu'il suffit de relier le sommet de plus grand degrés avec les sommets (autres que ) de plus grand degrés puis de recommencer avec le nouveau sommet de plus haut degrés restant...

[buzard]

c'est excellent cette condition, ça me rappel un peu le problème de coupe min pour un flot. En tous cas ça donne un tres bon oracle pour le choix des branches à couper quand tu fait de l'exploration pour le dénombrement.

bravo ben :++:

[dedibox]

Excellent mais j'ai un doute sur la 3eme condition.

Par exemple pour (4,4,2,2,2) je sais qu'il existe deux graphes donc les trois conditions devraient être vérifiées.

Mais pour la 3e condition j'ai 14 > 8 + (3x2)/2

[Ben314]

Pour (4,4,2,2,2), , le plus grand tel que est et on a donc tout est O.K.

Si tu prend (ce n'est pas utile du fait que, si c'est O.K. pour le plus grand tel que alors c'est O.K pour les autres ) tu obtient :

Par contre, aprés reflexion, ces conditions ne semblent pas suffisantes...