Starke Orientierung - Strong orientation

In der Graphentheorie ist eine starke Orientierung eines ungerichteten Graphen die Zuweisung einer Richtung an jede Kante (eine Orientierung ), die ihn zu einem stark zusammenhängenden Graphen macht .

Bei der Gestaltung von Einbahnstraßennetzen wurden starke Orientierungen angewendet. Nach dem Satz von Robbins sind die Graphen mit starken Orientierungen genau die brückenlosen Graphen . Eulersche Orientierungen und ausgewogene Orientierungen liefern wichtige Spezialfälle starker Orientierungen; wiederum können starke Orientierungen auf vollständig zyklische Orientierungen von nicht zusammenhängenden Graphen verallgemeinert werden. Der Satz starker Orientierungen eines Graphen bildet einen Teilwürfel , wobei sich benachbarte Orientierungen in dieser Struktur in der Orientierung einer einzelnen Kante unterscheiden. Es ist möglich, eine einzelne Orientierung in linearer Zeit zu finden, aber es ist #P-vollständig , die Anzahl der starken Orientierungen eines gegebenen Graphen zu zählen.

Antrag auf Verkehrskontrolle

Robbins (1939) führt das Problem der starken Orientierung mit einer Geschichte über eine Stadt ein, deren Straßen und Kreuzungen durch den gegebenen Graphen G dargestellt werden . Laut Robbins 'Geschichte wollen die Bewohner der Stadt jeden Straßenabschnitt während der Wochentage reparieren können, während sie dennoch jeden Teil der Stadt von jedem anderen Teil aus erreichen können, indem die verbleibenden Straßen als Einbahnstraßen verwendet werden. An den Wochenenden sind alle Straßen geöffnet, aber wegen des starken Verkehrsaufkommens wollen sie alle Straßen in Einbahnstraßen umwandeln und wieder alle Stadtteile von jedem anderen Stadtteil erreichen lassen. Das Theorem von Robbins besagt, dass ein Straßensystem für Reparaturen an Wochentagen genau dann geeignet ist, wenn es für den Umbau in ein Einbahnstraßensystem am Wochenende geeignet ist. Aus diesem Grund wird sein Ergebnis manchmal als Einbahnstraßensatz bezeichnet .

Im Anschluss an die Arbeit von Robbins modelliert eine Reihe von Arbeiten von Roberts und Xu das Problem der Umwandlung eines Rasters von Einbahnstraßen in Einbahnstraßen genauer und untersucht die Auswirkungen dieser Umwandlung auf die Abstände zwischen Punktpaaren innerhalb des Rasters. Wie sie zeigten, ist die traditionelle Einbahnstraße, bei der parallele Straßen ihre Richtung wechseln, nicht optimal, um die paarweisen Abstände so klein wie möglich zu halten. Zu den verbesserten Orientierungen, die sie gefunden haben, gehören jedoch Punkte, an denen der Verkehr von zwei Einbahnstraßen frontal aufeinandertrifft, was als Fehler in ihren Lösungen angesehen werden kann.

Ähnliche Orientierungsarten

Wenn ein ungerichteter Graph eine Euler-Tour hat , kann eine Eulersche Orientierung des Graphen (eine Orientierung, bei der jeder Knoten einen Ingrad gleich seinem Außengrad hat) gefunden werden, indem die Kanten konsistent um die Tour herum ausgerichtet werden. Diese Orientierungen sind automatisch starke Orientierungen.

Ein Satz von Nash-Williams ( 1960 , 1969 ) besagt, dass jeder ungerichtete Graph G eine ausgewogene Orientierung hat . Dies ist eine Orientierung mit der Eigenschaft, dass für jedes Knotenpaar u und v in G die Anzahl der paarweisen kantendisjunkten gerichteten Pfade von u nach v im resultierenden gerichteten Graphen mindestens ist , wobei k die maximale Anzahl von Pfaden in einer Menge kantendisjunkter ungerichteter Pfade von u nach v . Die Orientierungen von Nash-Williams haben auch die Eigenschaft, dass sie den Eulerschen Orientierungen so nahe wie möglich kommen: An jedem Scheitelpunkt liegen der In- und der Außengrad ineinander. Die Existenz ausgewogener Orientierungen zusammen mit dem Satz von Menger impliziert sofort den Satz von Robbins: Nach dem Satz von Menger hat ein zweikantenverbundener Graph mindestens zwei kantendisjunkte Pfade zwischen jedem Knotenpaar, woraus folgt, dass any ausgewogene Ausrichtung muss stark verbunden sein. Allgemeiner ausgedrückt bedeutet dieses Ergebnis , dass jede 2 k -Kante geschalteter kann ungerichteten Graphen zur Bildung einer ausgerichtet sein k -Kante geschalteten gerichteten Graphen.

