cards-deck: 100-199_university::111-120_theoretic_cs::115_graphentheorie

Ohrenzerlegung

anchored to 115.00_graphentheorie_anchor Tags: #graphtheory #Study #theoretical

Motivation

(auch gute Musik genannt?)

Die Ohrenzerlegung ist relevant ! (dennoch hat es niemand im Graphen-Team der Uni gekannt, bis sie es beschrieben hat).

Mit der Ohrenzerlegung meinen wir das Aufteilen eines Graphen in verschiedene Ketten von Knoten und Kanten, sodass es einen Kreis gibt und weiterhin diverse Endpunkte auftreten, welche in ihrer Struktur immer Endpunkte in anderen Ohren haben. Damit bilden wir eine Art Geflecht, was sich selbst nicht looped - außer beim ersten Kreis.

Wir können ferner in zwei verschiedene Varianten teilen:

Offene Ohrenzerlegung

[!Definition] Ohrenzerlegung

Betrachten wir einen Graphen $G=(V,E)$, dann möchten wir folgend eine Ohrenzerlegung definieren.

Wie können wir entsprechend eine Ohrenzerlegung aufteilen, wie ist das Konzept? Was macht die offene Ohrenzerlegung aus? #card

Eine Ohrenzerlegung eines Graphen $G=(V,E)$ ist eine Folge $(P_0,P_1,\dots ,P_k)$ von Teilgraphen (Ohren) von $G$, die $E$ so disjunkt partitionieren, dass folgende Eigenschaften gelten müssen:

1. $P_0$ ist ein Kreis (es gibt in der ganzen Struktur nur einen einzigen)
2. Jedes $P_i,1\le i\le k$ ist ein Pfad der $P_0\cup \cdots \cup P_{i-1}$ mit seinen Endpunkten schneidet (also sie fangen immer in einen beliebigen Punkt an, und enden in einem beliebigen, jedoch Bauen sie an den anderen Aufteilungen des Graphen an. (Wichtiger noch: sie bilden keinen Kreis))

Visuell könnte man folgenden Graphen etwa so darstellen ^1720364455252

Hieraus können wir jetzt bestimmte Eigenschaften folgern:

Lemma (28) | Ohrenzerlegung, wenn 2-zsh

[!Satz] Folgerung für Ohrenzerlegung

Betrachten wir einen Graph $G=(V,E)$, welcher eine Ohrenzerlegung hat. Sofern diese Aufteilung aufweist, ist der Graph auch 2-zusammenhängend (Knoten abhängige Betrachtung)!

weswegen folgt diese Aussage? #card

Wenn wir die Zerlegung aufbauen und hierbei einen Kreis bilden, dann ist dieser auf jeden Fall schon 2-zsh (das haben wir zuvor schon gezeigt und wissen wir). Ferner können wir anschließend immer mit H-Wegen diesen Kreis erweitern, also neue Pfade mit Kanten/Knoten bilden, die in dem bekannten Graphen anfangen und enden. –> Wir haben gezeigt, dass dadurch dann der Graph weiterhin 2-zsh ist. Siehe etwa H-Wege

Wir resultieren jetzt also mit einem entsprechenden Graphen! ^1720364455258

Es kann aber auch noch eine andere Definition von Ohrenzerlegungen betrachtet und definiert werden:

Geschlossene Ohrenzerlegung

[!Definition] Geschlossene Ohrenzerlegung

Betrachten wir wieder einen Graphen $G=(V,E)$ und konstruieren jetzt eine geschlossene Ohrenzerlegung auf diesen.

wie beschreiben wir die geschlossene Ohrenzerlegung? #card

Eine geschlossene Ohrenzerlegung eines Graphen $G=(V,E)$ ist eine Folge von Teilgraphen (Ohren) $P_0,P_1,\dots ,P_k$ von G, die wieder $E$ so disjunkt partitionieren, dass folgende Eigenschaften gelten:

1. $P_0$ ist ein Kreis!
2. Jedes $P_i,\le i\le k$ ist nun entweder ein Pfad, der $P_0\cup \cdots \cup P_{i-1}$ mit seinen Endpunkten schneidet oder ein Kreis der $P_0\cup \cdots \cup P_{i-1}$ in genau einem Knoten schneidet! Wir erlauben jetzt also mehr Kreise setzen dabei aber voraus, dass diese, wenn sie existieren, immer nur eine einzige Verbindung zu einer anderen Partition hat ( also in einem Kreis maximal jede Partition einmal auftritt!). Visuell also etwa so:

