Ungerichtete Graphen Umstellung auf Baum

Gegeben ungerichtete Graphen, in dem jeder Knoten hat ein Kartesisches Koordinatensystem im Raum, hat die Allgemeine Form eines Baumes, gibt es einen Algorithmus zum konvertieren des Graphen in einem Baum, und suchen Sie den entsprechenden root-Knoten?

Beachten Sie, dass unsere definition von "Baum" erfordert, dass die Zweige nicht abweichen von den Eltern-Knoten, in Spitzen Winkeln.

Beispiel siehe Diagramme unten. Wie finden wir die roten Knoten?

Ungerichtete Graphen Umstellung auf Baum
Ungerichtete Graphen Umstellung auf Baum

  • In diesem Beispiel ungerichteter graph, jeder Knoten genommen werden konnte, als die Wurzel, und Sie möchten Holen Sie sich ein richtiger Baum. Wenn ich es hinbekommen, die Knoten die Wurzel hängt von der räumlichen Anordnung der Knoten. Aber es ist mir nicht klar, wie und was du meinst mit "verzweigt nicht abweichen vom übergeordneten Knoten zu Spitzen Winkel". Können Sie das klären? Können Sie erklären, z.B. warum die oberste oder am weitesten rechts liegenden Knoten können nicht sein die Wurzel für Ihre Anwendung?
  • meinst du, dass die Winkel zwischen den Zweigen verknüpfen Geschwister, um Ihre (gemeinsamen) Eltern-Knoten muss nicht akut sein ? haben Sie eine Daten-Struktur auf über Koordinaten und Graphen-Struktur ? abgesehen von dem Grad der root-Knoten, werden Ihre Bäume werden binäre ? binäre Bäume wäre leichter zu verarbeiten als genau 1 der 3 Winkel zwischen den benachbarten Kanten ist die akute, also Eltern/Kind-Beziehungen ermittelt werden konnten lokal.
  • beachten Sie, dass Ihr problem scheint zu sein, schlecht definiert: betrachten Sie jeden steiner-Baum; es sind keine die Spitzen Winkel zwischen den ästen an alle. daher ist jeder Knoten gewählt werden konnte, da ein root-Knoten, ohne zu verletzen Ihre Einschränkung
  • nicht jeder Knoten Wurzel eines Baumes, je nachdem, wie Sie auf die Grafik schauen?