Eine vollständig zyklische Orientierung eines Graphen G ist eine Orientierung, bei der jede Kante zu einem gerichteten Kreis gehört. Für zusammenhängende Graphen ist dies dasselbe wie eine starke Orientierung, aber für unzusammenhängende Graphen können auch vollständig zyklische Orientierungen definiert werden, und sind die Orientierungen, in denen jede zusammenhängende Komponente von G stark zusammenhängend wird. Der Satz von Robbins kann so umformuliert werden, dass ein Graph genau dann eine vollständig zyklische Orientierung hat, wenn er keine Brücke hat. Völlig zyklische Orientierungen sind dual zu acyclischen Orientierungen (Orientierungen , die drehen G in einen gerichteten azyklischen Graphen ) in dem Sinne , dass, wenn G a planar Graph und Orientierungen von G an Orientierungen der transferierten planaren Dual Graph von G durch jede Kante Dreh 90 Grad im Uhrzeigersinn, dann entspricht eine total zyklische Orientierung von G auf diese Weise einer azyklischen Orientierung des Dualgraphen und umgekehrt. Die Anzahl der verschiedenen total zyklischen Orientierungen eines beliebigen Graphen G ist T G (0,2), wobei T G das Tutte-Polynom des Graphen ist, und die Anzahl der azyklischen Orientierungen ist dual T G (2,0) . Folglich impliziert der Satz von Robbins, dass das Tutte-Polynom genau dann eine Wurzel im Punkt (0,2) hat, wenn der Graph G eine Brücke hat.

Wenn eine starke Orientierung die Eigenschaft hat, dass alle gerichteten Zyklen durch eine einzelne Kante st gehen (gleichermaßen, wenn das Umkehren der Orientierung einer Kante eine azyklische Orientierung erzeugt ), dann ist die durch Umkehren von st gebildete azyklische Orientierung eine bipolare Orientierung . Jede bipolare Orientierung ist auf diese Weise mit einer starken Orientierung verbunden.

Grafiken umkehren

Wenn G ein mit drei Kanten verbundener Graph ist und X und Y beliebige zwei unterschiedliche starke Orientierungen von G sind , dann ist es möglich, X in Y umzuwandeln, indem die Orientierung einer einzelnen Kante gleichzeitig geändert wird, wobei bei jedem Schritt die Eigenschaft, dass die Orientierung stark ist. Daher bildet der Flipgraph, dessen Ecken den starken Orientierungen von G entsprechen und dessen Kanten Paaren von starken Orientierungen entsprechen, die sich in Richtung einer einzelnen Kante unterscheiden, einen Teilwürfel .

Algorithmen und Komplexität

Eine starke Orientierung eines gegebenen brückenlosen ungerichteten Graphen kann in linearer Zeit gefunden werden, indem man eine Tiefensuche des Graphen durchführt, alle Kanten im Tiefensuchbaum weg von der Baumwurzel ausrichtet und alle verbleibenden Kanten ausrichtet (was notwendigerweise einen Vorfahren und einen Nachkommen im Tiefensuchbaum verbinden) vom Nachkommen zum Vorfahren. Wenn ein ungerichteter Graph G mit Brücken gegeben ist, zusammen mit einer Liste von geordneten Knotenpaaren, die durch gerichtete Pfade verbunden werden müssen, ist es in polynomieller Zeit möglich , eine Orientierung von G zu finden , die alle gegebenen Paare verbindet, wenn eine solche Orientierung existiert. Das gleiche Problem ist jedoch NP-vollständig, wenn die Eingabe ein gemischter Graph sein kann.

Es ist #P-vollständig , die Anzahl der starken Orientierungen eines gegebenen Graphen G zu zählen , auch wenn G planar und bipartit ist . Für dichte Graphen (genauer Graphen, in denen jeder Scheitelpunkt eine lineare Anzahl von Nachbarn hat) kann die Anzahl der starken Orientierungen jedoch durch ein vollständig polynomialzeit-randomisiertes Näherungsschema geschätzt werden . Das Problem des Zählens starker Orientierungen kann auch für Graphen mit beschränkter Baumbreite in polynomieller Zeit exakt gelöst werden .

Anmerkungen

Verweise