Gibt es einen Non-Brute-Force-Algorithmus für die Eulerisierung von Graphen?

Bei einem ungerichteten, ungewichteten, verbundenen und möglicherweise parallelen Graphen kann eine Euler-Schaltung konstruiert werden, wenn jeder Scheitelpunkt in einen geraden Grad hat.$G$$G$

In Graphen mit zwei oder mehr Scheitelpunkten ungeraden Grades (es kann nur ein Vielfaches von zwei geben) muss der Graph "Eulerisiert" werden, wobei die ungeraden Scheitelpunkte bei Bedarf mit zusätzlichen Kanten durch andere Scheitelpunkte verbunden werden.

Der optimale Fall für die Eulerisierung ist die Konstruktion von nur Kanten, wobei die Anzahl der Scheitelpunkte ungeraden Grades ist. Dies kann jedoch nur dann der Fall sein, wenn jeder ungerade Scheitelpunkt einen benachbarten Partner hat, sodass wir beide Scheitelpunkte mit verbinden können eine Kante und beide gleichmäßig machen.$n/2$$n$

Davon abgesehen benötigen die meisten Diagramme mehr als Kanten. Als Menschen tendieren wir dazu, Graphen zu eulerisieren, indem wir immer jedes Paar ungerader Eckpunkte auswählen, die nebeneinander liegen, und dann für den Rest Versuch und Irrtum verwenden. Dies funktioniert jedoch nicht immer.$n/2$

Wenn Sie im folgenden Diagramm beispielsweise eine Kante zwischen dem Paar benachbarter ungerader Eckpunkte hinzufügen und Kanten verwenden, um zu verbinden, wird eine Eulerisierung durchgeführt, die Kanten kostet . Wenn Sie jedoch stattdessen und eine Eulerisierung, die Kanten kostet , obwohl die benachbarten ungeraden Scheitelpunkte nicht zu ihrem Vorteil verwendet wurden.$1\leftrightarrow 2$$5$$3\leftrightarrow 4$$6$$1\leftrightarrow 4$$2\leftrightarrow 3$$5$

Ich weiß mit Sicherheit, dass dieses Problem zumindest durch rohe Gewalt lösbar ist, da die Anzahl der Paare ungerader Eckpunkte, die mit einer bestimmten Anzahl von Kanten verbunden werden sollten, endlich ist. Insbesondere gibt es ( Mathematica sagte dies ) mögliche Sätze von Paaren ungerader Eckpunkte, die verbunden werden können. Es ist möglich, jeden einzelnen zu durchlaufen und jeden Scheitelpunkt mit seinem Partner zu verknüpfen (das Finden des kürzesten Pfades zwischen den beiden Scheitelpunkten in einem ungerichteten Diagramm ist wahrscheinlich eine Herausforderung für sich, für die Wikipedia keine zeitliche Komplexität angibt ).$2^{n/2} \Gamma(\frac{n+1}{2})/\sqrt{\pi}$

Am Ende läuft der ganze Deal wahrscheinlich in Polynomzeiten Exponentialzeiten Fakultätszeit, was ziemlich böse ist. Ich habe einige grundlegende Untersuchungen durchgeführt, ob es Algorithmen gibt, die Pfade Eulerisieren, aber keine zu finden scheinen.

Mathematica- Code für Grafik:

