date-created: 2024-04-15 10:27:53 date-modified: 2024-07-04 06:52:01

Grundlagen der Graphentheorie:

anchored to 115.00_graphentheorie_anchor

Notationen werden hier, wie bei 111.13_Graphen_basics mit $G = (V, E)$ bezeichnet, wobei wir mit $V$ die Menge aller Knoten beschreiben, während $E$ die Menge aller edges -> Kanten darzustellen.

$E \subset (\frac{v}{2}) = {(u, v) \subseteq V (G)}$ –> wir beschreiben hier die Menge von allen Kanten, die von V abgehen und somit etwas beschreiben –> dadurch werden damit alle möglcihen Kombinationen dargestellt, die auftreten können.

[!Tip] inzident(e Kanten) #card wir nennen eine Kante $e = (u, v)$ inzident zu $u$ und $v$ , Also Benachbart, aber aus “Sicht der Kante!”

[!Tip] Adjazent(e Knoten) #card Wir nennen zwei Knoten $u, v$ adjazent zueinander, $\exists e \in E : e = (u, v)$ Also wenn wir eine Kante haben, die (inzident) zu den beiden Knoten ist, dann sind diese Knoten adjazent zueinander!

[!Tip] Schlinge / cycle #card Sofern wir eine Kante $e = (u, v)$ mit $u = w$ haben, dann nennen wir die Kante

[!Tip] isolierte Knoten #card Ein isolierter Knoten beschreibt, einen Knoten, welcher keine Kante darstellt

Mehrfachkanten (zwischen Knoten) Sprechen wir von Mehrfachkanten meinen wir Graphen, in welchen zwischen zwei Knoten mehrere Kanten eine Verbindung zwischen diesen aufbauen.

[!Definition] meist einfache Graphen betrachtet In dieser Vorlesung schauen wir uns primär einfache Graphen an, also solche, die keine Schlingen und Mehrfachkanten aufweisen!

Minimale Knotengrade

[!Definition] Minimaler Knotengrad

Sei $G = (V, E)$ ein Graph.

Wie beschreiben wir den minimalen Knotengrad? #card

Der minimale Knotengrad des Graphen ist folglich beschrieben mit: $δ (G) = v \in V min de g (v)$

Maximaler Knotengrad

[!Definition] maximaler Knotengrad

Sei $G = (V, E)$ ein Graph.

Wie beschreiben wir jetzt den maximalen Knotengrad #card

Der maximale Knotengraph für einen Graphen ist beschrieben mit: $Δ (G) = v \in V max de g (v)$

Gerichtete Graphen

Notationen und die Idee der gerichteten Graphen ist gleich der Notation aus 111.14_Graphen_gerichtet

[!Important] Wir sehen hier weiter, dass $(u, v) \neq = (v, u)$

Kantenzüge

Wir möchten ferner Grundlagen bezüglich der Pfade und Verbindungen zwischen Knoten in Graphen darstellen. Dafür möchten wir für einen beliebigen Graphen die Kantenzüge und anschließend die Pfade und Wege als spezielle Version dieser betrachten und definieren:

[!Notation] Kantenzüge (in einem Graph) Betrachten wir einen Graphen $G = (V, E)$ mit Knoten $v_{1}, v_{2}, \dots, v_{t} \in V$ Sofern jetzt gilt, dass $\forall i, (1 < i \leq t) : (v_{i - 1}, v_{i} \in E)$ dann nennen wir etwas $π = (v_{1}, v_{2}, \dots, v_{t})$ einen Kantenzug von $v_{1} \to v_{t}$ Wir haben also unter Betrachtung der Existenz von Kanten zwischen diversen Knoten ( da $(v_{i - 1}, v_{i}) \in E$ ) einen Weg, wie wir von Knoten $v_{1}$ zu Knoten $v_{t}$ traversieren können!

[!Tip] Die Länge eines Kantenzuges $l (π)$ wird beschrieben durch die Anzahl von Kanten!

Ferner gibt es hiervon noch spezifischere Betrachtungen:

[!Definition] Pfad / Weg Wenn in einem Kantenzug $π = (v_{1}, v_{2}, \dots, v_{t})$ alle $v_{i}$ verschieden sind, dann nennen wir $π$ einen Pfad oder Weg

Das heißt, dass ein Kantenzug beispielsweise einfach eine Verbindung einer einzigen Kante mit sich selbst sein könnte, aber eine spezifischere Betrachtung dessen - wenn dann halt die ganzen Knoten verschieden sind - einem Pfad / Weg entsprechen könnte

Ferner noch die Betrachtung eines zusammenhängenden Graphen:

Grad von Graphen

