sous-graphe connexe contenant au moins un ensemble de noeuds

Question

J'ai un graphe non pondéré, connecté. Je veux trouver un sous-graphe connexe qui comprend certainement un certain ensemble de nœuds, et que quelques extras que possible. Comment cela pourrait-il se faire?

Juste au cas où, je vais reformuler la question en utilisant un langage plus précis. Soit G (V, E) un non pondéré, undirected, graphe connexe. Soit N un sous-ensemble de V. Quelle est la meilleure façon de trouver le plus petit G connecté sous-graphe « (V », E ') de G (V, E) tel que N est un sous-ensemble de V?

Approximations sont très bien.

Answer 1

Je ne peux pas penser à un algorithme efficace pour trouver la solution optimale, mais en supposant que votre graphique d'entrée est dense, ce qui suit pourrait fonctionner assez bien:

1. Convertir votre graphique d'entrée G(V, E) à un graphe pondéré G'(N, D), où N est le sous-ensemble de sommets que vous voulez couvrir et D est des distances (longueurs de trajet) entre les sommets correspondant dans le graphique d'origine. Cela « effondrement » tous les sommets ne vous ont pas besoin dans les bords.

2. Calculer l'arbre de recouvrement minimal pour G'.

3. « Développez » l'arbre couvrant minimal par la procédure suivante: pour chaque d de bord dans le minimum Spanning Tree, prendre le chemin correspondant dans le graphique G et ajouter tous les sommets (y compris les points d'extrémité) sur le chemin du jeu de résultats V' et tous les bords de la voie de l'ensemble de résultats E'.

Cet algorithme est facile à désarçonner pour donner des solutions non optimales. Exemple cas: triangle équilatéral, où il y a des sommets au niveau des coins, en milieux des côtés et au milieu du triangle, et les bords le long des côtés et des coins jusqu'au milieu du triangle. Pour couvrir les coins, il suffit de choisir le point central unique du triangle, mais cet algorithme peut choisir les côtés. Néanmoins, si le graphe est dense, il devrait fonctionner OK.

Answer 2

Ceci est exactement le bien connu NP-dur problème de Steiner Tree. Sans plus de détails sur ce que vos instances ressemblent, il est difficile de donner des conseils sur un algorithme approprié.

Answer 3

Les solutions les plus simples seront les suivants:

a) basé sur mst:    - d'abord, tous les noeuds de V sont en V »    - construire un arbre couvrant minimal du graphe G (V, E) - appeler T.
   - boucle:. Pour chaque feuille v T qui ne sont pas en N, suppression V de V »
   - boucle répétition jusqu'à ce que toutes les feuilles en T sont N.

b) une autre solution est la suivante - basée sur l'arbre des plus courts chemins
.    - choisir un nœud en N, appelez-v, soit v une racine d'un arbre T = {v}.    - supprimer v de N.

boucle
• : 1) sélectionner le chemin le plus court depuis un noeud quelconque en T et un noeud quelconque dans le plus court chemin N. p: {v, ..., u}, où v est en T et u est dans N.  2) chaque noeud p est ajouté à V ».  3) chaque noeud P et en N est supprimé de N. --- boucle de répétition jusqu'à ce que N est vide.

Au début de l'algorithme: calculer tous les chemins les plus courts dans G en utilisant tout algorithme efficace connu.

Personnellement, j'ai utilisé cet algorithme dans un de mes papiers, mais il est plus approprié pour les environnements distribués. Soit N l'ensemble des noeuds que nous devons interconnexion. Nous voulons construire un minimum connecté ensemble dominant du graphe G, et nous voulons donner la priorité pour les noeuds de N. Nous donnons à chaque noeud u un identifiant de l'identificateur unique (u). Nous laissons w (u) = 0 si u est dans le N, sinon w (1). Nous créons paire (p (u), id (u)) pour chaque noeud u.

• u chaque noeud construit un noeud relais multiset. Autrement dit, un ensemble M (u) de 1-hop neigbhors de telle sorte que chaque voisin 2-hop est un voisin d'au moins un noeud dans M (u). [Le minimum M (u), meilleure est la solution].

• u se trouve dans V » si et seulement si: u a la plus petite paire (p (u), id (u)) entre tous ses voisins. ou U est choisi dans le M (v) où v est un voisin de 1-hop u avec le plus petit (p (u), id (u)).

- l'astuce lorsque vous exécutez cet algorithme de manière centralisée pour être efficace dans le calcul de voisins à 2 sauts. Le mieux que je pouvais obtenir de O (n ^ 3) est à O (n ^ 2,37) par multiplication de la matrice.

-. Je voudrais vraiment savoir quelle est la ration d'approximation de cette dernière solution

J'aime cette référence pour heuristiques d'arbres steiner: Le problème de l'arbre de Steiner, Hwang Frank; Richards Dana 1955- hiver Pawel 1952

Answer 4

Vous pouvez essayer de faire ce qui suit:

1. Création d'un sommet couverture minimale pour les noeuds souhaité N.

2. Réduire ces derniers, peut-être sans lien, sous-graphes en nœuds "grands". C'est, pour chaque sous-graphe, retirez du graphique, et le remplacer par un nouveau nœud. Appelez cet ensemble de nœuds N'.

3. Faites un sommet-couverture minimale des noeuds N'.

4. "Décompresser" les noeuds N'.

Je ne sais pas si oui ou non il vous donne une approximation au sein de certains spécifiques liés ou si. Vous pourriez peut-être même tromper l'algorithme de prendre des décisions vraiment stupides.