Construire un graphe en connaissant les degrés

[MMVV]

Bonjour,
Je ne sais pas si c'est le bon forum (sinon merci de m'indiquer où je devrais poser la question) mais voici mon problème.

On cherche à construire un graphe G d'après les informations suivantes :
1) non orienté
2) connexe
3) N nœuds
4) les degrés d(i) des nœuds (ou, présentation équivalente, les sommes en ligne de la matrice d'incidence)

On ne peut pas toujours construire G. Par exemple N=3, d(1)=d(2)=d(3)=1.

Questions :
1) Quels critères sur N et les degrés permettent de conclure à la possibilité d'une construction ?
2) Si c'est possible, sur quels critères savoir qu'il n'y a qu'une seule solution .
3) Si c'est possible, comment définir une procédure explicite de construction ? D'une solution ? De toutes ?

Exemple 1
d(i)=N-1 pour tout i de 1 à N.
Construction possible avec une seule solution (le graphe complet).

Exemple 2
d(1)=1, d(N)=1, d(i)=2 pour i de 2 à N-1
Construction possible avec une seule solution : le graphe « linéaire » 1-2, 2-3, ..., (N-1)-N

Exemple 3
degrés=(3, 2, 2, 2,1)
Plusieurs solutions.
---
Merci d'avance pour toute suggestion ... constructive

[Kekia]

Bonjour MMVV,

Déjà pour que le graphe existe, il faut que la somme des degrés soit paire puisqu'on compte 2 fois chaque arête.
Donc il y a un nombre pair de sommets de degré impair ce qui supprime déjà ton exemple. Cette condition ne sera malheureusement pas suffisante pour garantir connexe.

Pour avoir la connexité, il faut aussi avoir au minimum N-1 arêtes donc une somme des degrés paire et supérieure ou égale à 2N-2. En revanche, je ne suis pas sure que ce soit suffisant

[lyceen95]

Partons de l'exemple (3,2,2,2,1)
Ici, c'est cool, les 5 sommets sont déjà triés du plus 'relié' au moins relié. Si ce n'est pas le cas, on classe les sommets dans cet ordre.
On a donc (A3,B2,C2,D2,E1)
On prend le premier sommet, il doit être relié à 3 autres points, on prend les 3 premiers sommets
Ca donne 3 arcs AB, AC AD et il reste (B1,C1,D1,E1)
Et on recommence de la même façon : le 1er sommet est B, on a besoin d'un arc partant de B, on va tracer BC, puisque C est le premier sommet après B.
Ca donne AB,AC,AD,BC et il reste (D1,E1)
Et au final, on a ces 5 arcs : AB AC AD BC DE

Redéroulons le processus avec un peu plus de données (A4,B4,C3,D3,E2,F2,G1,H1)
AB AC AD AE + (B3,C2,D2,E1,F2,G1,H1)
Eventuellement,on pourrait retrier par ordre décroissant à chaque étape, mais ce n'est pas une obligation. (Edit : En fait si, dans certains cas, on arrive à un blocage si on ne prend pas cette précaution)
AB AC AD AE BC BD BE + (C1,D1,F2,G1,H1)
AB AC AD AE BC BD BE CD+ (F2,G1,H1)
AB AC AD AE BC BD BE CD FG FH

Si on repart des mêmes données en retriant à chaque fois :
(A4,B4,C3,D3,E2,F2,G1,H1)
AB AC AD AE + (B3,C2,D2,E1,F2,G1,H1) On fait juste un tri , on permute E1 et F2:
AB AC AD AE + (B3,C2,D2,F2,E1,G1,H1)
AB AC AD AE BC BD BF + (C1,D1,F1,E1,G1,H1)
AB AC AD AE BC BD BF CD+ (F1,E1,G1,H1)
AB AC AD AE BC BD BF CD FE+ ( G1,H1)
AB AC AD AE BC BD BF CD FE GH

