A deux voies arbre minimum de découpage d'un graphe orienté

Question

Étant donné un graphe orienté avec des bords pondérés, quel algorithme peut être utilisé pour donner un sous-graphique qui a un poids minimum, mais permet le déplacement de tout sommet à un autre sommet dans le graphe (sous l'hypothèse que les chemins entre deux sommets existe toujours).

Est-ce qu'un tel algorithme existe?

Answer 1

Cela semble être NP-dur. Le poids minimum fortement connecté couvrant problème de sous-graphe

Je crois problème du cycle hamiltonien peut être réduit à ce: Etant donné un graphe G (V, E), la construction d'un digraphe DG avec le poids 1 pour les bords qui apparaissent et poids 100 (| V | +1) pour les arêtes qui n » t. DG a un poids minimum fortement connecté couvrant exactement sous-graphe de poids | V | si et seulement si G a un cycle hamiltonien.

Le document présente ici un algorithme d'approximation: http://portal.acm.org /citation.cfm?id=844363

Answer 2

Même si elles ne sont pas eux-mêmes à droite, prendre le temps de suivre les liens Wikipédia de Vitalii découvert rapidement cet algorithme:

http://en.wikipedia.org/wiki/Chu % E2% 80% 93Liu / Edmonds_algorithm

Answer 3

Diviser chaque nœud du graphe en deux noeuds. Un nœud acceptera tous les bords entrants vers le nœud d'origine, et l'autre aura tous les bords sortants. Ensuite, laissez tomber la direction sur tous les bords, de sorte que le graphique est non orienté. Ensuite, vous pouvez exécuter un algorithme standard MST sur le graphique (Prim de son, Kruskal) et vous assurer que chaque nœud d'origine peut être parcourue par tous les autres noeuds d'origine.

Answer 4

Ceci est un Directed Arbre Steiner problème. Comme l'arbre Steiner, il est NP-dur.

Vous pouvez trouver des algorithmes de aproximate ici:

http://citeseerx.ist .psu.edu / viewdoc / téléchargement? doi = 10.1.1.38.8774 & rep = rep1 & type = ps

Answer 5

Pick tout nœud et le retourner.

Vouliez-vous dire peut-être trouver le plus fortement connectés sous-graphe (moins nombre de noeuds supprimés possible), ou poids minimum couvrant (pas de sous-graphes transfert de noeud permis)?