date-created: 2024-06-24 10:26:36 date-modified: 2024-07-08 10:26:16

Faktorisierung

anchored to 115.00_graphentheorie_anchor Tags: #graphtheory #computerscience proceeds and is closely tied to 115.10_matching

Overview

Grundlegend wollen wir jetzt eine Aufteilung von Graphen beetrachten, welche in ihrer Idee Ähnlichkeiten zum matching sind / sein kann.

[!Definition] Faktorisierung

Betrachten wir einen Graphen $G=(V,E)$ Dann beschreiben wir mit einem $r$-Faktor folgend:

Was wird mit dem r-Faktor beschrieben? #card

Der $r$-Faktor eines Graphen ist ein $r$-regulärer Untergraph $H(V,E^{\prime })$, wobei hier $E^{\prime }\subseteq E$ (Das heißt wir können eine Teilgraphen finden, welcher genau jedem Knoten (wir müssen alle Knoten einbringen!) $k$-viele Kanten zuweist)

Visuell etwa: Wir können hier erkennen, dass das der $1$-Faktor äquivalent zum Matching ist

Spezifisch ist es perfektes Matching!

Satz (41) | $1$-Faktor unter Bedingung

Für den Satz brauch es vorab eine neue Notation, welche wir beschreiben müssen:

[!Bsp]

Betrachten wir einen Graphen $G=(V,E)$.

Mit $u(G)$ möchten wir jetzt eine neue Notation einführen.

Was gibt sie an? #card

Mit $u(G)$ beschreiben wir die Anzahl von ungeraden Komponenten in $G$ –> also alle Komponenten die eine ungerade Knotenzahl haben!

[!Satz] Satz von Tutte (1947)

Ein $G=(V,E)$ besitzt genau dann einen $1$-Faktor, wenn folgendes gilt:

Was muss gelten, damit er genau einen 1-Faktor aufweist? #card

Die Aussage gilt, wenn folgend: $u(G\setminus A)\le |A\mid ,\forall A\subseteq V$ (also alle Teilmengenh haben weniger ungerade Komponenten, als sie Knoten haben!)

Diesen Satz möchten wir jetzt entsprechend beweisen:

Beweis:

Sei $G=(V,E)$ ein r-regulärer Graph (und somit haben Knoten im Teilgraphen Grad $r$) Sei dann jetzt $u(G\setminus A)\le |A\mid ,\forall A\subseteq V$

Richtung:

$G$ hat einen 1-Faktor $M$. Dann heißt es, dass wir den Graphen in eine Menge von Komponenten ungerader Menge $V$ aufteilen können. $G\setminus A$ zerfällt also in $C_1,C_2,\dots ,$ wobei diese ungeraden Komponenten sind, ferner zerfällt er auch in $D_1,D_2,\dots$, welche gerade Komponenten sind.

Für jede dieser ungeraden Komponenten gilt dann jetzt: $\mid C_i\mid$ ist ungerade und somit muss es eine ante $e\in M$ aus $C_i$ heraus geben zu einem anderen Knoten zu $a_i\in A$ (Bedenke, dass $A$ die Menge ist, die wir entfernt haben) ( denn es gilt ja, dass ). Dadurch folgt ferner, dass alle $a_i$ unterschiedlich sind und somit folgt: $⟹|A\mid \ge m=u(G\setminus A)$

Damit haben wir die eine Richtung

Rückrichtung:

Wir betrachtne die Induktion über die Knotenanzahl $\mid V\mid$:

IA: $\mid V\mid =0$

IS: $\mid V\mid \ge 1$ Sei jetzt etwa: $A=\varnothing$ dann folgt $u(G\setminus \varnothing )\le |\varnothing |=0$ G hat dadurch keine ungeraden Komponenten ! (und somit wissen wir, dass es ein perfektes Matching geben kann)

Sei ferner $A=\{v\}$ dann folgt auch hier: $1:u(G\setminus A)\le |A\mid =1$

Sei dann jetzt $A_0$ die maximal große Menge mit $A_0\subseteq V$ und $u(G\setminus A_0)+|A_0\mid$

Wir wollen drei Eigenschaften zeigen, damit unsere Konstruktion funktioniert / passend ist:

