Kantenkontraktion

Vertrag der Kante zwischen den angegebenen Scheitelpunkten, was zu Graphen führt G / {uv}.

Im Graphentheorie, ein Kantenkontraktion ist ein Betrieb Das entfernt eine Kante von a Graph während gleichzeitig die beiden verschmelzen Eckpunkte dass es zuvor beigetreten ist. Randkontraktion ist eine grundlegende Operation in der Theorie von Graph Minderjährige. Scheitelpunktidentifikation ist eine weniger restriktive Form dieser Operation.

Definition

Das Kantenkontraktion Der Betrieb erfolgt relativ zu einer bestimmten Kante, . Die Kante wird entfernt und seine beiden einfallenden Scheitelpunkte, und , werden zu einem neuen Scheitelpunkt verschmolzen , wo die Kanten zu Ende gehen jeweils entspricht einer Kante, die bei beiden vorkommt oder . Allgemeiner kann der Betrieb an einer Reihe von Kanten durchgeführt werden, indem jede Kante (in beliebiger Reihenfolge) zusammengearbeitet wird.[1]

Die resultierende induzierte Grafik wird manchmal als geschrieben als . (Kontrast dies mit , was bedeutet, die Kante zu entfernen .))

Vertrag einer Kante, ohne mehrere Kanten zu erstellen.

Wie unten definiert, kann ein Edgekontraktionsvorgang zu einem Diagramm mit führen Mehrere Kanten Auch wenn die Originalgrafik a war Einfaches Diagramm.[2] Einige Autoren jedoch[3] Die Erstellung mehrerer Kanten nicht zulassen, so dass Kantenkontraktionen, die an einfachen Diagrammen durchgeführt werden, immer einfache Diagramme erzeugen.

Formale Definition

Lassen eine Grafik sein (oder gerichteter Graph) mit einer Kante enthalten mit . Lassen Sei eine Funktion, die jeden Scheitelpunkt in für sich selbst und ansonsten einen neuen Scheitelpunkt . Die Kontraktion von führt zu einer neuen Grafik , wo , und für jeden , ist auf eine Kante zu sehen wenn und nur wenn die entsprechende Kante, ist ein Zwischenfall an in .

Scheitelpunktidentifikation

Scheitelpunktidentifikation (manchmal genannt Scheitelpunktkontraktion) entfernt die Einschränkung, dass die Kontraktion Muss über Scheitelpunkte auftreten, die eine einfallende Kante teilen. (Daher ist die Kantenkontraktion ein spezieller Fall der Vertex -Identifizierung.) Die Operation kann an jedem Paar (oder Teilmengen) von Scheitelpunkten in der Grafik auftreten. Kanten zwischen zwei Vertrag Scheitelpunkte werden manchmal entfernt. Wenn und sind Scheitelpunkte verschiedener Komponenten von Dann können wir ein neues Diagramm erstellen durch Identifizierung und in Als neuer Scheitelpunkt in .[4] Allgemeiner gegeben, gegeben a Trennwand Von dem Scheitelpunktsatz kann man Scheitelpunkte in der Partition identifizieren; Die resultierende Grafik ist als a bekannt Quotientengrafik.

Scheitelpunktspalten

Scheitelpunktspalten, was der gleiche wie die Vertex -Spaltung ist, bedeutet, dass ein Scheitelpunkt in zwei geteilt wird, wobei diese beiden neuen Scheitelpunkte an die Eckpunkte nebeneinander liegen, an die der ursprüngliche Scheitelpunkt angrenzend war. Dies ist ein umgekehrter Betrieb der Vertex -Identifizierung, obwohl im Allgemeinen für die Vertex -Identifizierung benachbarte Scheitelpunkte der beiden identifizierten Scheitelpunkte nicht derselbe Satz sind.

Pfadkontraktion

Pfadkontraktion tritt an den Kanten in a auf Weg das Vertrag um eine einzelne Kante zwischen den Endpunkten des Pfades zu bilden. Kanten, die Scheitelpunkten entlang des Pfades erfassen, werden entweder beseitigt oder willkürlich (oder systematisch) mit einem der Endpunkte verbunden.

Verdrehen

Betrachten Sie zwei disjunkte Diagramme und , wo Enthält Eckpunkte und und Enthält Eckpunkte und . Angenommen, wir können die Grafik erhalten Durch die Identifizierung der Eckpunkte von und von als Scheitelpunkt von und Identifizierung der Eckpunkte von und von als Scheitelpunkt von . In einem verdrehen von in Bezug auf den Scheitelpunktsatz , wir identifizieren stattdessen, mit und mit .[5]

Anwendungen

Sowohl Edge- als auch Scheitelpunkt -Kontraktionstechniken sind wertvoll in Beweis durch Induktion Bei der Anzahl der Eckpunkte oder Kanten in einem Diagramm, in dem angenommen werden kann, dass eine Eigenschaft für alle kleineren Graphen gilt und dies verwendet werden kann, um die Eigenschaft für das größere Diagramm zu beweisen.

Kantenkontraktion wird in der rekursiven Formel für die Anzahl von verwendet Bäume überspannen eines willkürlichen verbundenes Diagramm,[6] und in der Rezidivformel für die chromatisches Polynom einer einfachen Grafik.[7]

Kontraktionen sind auch in Strukturen nützlich, bei denen wir ein Diagramm vereinfachen möchten, indem Sie Scheitelpunkte identifizieren, die im Wesentlichen gleichwertige Entitäten darstellen. Eines der häufigsten Beispiele ist die Verringerung eines allgemeinen gerichteter Graph zu einem Acyclic Cancted Graph durch Vertrag aller Scheitelpunkte in jedem stark verbundene Komponente. Wenn die durch die Grafik beschriebene Beziehung lautet transitivEs gehen keine Informationen verloren, solange wir jeden Scheitelpunkt mit dem Satz von Beschriftungen der Scheitelpunkte kennzeichnen, die als Bildung vertraglich sind.

Ein weiteres Beispiel ist das Koalescing in Global Graph Malvorlagenregister Allokation, wo Scheitelpunkte beauftragt werden (wo es sicher ist), um Bewegungsvorgänge zwischen verschiedenen Variablen zu beseitigen.

Die Edgekontraktion wird in 3D-Modellierungspaketen (entweder manuell oder über eine Funktion der Modellierungssoftware) verwendet, um die Scheitelpunktzählung konsistent zu reduzieren, was bei der Erstellung von Modellen mit niedrigem Polygon unterstützt wird.

Siehe auch

Anmerkungen

  1. ^ Gross & Yellen 1998, p. 264
  2. ^ Ebenfalls, Schleifen kann entstehen, wenn das Diagramm mit mehreren Kanten begann oder selbst wenn die Grafik einfach aus der wiederholten Anwendung der Kantenkontraktion war.
  3. ^ Rosen 2011, p. 664
  4. ^ Oxley 1992, S. 147-148
  5. ^ Oxley 1992, p. 148
  6. ^ Gross & Yellen 1998, p. 264
  7. ^ West 2001, p. 221

Verweise

  • Gross, Jonathan; Yellen, Jay (1998), Graphentheorie und ihre Anwendungen, CRC Press, ISBN 0-8493-3982-0
  • Oxley, James (1992), Matroid -Theorie, Oxford University Press
  • Rosen, Kenneth (2011), Diskrete Mathematik und ihre Anwendungen (7. Aufl.), McGraw-Hill, ISBN 9780073383095
  • West, Douglas B. (2001), Einführung in die Graphentheorie (2. Aufl.), Prentice-Hall, ISBN 0-13-014400-2

Externe Links