Connexité et degré minimum

Bonjour à tous,

j'aimerai pouvoir générer, à partir d'un ensemble de noeuds (spécifiés par leur coordonnée [x,y]), un graphe qui soit connexe et k-connecté.

Le paramètre k serait une entrée de mon algorithme.

Ma première idée serait d'utiliser un algorithme d'arbre recouvrant type Prime ou Kruskal afin d'avoir au moins un chemin entre chaque paire de noeud.

Ensuite, je testerais le degrés de chacun des noeuds en venant ajouter un arc entre le noeud courant et un autre noeud choisit aléatoirement pour atteindre le degré k...

Existe-t-il des algorithmes précis pour ce genre de problème?

Merci d'avance.

Citation:

---

Envoyé par dvp_zero

Bonjour à tous,

j'aimerai pouvoir générer, à partir d'un ensemble de noeuds (spécifiés par leur coordonnée [x,y]), un graphe qui soit connexe et k-connecté.

Le paramètre k serait une entrée de mon algorithme.

Ma première idée serait d'utiliser un algorithme d'arbre recouvrant type Prime ou Kruskal afin d'avoir au moins un chemin entre chaque paire de noeud.

Ensuite, je testerais le degrés de chacun des noeuds en venant ajouter un arc entre le noeud courant et un autre noeud choisit aléatoirement pour atteindre le degré k...

Existe-t-il des algorithmes précis pour ce genre de problème?

Merci d'avance.

---

J'ai trouvé plusieurs définitions pour un graphe k-connecté :
-Un graphe est dit k-connecté si pour chaque paire de nœuds il existe au moins k chemins de noeuds disjoints connectant le graphe
-Un graphe est k-connecté si tous ses sommets sont de degré k.

Je pense que tu prends la deuxième. Es tu sûr que toutes les combinaisons sont possibles (en fonction de la parité de k et de n) ?

Personnellement je tentai une approche "incrémentale". Je commencerai par un graphe avec peu de nœud et un petit k. Et j'augmenterai petit à petit le nombre de nœud et la valeur de k. Ou par construction à partir de graphes triviaux. Ce ne sont que des pistes je ne garantis pas que la solution se trouve là :).

Merci pour ton message.

C'est effectivement la deuxième définition qui m'intéresse.

Lorsque tu parles des combinaisons possibles en fonction de la parité de k et de n, que veux-tu dire par là?
Qu'il ne serait pas toujours possible d'atteindre n'importe quelle valeur de k en fonction du nombre n de noeuds du graphe?

Si j'ai bien compris, ça ne devrait pas trop poser de problème car le nombre de noeuds de mon graphe est grand.

Oui ton idée est bien mais le problème c'est que le nombre de noeuds est fixé au départ, il me sera donc difficile de partir d'un graphe "général" à toute les situation.

Citation:

---

Envoyé par dvp_zero

Lorsque tu parles des combinaisons possibles en fonction de la parité de k et de n, que veux-tu dire par là?
Qu'il ne serait pas toujours possible d'atteindre n'importe quelle valeur de k en fonction du nombre n de noeuds du graphe?

---

Oui je me demandais si toutes les combinaisons n-k sont possibles (autres que les cas ou k>=n).

Citation:

---

Envoyé par dvp_zero

Oui ton idée est bien mais le problème c'est que le nombre de noeuds est fixé au départ, il me sera donc difficile de partir d'un graphe "général" à toute les situation.

---

Je pensais partir par exemple, pour un k fixé, d'un graphe complet à (k+1) nœuds. Et d'augmenter progressivement le nombre de nœud jusqu'à avoir n nœuds. Reste à mettre au point la méthode permettant de passer d'un graphe connexe de degré k à m sommets à un graphe connexe de degré k à (m+1) sommets. Mais j'avais l'intuition que cela pouvait se faire simplement.

Après ça reste qu'une idée, c'est toi qui voit ce qui te semble le plus prometteur. ;)

Bonjour je pense que tu parle d'un graphe K-régulier c'est à dire que chaque sommet est connecté à K autres sommets .

pour les combinaisons , elle ne sont pas toutes possibles , je sais qu'il y a deux contraintes ( et peut être y en a d'autres ) .

1)
k doit être inférieur à N , un graphe à N sommet peut être au max (N-1)-régulier donc chaque nœud dans ce cas est lié à tous les autres nœuds et on dit que c'est un graphe complet .

2)
le nombre d’arrêtés est de k*n/2 ( tu peux vérifier ) et donc il y a une contrainte de parité du produit K*n car le nombre arrêtes est entier (évidemment :P)
pare exemple tu peux pas avoir un graphe d'ordre N et K-régulier ou K et N sont impairs .

pour l'algorithme je pense que j'en ai déjà vu Un ( qui est très simple à ce que je me rappelle ) , je vais le ré-chercher , mais tu peux me dire si tu veux générer un graphe quelconque ou tous les graphes ???

Merci pour ce complément d'informations.

Je viens d'allé voir la définition d'un graphe k-régulier et c'est bien ce que je veux à une nuance près : tous les noeuds de mon graphe ne sont pas obligés d'avoir le même degré. Il y a simplement une contrainte sur le degré minimum.

Pour répondre à ta question, c'est bien un graphe quelconque que je veux générer.

Merci beaucoup :P

Citation:

---

Envoyé par Acrim

Oui je me demandais si toutes les combinaisons n-k sont possibles (autres que les cas ou k>=n).




Je pensais partir par exemple, pour un k fixé, d'un graphe complet à (k+1) nœuds. Et d'augmenter progressivement le nombre de nœud jusqu'à avoir n nœuds. Reste à mettre au point la méthode permettant de passer d'un graphe connexe de degré k à m sommets à un graphe connexe de degré k à (m+1) sommets. Mais j'avais l'intuition que cela pouvait se faire simplement.

Après ça reste qu'une idée, c'est toi qui voit ce qui te semble le plus prometteur. ;)

---

excusez moi je pensais que vous parlez des graphes réguliers

sinon je pense que pour le passage de m à m+1 en gardant k ,
tu peux retirer k/2 ou(k+1/2 selon la parité de k ) arcs associés à k ou (k+1) nœuds ( on ne supprime pas plus d'un arc pour un nœud) et ajouter nouveau nœud puis le lier par k ou (k+1) arcs à ces nœuds :)
si j'ai bien compris

Bonjour, désolé pour la méprise, j'avais compris la même chose que Mohammed_S. Effectivement si k est seulement le degré minimum à atteindre, la démarche que tu décris dans ton premier message devrait fonctionner.