1. Jedes $D_j$ besitzt 1-Faktor ($D_i$ waren gerade Komponenten!)
2. Sei $v\in C_i$, dann hat $C_i\setminus v$ 1-Faktor ( das kann etwa die Kante sein, die zum matching in die Menge $A$ notwendig ist! (Die anderen Knoten matchen u.U. bereits innerhalb der Komponente))
3. Es gibt Kanten $e_1,\dots ,e_m$ wobei $e$ $C_i$ mit $A_0$ verbindet und alle Endknoten aller kanten verschieden sind (Denn sonst könnten wir kein entsprechendes Matching erzeugen! Weil man dann manche Kanten mehrfach nutzen würde, was unsere Eigenschaft verletzt!)

Zeigen wir diese Aussagen jetzt:

1. Sei $S\subseteq V(D_j)$, also $V\subset D_j$ ist die Knotenmenge von $D_j$

Es gilt hier: $u(G\setminus (S\cup A_0))=u(CG\setminus A_0)+u(D_j\setminus S)\le \mid A_0+S\mid =|A_0\mid +|S|$ Und da ferner $u(G\setminus A_0)=|A_0\mid ⟹u(D_j\setminus S)\le |S\mid$ und somit hat $D_j$ gemäß der Induktionsvoraussetzung dann einen $1$-Faktor!

Konzept der Aussag

2. Sei $v\in C_i$, dann hat $C_i\setminus v$ 1-Faktor Wir wollen durch Widerspruch beweisen:

Gemäß der Induktionsvoraussetzung gibt es $S\subseteq V(C_i)\setminus v$ mit $u(C_i\setminus (S\cup v))>|S\mid$ dann hat $C_i\setminus v$ eine gerade Zahl an Knoten

Ferner hat aber auch $u(C_i\setminus (S\cup v))-|S\mid$ ebenfalls eine gerade Anzahl von Knoten ( Was aus der obigen Betrachtung folgt). Es folgt hieraus: $u(C_i\setminus (S\cup v))\ge |S\mid +2$

Wir setzen eine Annahme: $$\begin{aligned} \mid A_{0} + { v } + S \mid & = \mid A_{0}\mid + 1 + \mid S\mid \geq u(G \setminus (A_{0} \cup v \cup S))$ \ & = u ( G \setminus A_{0}) - 1 + u(G \setminus (S \cup v)) \ & \geq \mid A_{0}\mid + 1 + \mid S\mid + 2 = \mid A_{0} \mid + 1 + \mid S\mid \ &\text{ was einen Widerspruch verursacht} \end{aligned}$$

3. Es gibt Kanten $e_1,\dots ,e_m$ wobei $e$ $C_i$ mit $A_0$ verbindet und alle Endknoten aller kanten verschieden sind

Sei $\hat{G}=(\hat{V},\hat{E})$ der bipartite Graph mit $\hat{V}=\{c_1,c_2,\dots \}\cup \{a_i\mid a_i\in A_0\}$ (Also wir teilen den Graphen in zwei Partitionen, wobei wir die ungeraden Komponenten $C_1,C_2,\dots$ in eine Partition - wichtig die Komponenten werden als ein Knoten zusammengefasst, wir brauchen die Aspekte innerhalb dieser nicht zwingend! - und $A_0$ als die andere Komponente (wir zählen sie ab, weil wir jeden Knoten in dieser Menge betrachten wollen / werden) )

Für die kante gilt dann: $\hat{E}$: es Kanten zwischen $C_i$ und $a_j\in A_0$ wenn es in $G$ Kanten von $C_i$ zu $a_j$ gibt.

Es ist zu zeigen, dass es ein perfektes Matching $\hat{M}$ in $\hat{G}$ gibt, wobei $\mid \hat{M}\mid =m$

Wir können damit den Satz von Hall anwenden: Satz (39) Satz von Hall (bipartite Graphen)

Sei hierbei $X\subseteq C=\{C_1,\dots ,C_m\}$( also die Kombination aller ungeraden Komponenten) und ferner $R(X)\subseteq A_0$ die Menge der “mit mindestens einer Kante aus $X$ verbundenen Knoten aus $A_0$” (also eine solche Teilmenge, die immer mit $A_0$ verbunden ist)

Damit hat dann auch: $G\setminus R(X)$ die Komponente $X$ ( weil wir sie ja so passend konstruiert haben) Damit folgt dann: $$\begin{array}{rl}⟹\mid X\mid \le & u(G\setminus R(x))\\ \text{ und da }& u(G\setminus R(x))\le \mid R(X)\mid \text{ folgt}\\ & ⟹\mid X\mid \le \mid R(X)\mid \forall X\subseteq C\end{array}$$