Wir sehen hier, dass diese Definition sich auf die Kantenzusammenhänge bezieht! ^1720364455262

Es folgt auch hieraus ein Lemma:

[!Lemma] Folgerung für geschlossene Ohrenzerlegung

Betrachten wir also einen Graphen $G=(V,E)$, welcher eine geschlossene Ohrenzerlegung aufweist.

Es folgt jetzt: hat er eine geschlossene Ohrenzerlegung, dann ist er auch 2-kantenzusammenhängend!

weswegen folgt diese Aussage? #card

Wir können diese Aussage durch Betrachtung des 2-Kantenzusammenhangs beweisen:

Ist der Graph 2-kantenzsh, dann heißt, das, dass man definitiv 2 Kanten löschen muss, um den Graph trennen zu können. ( das gilt für jeden Knoten). Ferner kann man dann also einen Trenner konzipieren, welcher zwei Kanten aufweist, sodass der Graph dann zerfällt. –> damit hat also auch jeder Knoten mindestens $deg(v)=2$ und somit ist er 2-zsh. Daraus kann man dann mindestens einen Kreis bilden. zund dann mit H-Wegen erweitern, wodurch die Eigenschaft nicht verletzt wird.

Wenn er bereits eine geschlossene Ohrenzerlegung hat. Dann hat jeder Knoten eine Kante, die entweder in dem Kreis (in der Partition) oder der Partition enthalten ist. Ferner ist die andere Kante dann teil einer anderen Partition, wodurch die Verbindung geschaffen wird, dass man mindestens 2 Kanten entfernen muss, um den Graphen in seine Partitionen zu teilen. ^1720364455266

Berechnung einer Ohrenzerlegung

Wir wollen jetzt algorithmisch zeigen und herausfinden, ob man für einen Graphen eine Ohrenzerlegung bauen kann oder nicht.

[!Definition] Algorithmus zur Bestimmung Ohrenzerlegung

Der Algorithmus gibt eine Ohrenzerlegung an oder sagt, ob der Graph nicht 2-zusammenhängend ist. Sei hier nun ein Graph $G=(V,E)$ gegeben, wobei $\mid V\mid \ge 3$ ist. Wir wollen jetzt ferner den Algorithmus durchlaufenz;

wie ist er aufgebaut, wozu brauchen wir den DFS-Baum? Wann ist keine Zerlegung möglich? #card

• Wir teilen $G$ in Ketten auf. Eine Kette kann hierbei ein Pfad oder ein Kreis sein
• Wir starten weiter mit einem DFS (DFS) um dann zu prüfen, ob der Graph zusammenhängend ist. Und um den DFS-Baum zu erhalten! (Vorwärts/Rückwärts-Kanten etc.) Damit ist die Initiale Konstruktion abgeschlossen.

Jetzt:

1. wir richten vom DFS-Baum alle Baumkanten zur Wurzelhin und alle Rückwärtskanten von der Wurzel weg. (Jede Rückwärtskante $e$ liegt in genau einem gerichteten Kreis $C(e)$)
2. Wir beschreiben mit DFI jetzt die DFS-Nummerierung
3. Wir markieren alle Knoten als unbesucht und laufen dann jeden Knoten mit seiner aufsteigenden DFI
4. Für jede Rückwärtskante $e$, die in $v$ startet, durchlaufen wir ihren Kreis $C(e)$
5. Wir beginnen bei $v$ und stoppen dann beim ersten Knoten, den wir schon besucht haben. –> Dabei werden alle besuchten, auf besucht gesetzt.
6. Dadurch wird mit jeder Iteration ein Pfad / Kreis gebildet, den wir dann beliebige benennen.
7. Es wird somit eine Aufteilung in Komponente gebildet!

Folgendes Beispiel können wir dann betrachten: Original-Graph: ( rot ist Vorwärts-Kante, blaue Rückwärts)

gebildeter DFS-Baum: abgeschlossene Aufteilung:

^1720364455269

Dieser Algorithmus kann folgende Eigenschaften zeigenz:

• 2 Knoten zusammenhang + mit offenen Ohren
• 2 Kantenzusammenhang + mit geschlossenen Ohren
• 2 Zusammenhängenden

[!Important] Menge von Ketten | für Ohrenzerlegung

Wie viele Ketten gibt es in einem Graphen (maximal?) #card

$$\mid E\mid -\mid V\mid +1$$ -> da jede Rückwärtskante eine Kette erstellt (und wir sonst nicht die Möglichkeit haben) ^1720364455271