Graphe non-dirigé la conversion de l'arbre

voici une suggestion sur la façon de résoudre votre problème.

conditions préalables

• notation:
  
  • g graphique, g.v graphe de sommets
  • v,w,z: sommets
  • e: edge individuel
  • n: nombre de sommets
• n'importe quelle combinaison des non-orienté arbre de g et d'un nœud donné.g.v unique détermine dirigé arbre avec racine de g.v (prouvable par induction)

idée

• compléter les bords de g par les orientations de l'arbre implicite par g et la encore-à-être-trouvé nœud racine par des calculs locaux sur les nœuds de g.
• ces orientations seront représentent enfant-parent-relationsships entre les nœuds (v -> w: v enfant, w parent).
• le tout marqué de l'arbre contient un seul nœud avec outdegree 0, qui est le nœud racine de votre choix. vous pourriez vous retrouver avec 0 ou plus d'un nœud racine.

algorithme

assume la représentation standard de la graphique de l'arborescence de la structure (par exemple la liste d'adjacence)

1. tous les sommets de g.v sont marqués d'abord comme pas de visites, pas fini.

2. visiter tous les sommets de suite arbitraire. ignorer les nœuds marqués comme "fini".
   
   laissez v être actuellement sommet visité.

   • 2.1 balayer toutes les arêtes reliant v des aiguilles d'une montre en commençant par un choisi au hasard e_0 dans l'ordre des bords de l'angle avec e_0.

   • 2.2. orienter les arêtes adjacentes e_1=(v,w_1), e_2(v,w_2), qui entourent un angle aigu.
     
     adjacent: wrt être commandés en fonction de l'angle qu'ils renferment avec e_0.

     [ note: l'existence de cette paire n'est pas garanti, voir 2ème commentaire et dernière remarque. si aucun angle est aigu, passez au point 2. avec le nœud suivant. ]

     • 2.2.1 les orientations des arêtes e_1, e_2 sont connus:

       • w_1 -> v -> w_2: impossible, comme un grand-parent-enfant-segment englobe un angle aigu
       • w_1 <- v <- w_2: impossible, même raison

       • w_1 <- v -> w_2: impossible, il n'y a pas de nœuds avec outdegree >1 dans un arbre

       • w_1 -> v <- w_2:
         
         seule paire possible d'orientations. e_1, e_2 pourrait avoir été orienté avant. si l'orientation précédente viole l'affectation actuelle, le problème de l'instance n'a pas de solution.

     • 2.2.2 cette mission implique une structure arborescente sur le sousgraphes induite par tous les sommets accessibles depuis w_1 (w_2) sur un chemin ne comprenant pas de e_1 (e_2`). marquer tous les sommets dans les deux induite par les sous-arbres finis

       [ note: la sous-arborescence de la structure peut violer l'angle des contraintes. dans ce cas, le problème n'a pas de solution. ]

   • 2.3 marque v visité. après avoir terminé les étapes 2.2 au sommet v, de vérifier le nombre nc des bords de la connexion qui n'ont pas encore été affectés à une orientation.

     • nc = 0: c'est la racine que vous avez été à la recherche pour - mais vous devez vérifier si la solution est compatible avec vos contraintes.

     • nc = 1: laissez cette arête être (v,z).
       
       l'orientation de ce bord est v->z que vous êtes dans un arbre. la marque de v comme fini.

       • 2.3.1 vérifier z si il est marqué terminé.
         si elle n'est pas, vérifiez le nombre nc2 de pas orientées arêtes reliant z.
         nc2 = 1: répétez l'étape 2.3 en prenant z pour v.

3. si vous n'avez pas encore trouvé un nœud racine de votre problème instance est ambiguë:
   orienter le reste pas orientées bords.

remarques

1. résiliation:
   chaque nœud est visité au max 4 fois:

   • une fois par l'étape 2
   • au max deux fois par étape 2.2.2
   • au max une fois par étape 2.3

2. exactitude:

   • toutes les arêtes joignant un angle aigu sont orientés par étape 2.2.1

3. complexité (temps):

   • la visite de chaque nœud: O(n);

   • le balayage des aiguilles d'une montre par le biais de tous les bords de la connexion à un même sommet a besoin de ces bords afin d'être triés.
     
     ainsi, vous devez O( sum_i=1..m ( k_i * lg k_i ) ) à m <= n sommets sous la contrainte sum_i=1..m k_i = n.

     au total cela nécessite O ( n * lg n), comme sum_i=1..m ( k_i * lg k_i ) <= n * lg n donné sum_i=1..m k_i = n pour tout m <= n (démontrable par l'application de lagrange d'optimisation).

     [ note: si vos arbres ont un degré borné par une constante, vous avez théoriquement de tri en temps constant à chaque nœud affecté; grand total dans ce cas: O(n) ]

   • de la sous-arborescence de marquage:
     
     chaque nœud du graphe est visité au max 2 fois par cette procédure si elles sont appliquées comme un dfs. donc un grand total de O(n) pour l'invocation de cette sous-routine.

     au total: O(n * lg n)

4. complexité (de l'espace):

   • O(n) de tri (avec un sommet de degré et pas constant lié).

5. problème est probablement mal définis:

   • plusieurs solutions: par exemple, steiner tree
   • pas de solution: par exemple, le graphique, la forme d'un double pointe de flèche (<->)

OriginalL'auteur collapsar