1 Grundbegriffe
Definition 1.1 (Schlichte Graphen)
Ein Graph ist ein Paar \(G=(V,E)\), wobei \(V\) eine Menge ist und
\[E\subseteq [V]^2 := \{\{a,b\}\mid a,b\in V,\;a\neq b\}.\]
- Die Elemente von \(E\) sind 2-elementige Teilmengen von \(V\). Daher beträgt die maximale Anzahl der Kanten die Dreieckszahl
\[\Delta_{n-1} = {n\choose 2} = \frac{n(n-1)}{2}.\] - Um Notationskonflikte zu vermeiden, nehmen wir stillschweigend an, dass \(V\cap E=\emptyset\).
Dies nennt man einen ungerichteten Graphen, um ihn von einem gerichteten Graphen zu unterscheiden, und einen schlichten Graphen, um ihn von einem Multigraphen abzugrenzen.
- Ein gerichteter Graph entspricht einer beliebigen binären Relation und ein ungerichteter Graph entspricht einer irreflexiven, symmetrischen binären Relation.
Die Elemente von \(V\) sind die Knoten (Ecken, engl. vertices) von \(G\), und die Elemente von \(E\) sind dessen Kanten (engl. edges). Ein Graph mit Knotenmegne \(V\) heißt ein Graph auf \(V\).
- Wir bezeichnen das Knotenset von \(G\) mit \(V(G)\) und das Kantenset mit \(E(G)\).
- Später schreiben wir \(G=(V(G),E(G))\).
- Wir sprechen vereinfacht von einem Knoten \(v\in G\) (statt \(v\in V(G)\)), einer Kante \(e\in G\) usw.
Die Zahl der Knoten eines Graphen \(G\) ist seine Ordnung, geschrieben
\[n(G)=|V(G)|,\]
und die Zahl der Kanten (seine Größe) ist
\[m(G)=|E(G)|.\]
Graphen werden je nach ihrer Ordnung als endlich, unendlich, abzählbar usw. bezeichnet. Unsere Graphen sind, falls nicht anders angegeben, endlich.
- Für den leeren Graphen \((\emptyset,\emptyset)\) schreiben wir einfach \(\emptyset\). Ein Graph der Ordnung 0 oder 1 heißt trivial.
Definition
Sei \(G = (V,E)\) ein Graph.
- \(a,b \in V\) sind abhängig / benachbart \(\eq\) \(\{a,b\} \in E\).
- \(e,f \in E\) sind abhängig / benachbart \(\eq\) \(a \cap b \neq \emptyset\).
- \(V^\prime \subseteq V\) ist stabil \(\eq\) die Knoten aus \(V^\prime\) sind paarweise unabhängig \(\eq\) \(G[V^\prime] \cong (V^\prime, \emptyset)\).
- \(V^\prime\) ist maximal stabil \(\eq\) \(\forall v \in V \setminus V^\prime: V^\prime \cup \{v\}\) ist nicht stabil.
- \(V^\prime\) ist maximum stabil, wenn es keine größere stabile Menge gibt.
- Die Mächtigkeit einer größten stabilen Menge heißt die Unabhängigkeitszahl oder Stabilitätszahl \(\alpha(G)\). Also \[\alpha(G) = \max \{ |I| : I \subseteq V \text{ und } \forall u,v \in I: \{u,v\} \notin E \}\]
Analog definiert man Matching als eine stabile Menge von Kanten und die Mächtigkeit einer größten kantenstabilen heißt die Matchingzahl \(\nu(G)\) (mehr darüber in section 9).
Beispiel
Ein Graph hat Unabhängigkeitszahl \(\alpha(G)=1\) genau dann, wenn er vollständig ist: \[\alpha(G)=1\;\eq\;\exists n\in\mathbb{N}:G\cong K_n.\]
Definition 1.6
- Untergraph (induzierter Teilgraph) entsteht, indem einige Knoten entfernt werden;
- Teilgraph (Subgraph) entsteht, indem einige Knoten und Kanten entfernt werden.
- Aufspannender Teilgraph entsteht, indem einige Kanten entfernt werden.
Definition 1.7 (Cliquenzahl)
Sei \(G = (V,E), V^\prime \subseteq V, n^\prime := |V^\prime|\). \(V^\prime\) heißt Clique, wenn induzierter Teilgraph \(G[V^\prime]\) vollständig ist, also \[ G[V^\prime] \cong K_{n^\prime} \] Insbesondere ist Clique \(V^\prime\) die Menge der paarweise benachbarten Knoten.
Die Mächtigkeit der größten Clique heißt die Cliquenzahl w(G) von G. Also \[\omega(G) = \max \{ |C| \mid C \subseteq V \text{ und } \forall u, v \in C : \implies \{u, v\} \in E \}\]
- Eine Menge \(\{A_{1},\dots,A_{k}\}\) mit \(V(G)=A_{1}\cup\cdots\cup A_{k}\), sodass \(G[A_{i}]\) für alle \(i=1,\dots,k\) vollständig ist, heißt Cliquen-Überdeckung von \(G\) der Größe \(k\). >
- Die minimale Größe aller Cliquen-Überdeckungen von \(G\) heißt Cliquen-Überdeckungszahl \(\theta(G)\).
Beispiel
Ein Graph mit der Cliquenzahl 4, der besitzt
- 23 Cliquen als Knoten (rot)
- 42 Cliquen als Kanten (schwarz)
- 19 Cliquen als Dreiecke (hell-/dunkelblau)
- 2 Clique als Tetraeder (dunkelblau)
Definition
- Der Kantengraph / Line-Graph von \(G\) ist \(L(G) := (E(G), E^\prime)\) mit Kanten als Knoten und je zwei Knoten sind in \(L(G)\) adjazent, wenn die zugehörigen Kanten auseinen gemeinsamen Endknoten haben, also in \(G\) adjazent sind. D.h. \[\forall e, f \in E(G) : ef \in E^\prime :\eq e \cap p \neq \emptyset\]
- Komplementgraph \(\bar{G}\) von \(G = (V, E)\) ist \(\bar{G} = (V, [V]^2 \setminus E\)).
Definition 1.13 (Knotengrad)
Sei \(G=(V,E)\) ein Graph. Der Grad (oder Valenz) eines Knotens \(v\in V\) ist \[d_G(v)=|\{\,e\in E\mid v\in e\}|.\] Ein Knoten mit Grad \(0\) heißt isoliert.
Das Minimum der Grade und das Maximum der Grade von \(G\) definiert man durch \[\delta(G):=\min_{v\in V}d_G(v),\quad \Delta(G):=\max_{v\in V}d_G(v).\]
Ist \(d_G(v)=k\) für alle \(v\in V\), so heißt \(G\) k-regulär. Ein 3-regulärer Graph heißt kubisch.
Der Durchschnittsgrad von \(G\) ist \[d(G):=\frac{1}{|V|}\sum_{v\in V}d_G(v).\]
Das Verhältnis zwischen Knoten und Kanten ist \[\varepsilon(G) := \frac{n(G)}{m(G)}\]
Lemma
Klar, dass minimaler ≤ durchschnittlicher ≤ maximaler Grad: \[ \delta(G) \leq d(G) \leq \Delta(G) \leq \min(n(G), m(G)) \]
Bemerkung
Reguläre Graphen mit einem Grad von höchstens 2 lassen sich leicht klassifizieren:
- 0-regulärer Graph (kantenloser Graph \(\bar{K}_n\)) besteht aus unzusammenhängenden Knoten.
- 1-regulärer Graph (Paarung) besteht aus unabhängigen Kanten.
- 2-regulärer Graph besteht aus disjunkten Kreisen.
Lemma 1.14 (The degree sum formula)
- \(\sum_{v \in V(G)} d_G(v) = 2|E(G)|\)
- \(2\varepsilon(G) = d(G)\)
Lemma 1.15 (Handshaking lemma)
Die Anzahl der Knoten ungerades Grades ist stets gerade.
Lemma 1.16
Jeder Graph G mit mindestens einer Kante hat einen Teilgraphen H mit \[\delta(G) \varepsilon(h) \ge \varepsilon(G)\]