Grad eines Knoten –> siehe 111.13_Graphen_basics Jenachdem, ob es sich um einen gerichteten / ungerichteten Graphen handelt spricht man nur von degree (ungerichtete Graphen), was etwa der Menge der Adjazentliste des Knoten entspricht, oder auch von outdeg/indeg (gerichtete Graphen), wo man entweder die ausgehenden Verbindungen oder die eingehenden Verbindungen betrachtet.

(1) Lemma | Menge Kanten und Summendarstellung

[!Definition] (1)

$G = * V, E$ sei ein ungerichteter Graph, dann gilt folgend: $2 ∣ E ∣= v \in V \sum d e g (v)$

Wie können wir das beweisen? #card

Beweis: Wir wenden das zweifache Abzählen an, und zählen jetzt alle Kanten-Knoten-Inzidenten Betrachten wir jeden Knoten, und schauen dann die Kanten an, die dieser aufweist. Beschrieben wird dies mit dem Grad $de g$ und wir wissen, dass dieser jeweils zu anderen Knoten im Graph zeigen wird. Aus dieser Betrachtung heraus können wir das dann für alle anderen Knoten wiederholen. Folgend bilden wir also die Summe aller Grade von den Knoten in unserem Graph: $v \in E \sum (de g (v))$ Betrachten wir jetzt folgend die Kanten : dann wissen wir, dass sie zu zwei Knoten inzident ist. (sie verbindet ja zwei Punkte $(u, v$ ) Daraus folgt jetzt also die Zählung von: $e \in E \sum 2 = 2 ∣ E ∣$ und daraus folgt jetzt: $2 ∣ E ∣= v \in V \sum de g (v)$

Wichtig, bei einem Graph mit Schlinge: gilt der Satz auch:

[!Tip] Graph mit Schlinge gilt auch: Betrachten wir einen Graph mit einem Knoten und einer Schlinge: Dann gilt :: $2 \cdot ∣ E ∣= 2 = de g (v) = 2$

(2) Lemma | Anzahl Knoten ungeraden Grades ist gerade

[!Lemma] Die Anzahl von Knoten die ungerade Grades sind sind gerade.

Warum? #card

Beweis: Wir beschreiben unsere Menge von Knoten $V$ als $V = V_{ungerade} \cup V_{gerade}$ Wir splitten also auf in eine Menge von Knoten die einen geraden Grad und ungeraden haben / aufweisen. Wir wissen aus Lemma 1 Menge Kanten und Summendarstellung jetzt: $2 ∣ E ∣= v \in V \sum de g (v) = v \in V_{[} gerade] \sum de g (v) + v \in V_{ungerade} \sum de g (v)$ Dabei ist der erste Term $2 ∣ E ∣$ gerade! Die Summe aus geraden Zahlen ( hier die Grade der geraden Grade) sind auch gerade Ferner ist die Summe aus den ungeraden Zahlen ebenfalls gerade, denn sonst könnte die gesamte Summe nicht gerade sein, wie wir zuvor bereits betrachtet haben! Es folgt jetzt also:

$v \in V_{ungerade} \sum de g (v)$ ist gerade, $⟹ ∣ V_{ungerade}$ ist gerade -> da jeder Summand ungerade ist, muss dann die Anzahl dieser gerade sein.

Wir benötigen noch einige Grundlagen zur Betrachtung von Graphen. Diese beziehen sich auf die Erweiterung oder Verminderung von Kanten / Knoten in einem existierenden Graphen $G$ und wie diese Veränderung entsprechend betitelt wird.

Untergraphen | Teilgraphen

Wir bezeichnen $G^{'} = (V^{'}, E^{'})$ als einen (echten) Untergraph/Teilgraph eines Graphen $G = (V, E)$ , wenn für diesen gilt: $V^{'} \subseteq V \land E^{'} \subseteq E$ Ferner entsteht ein solcher Graph, indem man aus dem originalen Graph $G$ eine nicht leere! Menge an Kanten oder Knoten löscht.

[!Definition] induzierter Untergraph

_was beschreiben wir mit einem induzierten Untergraph? Was gilt für ihn? #card

Ferner nennen wir einen Untergraph $G^{'} = (V^{'}, E^{'})$ induziert, wenn er alle Kanten aus $E$ enthält, bei welchen beide Endknoten in $V^{'}$ liegen.

Er ist also “vollständig” und hat nur Kanten, die einen Anfang und Ende aufweisen.

Wir können noch das Komplement dieser Betrachtung betrachten:

Obergraph | Supergraph

[!Definition] Obergraph

Wie beschreiben wir einen Obergraph? #card

Wir bezeichnen $G^{'} = (V^{'}, E^{'})$ als einen Obergraph/Supergraph von $G = (V, E)$ , wenn für diesen gilt: $V^{'} \supseteq V \land E^{'} \supseteq E$ Also er hat noch weitere Kanten/Knoten enthalten.

Er entsteht, wenn man zu einem Graphen eine nicht leere Menge von Kanten oder Knoten hinzufügt!

Vollständige Graphen

Ferner möchten wir noch vollständige Graphen definieren.

[!Definition] Vollständiger Graph Wir nennen einen einfachen Graph vollständig, wenn jeder Knoten mit allen anderen verbunden ist.

Der vollständige Graph mit $n$ Knoten wird entsprechend $K_{n}$ bezeichnet!

Beispiel liefern folgende vollständige Graphen -> welche hierbei eindeutig sind!

Bipartite Graphen

Durch diese Definition und Betrachtung wird dann $G$ meist auch folgend beschrieben: $G = (V_{1} \cup V_{2}, E)$ -> da wir ja in zwei Mengen aufteilen konnten.

Vollständige bipartite Graphen

[!Definition] vollständiger bipartiter Graph

Was muss gelten, damit ein bipartiter Graph vollständig bipartite heißt? Was wären beispiele dafür? #card

Wir nennen jetzt einen einfachen bipartiten Graphen $G = (V_{1} \cup V_{2}, E)$ vollständig bipartite wenn jeder Knoten $v \in V_{1}$ mit allen Knoten $v_{2 i} \in V_{2}$ verbunden ist -> und weiterführend auch selbiges für alle Knoten $v \in V_{2}$ gilt. Auch diese sind wieder eindeutig und es werden die bipartiten Graphen mit $∣ V_{1} ∣= k \land ∣ V_{2} ∣= l$ mit $K_{k, l}$ bezeichnet.

Beispiele wären etwa

Satz (9) Eigenschaft bipartiter Graph -> Bezug zu Kreisen

[!Definition] Graphen sind bipartit, wenn… #card

Ein Graph ist genau dann bipartite wenn er keinen Kreis ungerader Länge enthält.

-> Diese Betrachtung schließt also ein, dass entweder kein Kreis existiert oder ein Kreis mit gerader Länge gefunden werden kann.

BEWEIS: #nachtragen ! Als möglichen Beweis müssten wir also einen der obigen obigen Fälle zeigen:

kein Kreis schließt ein, dass keine Verbindung zwischen Kanten existieren kann und somit kein Kreis möglich ist, also mindestens ein Element nicht mit dem Rest verbunden ist, außer über eine einzelne Stelle! –> Das ist tatsächlich möglich, weil man

Die Verneinung: “ein Graph ist kein bipartiter Graph, wenn er einen Kreis ungerader Länge enthält” ist vergleichsweise einfach zu betrachten.

Wenn es sich um einen Graph handelt, bei welchem ein Kreis mit ungerader Länge auftritt, so gibt es

Beweis | Satz (9) Eigenschaft bipartiter Graph -> Bezug zu Kreisen

Beweisen wir wieder in zwei Schritten: Beweis: $⟹$ $G$ ist bipartit. Das heißt, wir können ihn in zwei disjunkte Teilmengen $V = V_{1} \cup V_{2}$ aufteilen und jede Kante hat einen Endknoten in Menge $V_{1}$ und $V_{2}$ . Daraus folgt, dass ein Kreis in dieser Menge nur gerade viele Kanten haben kann ( weil wir immer “in die Menge hinein und raus” können).

Beweis: $⟸$ $G$ hat keinen Kreis ungerader Länge lässt darauf schließen, dass es sich um einen bipartiten Graphen handelt Dabei setzen wir voraus, dass $G$ zusammenhängend ist –> da wir somit eine Verallgemeinerung habe und bei disjunkten - nicht zusammenhängenden Mengen - einfach die einzelnen Komponenten prüfen können - weil sowieso bei nicht zusammenhängenden kein bipartiter Graph existiert.

Sei nun $T \subseteq G$ ein Spannbaum mit einer Wurzel $r$ –> 111.26_Graphen_MST (Spannbaum also der, der die Verbindungen des Graphen als Baumstruktur darstellen kann)

Für jedes $v \in V$ ist der Weg in $T$ von $r$ zu $v$ entweder gerade oder ungerade. Dadurch lässt sich jetzt eine Aufteilung generieren –> ist gerade/ungerade und wir haben somit eine Partitionierung erhalten! Ferner also eine disjunkte Verteilung von $V = V_{1} \cup V_{2}$ erhalten! (erste Eigenschaft bipartit) Jetzt gilt zu zeigen, dass bei der Betrachtung ferner keine Kanten in $V_{1} \lor V_{2}$ in sich selbst zeigen

Sei dafür jetzt $e = uv \in E$ Ist jetzt $e \in T$ (also zwei verschiedene Knoten in dem Baum ( beispielsweise eine Knoten $v$ und sein “Kind” $e$ )). Gilt diese Eigenschaft, dann liegen $u$ und v in verschiedenen Partitionen. (Also wir betrachten immer nur die benachbarten Kanten in diesem Spannbaum )

flowchart LR
a0 --> b1 
a0 --> b2
b1 --> c1 
b1 --> c2

(etwa b1 und c2 –> unterschiedliche Länge von $r = a_{0}$ ) aus!

Betrachten wir jetzt eine Verbindung zwischen zwei Knoten, wobei diese nicht im Spannbaum aufgenommen wurde. Es gilt also: $e = uv \neq \in T$ . Dann ist der Weg von $u \to v$ in T zusammen mit $e$ ein Kreis C ( weil wir ja quasi schon einen anderen Pfad gefunden hatten, der die beiden über den Baum verbinden kann) und die Ecken auf dem Weg $T$ von $u \to v$ liegen abwechselnd in $V_{1} \land V_{2}$ Da jetzt $C$ (der Kreis) gerade Länge hat, müssten $u$ und $v$ auch in verschiedenen Partitionen liegen. –> WIr können halt bei einem Kreis gerader Länge schon damit argumentieren, dass diese Menge dann bipartite ist!

[!Attention] Jeder Baum ist bipartite Da sie keinen Kreis aufspannen und etwa das Argument der Aufteilung in gerader/ungerader Abstand zu $r$ eine Partitionierung erzeugt / schafft!

Isomorphe Graphen

[!Definition] Isomorphe Graphen

Wir möchten noch die Eigenschaft von isomorphen Graphen definieren. Wir nennen zwei Graphen $G = (V, E)$ und $G^{'} = (V^{'}, E^{'})$ isomorph, wenn es eine Bijektion $ϕ_{v} : V \to V^{'}$ gibt, sodass $(u, v) \in E ⟺ (ϕ (u), ϕ (u)) \in E^{'}$ ist.

Was beschreibt das, wie kann man es definieren? #card

Das heißt also, dass wir einen Graphen durch eine Translation so darstellen können, dass die Ursprungs-Beziehungen zwischen Knoten via Kanten erhalten bleibt und wir somit diese Informationen der Verbundenheit nicht verlieren!.

Ein mögliches Beispiel:

Simpel also “wir können den Graphen anders aufschreiben” ( ohne, dass seine Grundkonzeption verloren geht)

[!Tip] Bedingung, um Isomorphie zu prüfen: Betrachten wir zwei Graphen und wollen schauen, ob sie isomorph sind, dann müssen wir drei Bedingungen prüfen:
Welche drei sind es? #card

Sei also $G = (V, E), G^{'} = (V^{'}, E^{'})$ dann können wir die Menge der Knoten und Kanten prüfen: $∣ V ∣ = ∣ V^{'} ∣$ ? und $∣ E ∣ = ∣ E^{'} ∣$ ? und ferner: Ist die Verteilung von Graden in dem Graph gleich? Also die $d e g (v) = d e g (v^{'}), v \in V, v^{'} \in V^{'}$ ?

Knotenfärbung |

[!Definition] Knotenfärbung eines Graphen was wird damit beschrieben? #card

Betrachten wir einen Graphen $G = (V, E)$ . Wir bezeichnen eine Abbildung $f : V \to W$ - M ist eine Farbmenge, also enthält einfach Farbbeschreibungen - als Knotenfärbung, wenn diese Abbildung für Kanten $(u, v) \in E$ impliziert, dass $f (u) \neq = f (v)$ –> Das heißt also, dass für Kanten dann gilt, dass ihre verbindenden Knoten nicht die gleiche Farbe haben dürfen!

Aus dieser Definition kann man jetzt noch bestimmen, was das Minimum am Farben ist, um diese Eigenschaft aufbauen zu können.

Chromatische Zahl $X (G)$

[!Definition] chromatische Zahl $X (G)$ was gibt sie an? #card

Die chromatische Zahl ist die kleinste Zahl von Farben, die benötigt werden, um eine Kantenfärbung für einen Graphen $G$ umzusetzen.

Further topics:

Auf diesen Themenkomplex bauen die fortlaufenden Inhalte auf:

scattered-lenity

date-created: 2024-04-15 10:27:53 date-modified: 2024-07-04 06:52:01