Graphentheorie

by Bartlomiej Marzec

Posted on 27 Mar 2014

Graphen sind ein anderer Blickwinkel auf Relationen, d.h. mathematische Strukturen die Beziehungen zwischen verschiedenen Objekten darstellen.

Grundlagen

Definition G1 (Graph)
Ein Graph ist ein Paar $G=(V,E)$ wobei:
  • $V$ eine Menge ist und
  • $E \subset V^{[2]}$ eine Teilmenge der zweielementigen Teilmengen von $V$ ist. Dabei ist: $V^{[2]}=\{\{u,v\}|u,v\in V, u\not=v\}$
Ein gerichteter Graph ist ein paar $G=(V,E)$, wobei:
  • $V$ eine Menge ist und
  • $E\subset V\times V$
Die Elemente von $V$ heißen Knoten oder Ecken, die Elemente von $E$ heißen Kanten. Wir nehmen immer an, dass $V$ endlich ist und dass $V \cap E = \emptyset$ ist.
  • Ein gerichteter Graph ist nichts anderes als eine Relation (auf der Menge der Knoten)
  • Ein Graph ist nichts anderes als eine symmetrische, antireflexive Relation (auf der Menge der Knoten)
Definition G2 (Vollständiger Graph)
Sei $n\in\mathbb{N}:=\{0,1,2,...\}$. Der vollständige vollständige Graph der Ordnung $n$ ist der Graph $K_n$, der wie folgt definiert ist:
  • Knotenmenge von $K_n:\{1,...,n\}$
  • Kantenmenge von $K_n:\{\{j,k\}|j,k\in\{1,...,n\}, und j\not=k\}$