(Also wir können hier belegen, dass die Kanten, die die Komponenten verbindet, garantiert unterschiedlich sind, weil wir durch Konstruktion eines bipartiten Graphs ein perfektes Matching finden können –> Und das hilft uns genau das zu beweisen!)

Satz (42) | Matchingzahl

[!Definition]

Unter Betrachtung des vorherigen Satzes können wir jetzt eine Aussage über die Matchingzahl eines Graphen $G$, also $m(G)$ geben;

Wenn wir wissen, dass es $n$ Knoten gibt, wie können wir die Matchingzahl bestimmen? #card

Es lässt sich bei $n$ Knoten für den Graphen $G=(V,E)$ folgend die Matchingzahl bestimmen: $$m(G)=\frac{1}{2}(n-\underset{A}{\max }(u(G\setminus A)-\mid A\mid ))$$ (Das heißt: wir iterieren über alle möglichen A und suchen das Maxima dabei!)

Satz (43) | Aussage: 3-regulärer $\wedge$ brückenloser Graph

[!Req] Satz | Peterson 1891

Ein zusammenhängender $3$-regulärer brückenloser ( ohe Schnittkante!) graph besitzt stets einen 1-Faktor

wie können wir das beweisen? #card

Sei $S\subseteq V$ und ein $C$ eine ungerade Komponente von $G\setminus S$ Wir wissen, dass $G$ 3-regulär ist, das heißt also dass die Summe aller Knotengrade von allen $v\in C$ ungerade ( etwa $3\cdot 3=9$ lol) ist. Nur ein gerader Anteil dieser Summe kommt von kanten in $C$

Daraus folgt dann $⟹$ $G$ hat ungerade Anzahl an kanten zwischen $S\leftrightarrow C$

Da $G$ keine Brücke hat, gibt es $\ge 3$ solche Kanten. (unter dieser Betrachtung können wir dann passend argumentieren / aufteilen)

Damit ist die Gesamtanzahl der kanten zwischen $G$ und $G\setminus S$ $\ge 3\cdot u(G\setminus S)$ und ferner $\le 3\cdot |S\mid$ denn $G$ ist $3$-regulär!

damit folgt also auch $\mid u(G\setminus S)|\le |S\mid$

Er hat dann einen 1-Faktor

Satz (44) | 2-Faktor für jeden geraden, regulären Graph $>0$

[!Definition] Satz(44) | Peterson (1891)

Es gilt: Jeder regulärer Graph geraden Grades $>0$ hat einen $2$-Faktor ( bzw jeder regulärer Graph ist dadurch 2-zsh und daraus folgen all diese Aussagen)

Wie können wir das beweisen? Was gilt für einen solchen Graphen? #card

Sei $G=(V,E)$ ein $2k$ regulärer Graph, welcher zusammenhängend ist. –> $G$ enthält also einen Eulerkreis, da er gerade Kanten-Anzahlen pro Knoten hat! Also es gibt einen Pfad: $v_0,e_0{v}_1{e}_1\dots e_l{v}_l=v_0$

Ersetze jeden Konten $v$ durch Knotenpaar $(\overline{v},v^{+})$ und jede Kante $e_i=v_i{v}_{i+1}$ durch $v_i^{+},v_{i+1}^{-}$

Der entstandene Graph ist dann bipartite und $k-$regulär

er hat hierbei ein perfektes Matching mit $1$-Faktor Identifiziere in jedem 1- Fakto jedes Knotenpaar $(v^{-},v^{+})$ wieder zu $v$ (also wir mergen sie wieder)

und anschließend auch einen 2-Faktor in $G$

[!Bsp] Beispiel für 2-Faktor-Zerlegung

Unter Betrachtung des obigen Satzes können wir jetzt beispielhaft einen solchen 2-Faktor bestimmen.

Wir teilen die Knoten in die $v^{+}$ und $v^{-}$ Kompartments auf.

Nun werden wir in diesem neuen Graphen (der bipartite ist!) ein perfektes Matching suchen / aufbauen.

Anschließend werden wir nun die entsprechenden Komponenten nehmen und wieder zum Ursprungsgraphen zusammenschließen.

Anschliesend übernehmen wir die Kanten die wir zuvor für das Matching ausgewählt haben und bilden damit den 2-Faktor