Trouver spanning tree que spécifique v a k degrés

Question

quelqu'un peut-il expliquer pour moi comment le résoudre je sais que nous devrions utiliser DFS, mais je ne comprends pas ce que nous faisons après cela.

input : undirected graph G and specific v that belong to the G 
output : spanning tree that v has k degree 

Answer 1

Je vais suggérer la façon suivante. Ici, je suppose que G est connecté. Supprimez d'abord v du graphique, trouvez l'arbre recouvrant pour chacun des composants restants. Maintenant, vous pouvez avoir un seul Spanning Tree ou une forêt en fonction du graphe, vous pouvez rajouter v et utiliser les arêtes pour connecter v et chacun de Spanning Tree.

Ensuite, vous aurez un arbre couvrant de G, et il y aura trois cas.

cas 1: degré v> k, dans ce cas, la tâche est impossible

Cas n ° 2: degré v = k, vous avez la réponse.

cas 3:. Degré v < k, alors vous suffit d'ajouter des bords inutilisés de v Chaque fois que vous ajoutez un bord, vous allez créer un cycle, alors vous pouvez juste choisir un bord qui ne touche pas v et retirez-le . Vous continuez à ajouter des arêtes jusqu'à ce que vous ayez votre réponse ou que toutes les arêtes soient épuisées. Cependant, je ne peux pas penser à un moyen rapide d'interroger un cycle en plus de faire bfs/dfs.

Mise à jour: Il existe un moyen plus rapide pour cas 3 par Matt, après la connexion v à k voisins appropriés, utiliser l'algorithme de Kruskal ou Prim de remplir le reste de l'arbre couvrant, en commençant par les bords de v que vous avez déjà.

Answer 2

Voici un algorithme que je fournis, mais sa force brute.

Condition pour que cet arbre existe: si le degree of v < k, alors cet arbre n'existe pas.

suivre le reste de l'algorithme en tant que:

Choix k sommets de tous les sommets adjacents de v,

1.mark all adjacent vertices of v as VISITED. 

2.From each of those adjacent vertices , call DFS and the spanning tree grows. 

3.After all DFS is complete,if all vertices of graph G are marked VISITED, then we 
have our spanning tree, if a single vertex or more are left UNVISITED, then the 
4.pick another set of k vertices. 

si v a X que le degré et X > k, alors l'étape 4 doit être répétée XCk(X choose k) fois dans le pire des cas.

Answer 3

On peut penser de cette façon aussi:

1. Pour le sommet donné v entre tous les voisins v_i S.T. (v, v_i) dans E (G) choisir k arêtes avec les plus petits poids w (v, v_i), nous avons besoin de O (d * lg (d)) temps où deg (v) = d> = k. Ajoutez ces arêtes à l'ensemble de bord Spanning Tree S. Nous devons de toute façon ajouter ces arêtes à S pour nous assurer que la contrainte est respectée. Supprimer le sommet v du graphe G avec toutes les arêtes incidentes sur v. Maintenant, exécuter Prim/Kruskal sur le graphe G \ {v} en commençant par l'arête S, l'algorithme lui-même ajoutera des arêtes assurant l'acyclique et propriétés minimales. Cela fonctionnera dans O (m * lg (n)).

En supposant que d petite étape 1 & 2 fonctionne en O (m * lg (n)).