Definition G3 (Vollständiger bipartiter Graph)
Seien $n,m\in\mathbb{N}$. Der vollständige bipartite Graph der Ordnung (n,m) ist ein Graph, der wie folgt definiert ist:
  • Knotenmenge von $K_{n,m}:\{(0,1),...,(0,n),(1,1),...,(1,m)\}$
  • Kantenmenge von $K_{n,m}:\{\{(0,j),(1,k)|j\in\{1,...,n\},k\in\{1,...,m\}\}$.
Definition G4 (Isomorphie von Graphen)
  • Ein Isomorphismus zwischen zwei Graphen $G=(V,E)$ und $G'=(V',E')$ ist eine bijektive Abbildung $f:V\rightarrow V'$ mit: $$\forall \underset{u\not=v}{u,v}\in V \qquad \{f(u),f(v)\}\in E' \Leftrightarrow \{u,v\}\in E$$ D.h. ein Isomorphismus identifiziert die Knoten der beiden Graphen so miteinander, dass die Kantenstruktur erhalten bleibt
  • Ein Isomorphismus zwischen zwei gerichteten Graphen $G=(V,E)$ und $G'=(V',E')$ ist eine bijektive Abbildung $f:V\rightarrow V'$ mit: $$\forall u,v\in V \qquad (f(u),f(v))\in E' \Leftrightarrow (u,v)\in E$$
  • Zwei (gerichtete) Graphen heißen isomorph, wenn es einen Isomorphismus (gerichteter) Graphen zwischen ihnen gibt.

Im Allgemeinen ist es ein sehr schweres Algorithmisches Problem festzustellen, ob zwei gegebene Graphen isomorph sind. Aber es gibt viele Invarianten, die einem in Speziellfällen erlauben festzstellen, dass zwei Graphen nicht isomorph sind!

Definition G5 (Adjazenz, Grad)
  • Zwei Knoten $u,v\in V$ eines (gerichteten) Graphen $G=(V,E)$ heißen adjazent oder benachbart, falls es eine Kante zwischen $u$ und $v$ gibt, d.h. falls: $$\{u,v\}\in E \qquad ((v,u)\in E \text{ oder } (u,v)\in E)$$
  • Zwei Kanten in einem (gerichteten) Graphen heißen adjazent oder benachbart, falls sie einen gemeinsamen Knoten haben
  • Sei $G=(V,E)$ ein Graph und sei $v\in V$. Der Grad von $v$ ist definiert als $$\text{deg}(v):= \#\{\{u,v\}|u\in V\}$$
  • Sei $G=(V,E)$ ein gerichteter Graph und sei $v\in V$. Dann definieren wir folgende Grade von $v$:
    • Der Ein-Grad von $v$ ist $$\text{deg}^+(v):=\#\{(u,v)|u\in V, (u,v)\in E\}$$
    • Der Aus-Grad von $v$ ist $$\text{deg}^-(v):=\#\{(v,u)|u\in V, (v,u)\in E\}$$
    • Der Grad von $v$ ist $$\text{deg}(v):=deg^+(v)+deg^-(v)$$
Definition G6 (Gradfolge)
Sei $G=(V,E)$ ein (gerichteter) Graph. Die Folge $$(d,\#\{v\in V| \text{deg}(v)=d\})$$ heißt Gradfolge von $G$, $d\in\{0,...,\#V\}$, $(d\in\{2,\#V\})$

Analog im gerichteten Fall. Ein Gradfolge und Aus-Gradfolge.

In der Literatur wird die Gradfolge manchmal anders definiert, nähmlich als Folge aller Knotengrade, die tatsächlich auftreten, sortiert nach Größe.

Theorem G7 (Gradfolgen sind Isomorphie-Invarianten)
  • Sind zwei Graphen isomorph, so stimmen ihre Gradfolgen überein. Insbesondere stimmen die Gradfolgen zweier Graphen nicht überein, so können sie nicht isomorph sein! Die Umkehrung gilt i.A. nicht, d.h. aus der Gleichheit der Gradfolgen kann man nicht auf Isomorphie schließen.
  • Sind zwei gerichtete Graphen isomorph, so stimmen ihre Gradfolgen (bzw. die Ein-/Aus-Gradfolgen) überein
Satz G8 (Summe der Grade)
  • Sei $G=(V,E)$ ein (gerichteter) Graph. Dann ist $$\sum_{v\in V}\text{deg}(v)=2*\#E$$
  • Insbesondere: Jeder (gerichteter) Graph hat eine gerade Anzahl von Knoten mit ungeraden Grad

Beweis:

  • Ist $G$ ungerichtet, so verbindet jede Kante genau zwei Knoten untereinander. Also: $$\sum_{v\in V}\text{deg}(v)=2*\#E$$ Ist $G$ gerichtet, so folgt $$\sum_{v\in V}\text{deg}(v)=\sum_{v\in V}(\text{deg}^+(v)+\text{deg}^-(v))=2*\#E$$ (Jede Kante hat genau einen Anfangs- und Endknoten)
  • Nach dem ersten Teil ist die Summe der Knoten gleich $$\underbrace{2*(\text{Anzahl der Knoten})}_{gerade}$$ Da die Summe ungerade vieler ungeraden Zahlen ungerade ist folgt: die Anzahl der ungeraden Summanden ist gerade.

Beispiel
Die Anzahl der Chinesen, die bisher mit ungerade vielen Chinesen telefoniert haben ist gerade. Modellierung durch einen Graphen:

  • Knoten: die Menge der Chinesen
  • Kanten (ungerichtet): Zwei Knoten C und D sind dann durch eine Kante verbunden wenn die zu C und D gehörigen Chinesen mindestens einmal miteinander telefoniert haben

Beispiel:

  1. Der Graph:
    image/svg+xml
    hat die Gradfolge: (0,1), (1,2), (2,1), (3,0), (4,0).
  2. Der Graph: image/svg+xml hat die Gradfolge: (0,0),(1,0),(2,3),(3,0),...,(6,0) und die Ein-Gradfolge: (0,1),(1,1),(2,1),(3,0).
Definition G9 (Untergraphen, induzierte Untergraphen)
  • Sei $G=(V,E)$ ein (gerichteter) Graph. Ein (gerichteter) Graph $G'=(V',E')$ ist ein (gerichteter) Untegraph von $G$, wenn: $$V'\subset V\qquad \text{und} \qquad E'\subset E$$
  • Ein (gerichteter) induzierter Untegraph von $G=(V,E)$ ist ein (gerichteter) Untegraph $G'=(V',E')$ von $G$ mit $$E'=E\cap(V^{[2]}) \qquad (\text{bzw.} E'=E\cap(V'\times V'))$$

Ein iduzierter Untegraph enthält alle Kanten zwischen seinen Knoten, die auch bereits im ungebenden Graphen enthalten sind. Oft sagt man auch, dass ein (gerichteter) Graph ein (gerichteter|induzierter) Untegraph eines (gerichteten) Graphen ist, wenn er zu einem (gerichteten|induzierten) Untegraph isomorph ist.

Beispiel:

Sei $G$ durch die Abbildung gegebene Graph: Dann:

  • ist ein Untegraph von $G$, aber kein induzierter Untegraph von $G$
  • ist ein induzierter Untegraph von $G$
  • ist zu keinen Untegraph von $G$ isomorph

Definition G10 (Weg, Kreis)
Sei $G=(V,E)$ ein (gerichteter) Graph. Sein $n\in\mathbb{N}$:
  • Ein (gerichteter) Weg der Länge $n$ in $G$ ist eine Folge $v_0,...,v_n$ verschiender (!) Knoten aus $V$ mit: $$\forall_{j\in\{0,...,n-1\}}\{v_j,v_{j+1}\}\in E\qquad (\text{bzw. }(v_j,v_{j+1}\in E))$$
  • Ein (gerichteter) Kreis der Länge $n-1$ in $G$ ist eine Folge $v_0,...,v_n$ verschiender (!) Knoten aus $V$ mit: $$\forall_{j\in\{0,...,n-1\}}\{v_j,v_{j+1}\}\in E\qquad (\text{bzw. }(v_j,v_{j+1}\in E)) \text{ und}$$ $$\{v_n,v_0\}\in E\qquad (\text{bzw. } (v_n,v_0)\in E)$$

Beispiel:

  • 0,1,3 ist ein Weg in G, aber kein Kreis
  • 0,1,4 ist kein Weg in G
  • 0,1,2 ist ein Kreis in G
  • 0,1,0 ist kein Weg in G

Definition G11 ((stark) zusammenhängender Graph, Zusammenhangskomponenten eines Graphen)
  • Ein Graph heißt zusammenhängend, falls es zu je zwei (verschiedenen) Knoten einen Weg in diesem Graph gibt, der diese beiden Knoten verbindet.
  • Ein gerichteter Graph heißt stark zusammenhängend, falls es zu je zwei (verschiedenen) Knoten $u$ und $v$ einen gerichteten Weg von $u$ nach $v$ und einen von $v$ und $u$ gibt
  • Die bezüglich der (gerichteten) Untergraphenrelation maximalen (stark) zusammenhängenden Untegraphen heißen (starke) Zusammenhangskomponenten des Graphen
Definition G12 (Abstand)
Sei $G=(V,E)$ ein Graph und seien $u,v\in V$. Der Abstand $d_G(u,v)$ von $u$ nach $v$ in G ist die Länge eines kürzesten Weges in $G$ der $u$ und $v$ verbindet. Gibt es keinen Weg zwischen $u$ und $v$ (d.h. liegen $u$ und $v$ in verschiedenen Zusammenhangskomponenten von $G$), so definieren wir $d_G(u,v):=\infty$.

Bemerkung:

  • Ist $G=(V,E)$ ein Graph, so ist $d_G:V\times V\rightarrow \mathbb{N}\cup\{\infty\}$ eine Metrik auf $V$.
  • Analog können wir Abstände auf gerichteten Graphen definiere, diese sind i.A. jedoch nicht symmetrisch.
  • Wir werden später gewichtete Graphen einführen, in denen Kanten nicht unbedingt die Länge 1 haben müssen.

Representation von Graphen

Es gibt im wesentlichen zwei allgemeine Möglichkeiten um Graphen elektronisch zu repräsentieren:

  1. Adjazenzmatrizen
  2. Adjazenzlisten
Definition G13 (Adjazenzmatrix)
Sei $G=(V,E)$ ein Graph. Eine Adjzenzmatrix von $G$ ist die Matrix $(a_{u,v})_{u,v\in V}$, wobei: $$ a_{u,v}=\begin{cases} 1 & \text{falls } \{u,v\}\in E \\ 0 & \text{falls } \{u,v\}\not\in E\end{cases}$$
Definition G14 (Adjazenzlisten)
Sei $G=(V,E)$ ein Graph. Die Adjazenzlistendarstellung von $G$ ist die Folge $(a_v)_{v\in V}$ der Adjazenzlisten der Knoten, dabei ist $a_v$ die Liste der Knoten die zu $v$ benachbart sind.

Bäume

Definition G15 (Baum, Wald)

Ein Baum ist ein Graph, der zusammenhängend ist und keine Kreise enthält

Ein Wald ist ein Graph, dessen Zusammenhangskomponenten Bäume sind (bzw. ein Wald ist ein Graph, der keine Kreise enthält).

Definition G16 (Blatt, innerer Knoten)

Knoten vom Grad 1 in einem Baum heißen Blätter

Knoten vom Grad mindestens 2 in einem Baum heißen innere Knoten

Satz G17 (Existenz von Blättern)
Jeder Baum mit mindestens zwei Knoten enthält mindestens ein Blatt.

Beweis:

Sei $T=(V,E)$ ein Baum mit mindestens zwei Knoten. Sei $v_0,...v_n$ ein längster Weg in $T$. Wegen $\#V\geq 2$ ist $n\geq 1$. Wir zeigen: $v_0$ ist ein Blatt von $T$. (d.h. zu zeigen $\text{deg}(v_0)=1$)

  • Es ist $\text{deg}(v_0)\geq 1$, denn $v_1$ ist benachbart zu $v_0$
  • Es ist $\text{deg}(v_0)\leq 1$, denn: angenommen $v_0$ besitzt einen weiteren Nachbar $v\in V$. Da $v\not=v_1$ und $T$ keine Kreise enthält, folgt: $v\not\in\{v_2,...,v_n\}$. Dann ist aber auch $v, v_0, v_1,...,v_n$ ein Weg in $T$, im Widerspruch dazu, dass $v_0,...,v_n$ ein längster Weg in $T$ ist. Also ist $\text{deg}(v_0)\leq 1$
Insgesamt: $\text{deg}(v)=1$, d.h. $v_0$ ist ein Blatt von $T$.

Blog Search

Popular Blog Categories

Side Widget Well

Bootstrap's default wells work great for side widgets! What is a widget anyways...?