En mettant les sommets qui doivent avoir beaucoup de liens au début, ça évite des loups.
Mais si on ne retrie pas les sommets par ordre décroissant à chaque étape, on peut avoir ce blocage.
Exemple :
(A7,B7,C7,D4,E3,F3,G3,H3,I3)
AB AC AD AE AF AG AH + (B6,C6,D3,E2,F2,G2,H2,I3)
AB AC AD AE AF AG AH BC BD BE BF BG BH + (C5,D2,E1,F1,G1,H1,I3)
AB AC AD AE AF AG AH BC BD BE BF BG BH CD CE CF CG CH + (D1,I3)
AB AC AD AE AF AG AH BC BD BE BF BG BH CD CE CF CG CH DI+ (I2) Blocage.

[MMVV]

Merci pour les réponses.
Le fait que la somme des degrés doit être paire est une propriété classique (d'ailleurs évidente) :
https://fr.wikipedia.org/wiki/Lemme_des ... es_de_main

Sinon, j'ai trouvé plusieurs algorithmes en ligne, par exemple :
https://www.geeksforgeeks.org/construct ... -vertices/

Je vais les étudier, mais il me manque quand même une preuve de « correction » de ces algorithmes : si aucune solution n'est trouvée cela veut-il dire vraiment dire que c'est impossible ?
Et puis je voudrais construire toutes les solutions possibles.

[lyceen95]

Pour trouver tous les graphes, on est dans le domaine de l'algorithme.
Tu peux passer par une méthode récursive.
Partant de (A3,B2,C2,D2,E1), tu le ramènes à 2 problèmes un peu plus petits :
Problème 1 : (A2,B1,C2,D2,E1) et l'arc AB est dans le graphe
Problème 2 : (A3,B2,C2,D2,E1) et l'arc AB est interdit
Et on continue, chaque problème se redivise en 2 problèmes un peu plus petits.

Mais il faut bien modéliser tout ça.

[MMVV]

La méthode ne garantit pas la connexité :
(A2, B2, C2, D2, E1, F1) => AB, AC, DB, DC, EF

Je regarde aussi du côté de la matrice d'incidence nœuds-arcs (une ligne par nœud et une colonne par arc) telle que par exemple présentée ici:
https://www.sciencedirect.com/topics/ma ... nce-matrix
Ainsi non seulement les sommes en lignes sont les degrés, mais chaque colonne contient exactement deux 1. Et son rang est nombre_de_nœuds -1.

[MMVV]

Une méthode intéressante ici :
http://szhorvat.net/pelican/hh-connected-graphs.html
surtout de par son théorème de faisabilité.
L'algorithme soit trouve une solution connexe, soit pas de solution et ne propose pas de solution non connexe.
En tout cas plus l'on cherche plus l'on voit que ce problème a déjà été largement étudié et, surtout, résolu. Apparemment l'algorithme est même inclus dans Mathematica (fonction IGRealizeDegreeSequence) : http://szhorvat.net/pelican/igraphm-a-m ... graph.html

[lyceen95]

Ah, la connexité !!! Je pensais que c'était facultatif.
Adaptons.
(A2, B2, C2, D2, E1, F1) , je le note maintenant (A2.2 , B2.2, C2.2, D2.2, E1.1, F1.1)
C'est à dire :
A= l'identifiant du sommet
2 = le nombre d'arcs 'au début'
.2 = le nombre d'arcs qu'il faut encore trouver pour ce point.
(A2.2, B2.2, C2.2, D2.2, E1.1, F1.1) : Je prends A, et je l'associe à 2 autres sommets, les 2 premiers dans l'ordre de mon tableau.
(B2.1, C2.1 D2.2, E1.1, F1.1) + arcs AB, AC
On trie, sur le nombre d'arcs restant à pourvoir, en ordre décroissant, et en cas d'ex-aequo, sur le nombre d'arcs au début, en ordre croissant
(D2.2, E1.1, F1.1, B2.1, C2.1) + arcs AB, AC
(B2.1, C2.1) + arcs AB, AC, DE, DF
arcs AB, AC, DE, DF BC

Ca devrait être beaucoup mieux pour l'objectif 'connexité', mais pas sûr du tout que ça donne toujours un graphe connexe, même quand c'est possible.
Mais de toutes façons, si l'objectif est de recenser tous les graphes (connexes) compatibles, ce n'est pas du tout une bonne piste.

Et en voyant ton dernier message : oui, il y a certainement plein de littérature sur le sujet.