GraphPlot[
  {1 -> 2, 2 -> 5, 5 -> 3, 3 -> 6, 6 -> 3, 6 -> 7, 7 -> 6, 2 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 4, 4 -> 11, 11 -> 4, 11 -> 12, 12 -> 1, 1 -> 12}, 
  VertexRenderingFunction -> 
    (If[#2 < 5, 
        Text[Style[#2, Large], #1, Background -> Yellow], Null] &)]

Betrachten Sie das chinesische Postbotenproblem bei ungerichteten Graphen: Suchen Sie bei einem ungerichteten Graphen den kürzesten Stromkreis des Graphen, der jede Kante mindestens einmal durchläuft. Wenn nun Euler ist, dann ist die Euler-Schaltung die kürzeste solche Schaltung. Wenn nicht, werden einige Kanten mehr als einmal zurückgelegt. Mit anderen Worten, einige Kanten werden dupliziert, und die Schaltung ist im Diagramm mit diesen zusätzlichen Kanten Eulersch.$G$$G$

Um den kürzesten Stromkreis zu erhalten, muss nun die Kantenverdoppelung minimiert werden. Dies ist das gleiche wie Ihr Problem. Sie müssen einen neuen Graphen der alle Kanten von und einige zusätzliche parallele Kanten enthält - so wenige zusätzliche Kanten wie möglich -, damit Eulersch ist. Jede zusätzliche Kante in entspricht der Tatsache, dass ihre entsprechende parallele Kante in in einer kürzesten vollständigen Schaltung von . Mit anderen Worten, die optimale (minimale) "Eulerisierung" entspricht dem chinesischen Postbotenproblem. Für eine bessere ausgedrückt Erklärung hierfür finden Sie in Abschnitt 4 (Chinese Postman Problem) und Definition 11 (Eulerization, Minimal Eulerization) von diesen$H$$G$$H$$H$$G$$G$Anmerkungen. Glücklicherweise ist dies für ungerichtete Graphen in Polynomzeit lösbar.

Für das chinesische Postbotenproblem hat Wikipedia eine Lösung. Ich beschreibe einen anderen Algorithmus aus Steven Skienas The Algorithm Design Manual [1]:

1. Finden Sie die kürzesten Wege zwischen jedem Paar von Eckpunkten ungeraden Grades in : .$G$$O(n^3)$
2. Das Finden des besten Satzes kürzester Pfade zum Hinzufügen zu reduziert sich auf das Identifizieren der perfekten Übereinstimmung mit minimalem Gewicht in einem speziellen Graphen . Die Eckpunkte von entsprechen den Eckpunkten ungeraden Grades von , wobei das Gewicht der Kante als die Länge des kürzesten Weges von nach in . Beachten Sie, dass eine Übereinstimmung$G$$G' = (V', E')$$V'$$G'$$G$$(i, j) \in E'$$i$$j$$G$ist ein Satz paarweise nicht benachbarter Kanten. Somit verbindet jede Kante in der Übereinstimmung zwei Scheitelpunkte, und kein Scheitelpunkt ist Teil von zwei Übereinstimmungen (ein übereinstimmender Scheitelpunkt wird mit genau einem anderen Scheitelpunkt abgeglichen). Eine perfekte Übereinstimmung ist eine Übereinstimmung, bei der jeder Scheitelpunkt abgeglichen wurde. Jetzt können Sie für jede erhaltene übereinstimmende Kante die beiden zu scheitelnden Endscheitelpunkte betrachten. Die Einschränkung des "Mindestgewichts" beim Erhalten der Übereinstimmung stellt sicher, dass das Gesamtgewicht jeder Kante in der Übereinstimmung so klein wie möglich ist. Da das Gewicht jeder Kante der Abstand zwischen ihren Endpunkten in$G$Dies ist wiederum die Anzahl der Kanten, die dupliziert werden müssen, wenn die Endpunkte gepaart werden. Diese Bedingung stellt sicher, dass die Gesamtzahl der Kanten-Duplikationen global minimiert wird. Das Erhalten einer solchen Übereinstimmung ist in [2] beschrieben und basiert auf dem Blossom-Algorithmus . Eine effiziente Implementierung wird von Kolmogorov [3] ( Preprint-Kopie ) mit einer Implementierung hier beschrieben . Die Implementierung ist eine Verbesserung gegenüber den Ideen und der Überprüfung, die Cook und Rohe in [4] vorgestellt haben. Dies kann .$O(n^3)$
3. Sobald die Übereinstimmung erhalten ist, wird jeder ungerade Scheitelpunkt mit einem anderen ungeraden Scheitelpunkt gepaart. Dies ist die gewünschte Paarung.

Somit können Sie die optimale "Eulerisierung" im Zeitpolynom (kubisch) in der Anzahl der ungeraden Eckpunkte erhalten. Dies basiert auf einem Artikel von Edmonds und Johnson [2], der das chinesische Postbotenproblem löst.

Verweise:

1. Steven S. Skiena. Das Algorithmus-Design-Handbuch. ISBN: 978-1-84800-069-8 e-ISBN: 978-1-84800-070-4 und DOI: 10.1007 / 978-1-84800-070-4
2. J. Edmonds und E. Johnson. Matching, Euler-Touren und der chinesische Postbote. Mathematical Programming, 5: 88–124, 1973.
3. Vladimir Kolmogorov. Blossom V: Eine neue Implementierung eines Perfect Matching-Algorithmus mit minimalen Kosten. In Mathematical Programming Computation (MPC), Juli 2009, 1 (1): 43-67.
4. W. Cook und A. Rohe. Berechnung perfekter Übereinstimmungen mit minimalem Gewicht. INFORMS Journal on Computing, 11 (2): 138–148, Februar 1999.