InformationsquelleAutor paniwani | 2011-11-06
  1. 10

    hier ist ein Vorschlag, wie Ihr problem zu lösen.

    Voraussetzungen

    • notation:
      • g graph g.v graph Eckpunkte
      • v,w,z: vertices
      • e: einzelne Kante
      • n: Anzahl der Eckpunkte
    • jede Kombination aus einem ungerichteten Baum g und einen gegebenen Knoten g.v eindeutig bestimmt, einen gerichteten Baum mit Wurzel g.v (beweisbar durch Induktion)

    Idee

    • ergänzen die Kanten der g von Orientierungen in den gerichteten Baum impliziert g und das noch-zu-sein-gefunden root-Knoten durch lokale Berechnungen auf den Knoten g.
    • diese Leitlinien repräsentieren Kind-Eltern-relationsships zwischen den Knoten (v -> w: v Kind w Eltern).
    • die komplett markierten Baum enthält eine einzige Knoten mit outdegree 0, was ist ein root-Knoten. Sie könnten am Ende mit 0 oder mehr als ein root-Knoten.

    Algorithmus

    übernimmt die standard-Darstellung des Graphen/Baum-Struktur (z.B. Nähe-Liste)

    1. alle Scheitelpunkte in g.v markiert sind zunächst als nicht besucht, nicht fertig.

    2. besuchen Sie alle Eckpunkte in beliebiger Reihenfolge. skip-Knoten markiert als "fertig" ist.

      lassen Sie v werden, der derzeit besuchten vertex.

      • 2.1 sweep durch alle Kanten die Verknüpfung v im Uhrzeigersinn, beginnend mit einem zufällig gewählten e_0 in der Reihenfolge der Kanten Winkel mit e_0.

      • 2.2. orient angrenzenden Kanten e_1=(v,w_1), e_2(v,w_2), dass umschließen einen Spitzen Winkel.

        angrenzend: wrt bestellt werden, entsprechend dem Winkel, den Sie einschließen, mit e_0.

        [ Hinweis: die Existenz eines solchen Paares ist nicht garantiert, siehe 2. Kommentar und Letzte Bemerkung. wenn kein Winkel ist akut, gehen Sie mit 2. mit dem nächsten Knoten. ]

        • 2.2.1 die Orientierungen der Kanten e_1, e_2 sind bekannt:

          • w_1 -> v -> w_2: unmöglich, wie eine Großeltern-Kind-segment würde umschließen einen Spitzen Winkel
          • w_1 <- v <- w_2: unmöglich, denselben Grund

          • w_1 <- v -> w_2: unmöglich, es gibt keine Knoten mit outdegree >1 in einem Baum

          • w_1 -> v <- w_2:

            nur möglich, paar Orientierungen. e_1, e_2 gewesen sein könnte, orientiert vor. wenn die Vorherige Ausrichtung gegen die aktuelle Belegung, die problem-Instanz keine Lösung hat.

        • 2.2.2 diese Zuordnung impliziert eine Struktur, die auf die Teilgraphen, die durch alle Eckpunkte erreichbar von w_1 (w_2) auf einem Pfad nicht aus e_1 (e_2`). markieren Sie alle Scheitelpunkte in beiden induzierten Teilbäume als fertige

          [ Hinweis: der Teilbaum Struktur kann eine Verletzung der Winkel Einschränkungen. in diesem Fall das problem hat keine Lösung. ]

      • 2.3 mark v besucht. nach Abschluss der Schritte 2.2 am Scheitelpunkt v, überprüfen Sie die Anzahl nc Kanten anschließen, die noch nicht zugeordnet wurden, eine Orientierung.

        • nc = 0: das ist die Wurzel, die Sie gesucht habe - aber Sie müssen überprüfen, ob die Lösung, die kompatibel mit deinen Einschränkungen.

        • nc = 1: lassen Sie dies edge sein (v,z).

          die Orientierung dieser Kante ist v->z, wie Sie in einem Baum. mark v als beendet.

          • 2.3.1 prüfen z ob es markiert ist fertig.
            wenn es nicht, überprüfen Sie die Anzahl nc2 von unoriented Kanten verbinden z.
            nc2 = 1: wiederholen Sie Schritt 2.3 durch die Einnahme z für v.

    3. wenn Sie noch nicht gefunden haben einen root-Knoten, Ihr problem Instanz ist zweideutig:
      richten Sie die verbleibenden unoriented Kanten auf.

    Bemerkungen

    1. Kündigung:
      jeder Knoten wird besucht, bei max 4 mal:

      • einmal pro Schritt 2
      • bei max zweimal pro Schritt 2.2.2
      • bei max einmal pro Schritt 2.3

    2. Richtigkeit:

      • alle Kanten umschließen einen Spitzen Winkel orientiert sind pro Schritt 2.2.1

    3. Komplexität (Zeit):

      • Besuch aller Knoten: O(n);

      • den Uhrzeigersinn sweep über alle Kanten verbinden einen bestimmten Scheitelpunkt erfordert diese Kanten werden sortiert.

        so müssen Sie O( sum_i=1..m ( k_i * lg k_i ) ) bei m <= n Eckpunkte unter dem Zwang sum_i=1..m k_i = n.

        insgesamt erfordert dies O ( n * lg n) als sum_i=1..m ( k_i * lg k_i ) <= n * lg n gegeben sum_i=1..m k_i = n für alle m <= n (nachweisbar durch Anwendung der lagrange-Optimierung).

        [ Hinweis: wenn Ihr Bäume haben ein Maß begrenzt durch eine Konstante, Sie theoretisch Sortieren in konstanter Zeit auf den einzelnen Knoten betroffen; die Gesamtsumme in diesem Fall: O(n) ]

      • Teilbaum markieren:

        jeder Knoten im graph ist, besucht max 2 mal durch dieses Verfahren umgesetzt werden, wenn als dfs. somit eine Gesamtsumme von O(n) für den Aufruf dieses Unterprogramms.

        insgesamt: O(n * lg n)

    4. Komplexität (Speicherplatz):

      • O(n) für die Sortierung (mit vertex-Grad-keine-Konstante-gebunden).

    5. problem ist wahrscheinlich schlecht-definiert:

      • mehrere Lösungen: z.B. steinerbaum
      • keine Lösung: z.B. graph die Form einer Doppel-Spitze Pfeil (<->)
    • Verdammt.. ich war auf der Suche nach dem Gegenteil von den OP ' s Frage, aber diese Nägel. Gut erklärt, gut dokumentiert. Tolle Antwort. (Alter post, ich weiß)
    InformationsquelleAutor collapsar
  2. 0

    Einfache Lösung wäre zu definieren, wie ein 2d-Rechteck um den roten Knoten oder in der Mitte Ihres compute-Knoten und jeder Knoten mit einer moore-Kurve. Eine moore Kurve ist ein space-filling-curve, mehr über eine spezielle version der hilbert-Kurve, wo der start-und end-vertex ist die gleiche, und der Koordinate ist in der Mitte der 2d-Rechteck. In generell dein problem sieht aus wie eine diskrete Adressierung Speicherplatz-problem.

    InformationsquelleAutor Gigamegs
Schreibe einen Kommentar