date-created: 2024-05-13 01:14:21 date-modified: 2024-07-04 07:00:56

Graphen | Kontraktion

anchored to 115.00_graphentheorie_anchor

Overview

Durch die Kontraktion werdne uns ein paar Möglichkeiten zur Konstruktion und Benennung (von Eigenschaften) bei Graphen ermöglicht. Ferner können wir so auch den Satz von Kuratowski unter Anwendung der Kontraktion und bestimmten Unterformen von geformten Graphen konstruieren.

Zusammenhang

Wir möchten vor der Definition der Kontraktion erst das Konzept von Zusammenhängen betrachten und definieren. Betrachten wir einen Graphen $G=(V,E)$.

[!Definition] Ablauf Entfernen eines Knoten

Wenn wir jetzt einen Knoten $v\in V$ entfernen wollen wie gehen wir vor, geht es mit Mengen von Knoten? #card

Dann müssen wir den Knoten selbst und alle seine inzidenten Kanten entfernen -> Das sind ferner alle Kanten, die von oder zu diesem Knoten verlaufen.

Diese Operation gilt auch für Mengen von Knoten $V^{\prime }\subset V$: Auch hier entfernen wir nun alle Knoten dieser Teilmenge und damit auch alle Kanten die jeweils inzident zu den Knoten sind. Also selbe Idee aber halt auf mehr angewandt.

Als Beispiel betrachten wir etwa folgenden Graphen:

Wir können hier jetzt etwa den Knoten in der mitte Rechts entfernen und resultieren mit folgendem Graphen:

Zusammenhangszahl

Betrachten wir einen Graphen und möchten ihn so aufteilen dass er aus zwei Graphen besteht, dann können wir die passenden Knoten $v$ suchen, sodass dann das Entfernen dieser dabei beitraét.

[!Definition] Zusammenhangszahl

Das Finden und Entfernen von bestimmten Knoten eines Graphen $G=(V,E)$ und $V^{\prime }\subset V$ kann mit der Zsuammenhangszahl beschrieben werden. was sagt sie aus? #card

Die Zusammenhangszahl gibt uns die kleinste Zahl von Knoten an, die bei der Entfernung den Graphen entsprechend aufteilt (in einen Restgraphen). Wenn jetzt $K(G)\ge n$ ist, dann nennen wir $G$ $n-$fach zusammenhängend.

Als Zusatz: Für die vollständigen Graphen $K_n$ gilt hier $$K(K_n)=n-1$$ Für folgenden Graphen wäre hier etwa $K(G)=1$: wobei wir hier drei verschiedene Knoten betrachten können, die beim entfernen zwei Teilgraphen generiert / verursacht.

[!Important] trennende Knotenmengen Wir können die Knotenmenge $V^{\prime }$ von einem Graphen $G=(V,E)$ als trennende Knotenmenge beschreiben, wenn gilt, dass $G\setminus V^{\prime }$ (Also Der Graph mit den Knoten entfernt) folglich unzusammenhängend ist –> wir also zwei disjunkte Mengen erhalten haben.

A-B-Wege

Eine weitere Betrachtung, die Wege zwischen verschiedenen Mengen in verschiedenen Mengen beschreibt, benötigen wir, um anschließend den Satz (20) Satz von Menger beweisen und besser verstehen zu können.

Hierbei wollen wir jetzt A-B-Wege definieren.

[!Definition] A-B Weg Sei $G=(V,E)$ ein Graph und zwei Teilmengen von den Knoten $A,B\subset V$. wie können wir jetzt einen A-B-Weg beschreiben? wann sind sie kreuzungsfrei oder disjunk? #card

Wir beschreiben einen Weg $\pi$ als einen A-B-Weg des Graphen, wenn gilt, das $(x_0,x_1,\dots ,x_k)$ mit $A\cap V(\pi )=\{x_0\}$ (also der Anfang) und $B\cap V(\pi )=\{x_k\}$ (also das Ende) ist, wobei $V(\pi )$ die Knotenmenge von $\pi$ beschreibt. Das heißt also, wir haben zwei disjunkte Mengen von Knoten und wollen jetzt Verbindungswege zwischen diesen schaffen / finden. Kreuzungsfrei und disjunkt nennen wir jetzt zwei Wege ( oder mehrere), wenn keiner der inneren Knoten (also abgesehen vom start und ende) in einem Anderen enthalten ist. Das heißt ferner, dass zwei a-b-Wege kreuzungsfrei sind, wenn sie bis auf die Start/Endpunkte $a,b$ disjunkt sind!

Folgend kann man das auch an einem Beispiel noch gut zeigen: Färben wir dabei zwei Mengen $A,B$ ein: Wir können jetzt einige Verbindungen ziehen, werden aber auch Überschneidungen finden, sodass also kreuzende Wege auftreten:

Kontraktion

Wenn wir jetzt einen Graphen betrachten $G=(V,E)$ dann können wir ihn ähnlich, wie bei der Unterteilung zusammenfassen bzw. “seine Darstellung” stauchen, sodass man ihn anders darstellen kann.

[!Definition] Kontraktion was ist mit Kontraktion im Kontext von einer Kante $e=(u,v)$ in einem Graphen gemeint? #card

Mit der Kontraktion beschreiben wir den Vorgang, wenn wir in einem Graphen $G$ eine bestimmte Kante “zusammenziehen” bzw. die Knoten $u,v$verschmelzen un dabei die Kante $e=(u,v)$ terminieren. Dabei erhalten wir einen Knoten $v_e$ welcher eben die Verbindungen symbolisiert / darstellt.

Grafisch vielleicht einfacher erklärt:

Als logische Konsequenz daraus:

• die Nachbarn sind dann alle Knoten, die zuvor benachbarte von u und v waren.
• Mehrfachkanten werden in dem Kontext auch verschmolzen

Man kann hierfür jetzt einen “neuen Graphen” beschreiben.

Kontraktion mit $G/e$: Betrachten wir also einen Graphen $G=(V,E)$ und weiter eine Kante $e=(u,v)$, die in u startet und v endet.

Wir beschreiben jetzt mit $G/e$ den Graphen “kontrahiert e”, also bei welchem wir die Kontraktion für $e$ durchgeführt haben.

Weiterführende Betrachtung |

Das Konzept der Kontraktion ist in diversen Bereichen relevant und anwendbar.

Etwa bei:

• 115.06_Eulers_Formel_Graphen, wo man einen entsprechenden Minor finden kann, der einem $K_5,K_{3,3}$ entspricht, um so die Planarität zu prüfen.
• Die Betrachtung der Zusammenhangszahl kann man auch für Kanten machen:
• Unter Betrachtung der Zusammenhangszahl kann man schauen, wie man Graphen entsprechend aufteilen kann / oder nicht. Dafür ist der Term der $k-$zusammenhängenden Graphen relevant!