Endliche Graphen
Wir konzentrieren uns hier auf den einfachsten Graphen-Typ:
Definition (Graph)
Ein (endlicher, ungerichteter, einfacher) Graph ist ein Paar G = (E, K) mit:
(a) | E ist eine endliche nichtleere Menge, |
(b) | K ⊆ { { a, b } | a, b ∈ E, a ≠ b }. |
Die Elemente von E heißen die Ecken von G und die Elemente von K die Kanten von G. Gilt { a, b } ∈ K, so sagen wir, dass die Ecken a und b durch eine Kante verbunden sind. Die Ecke b heißt dann ein Nachbar von a in G.
Wir schreiben für Kanten oft auch kurz a b anstelle von { a, b }.
Die Anzahl |E| der Ecken eines Graphen G heißt die Ordnung von G und die Anzahl |K| der Kanten von G heißt die Größe von G.
Graphen können wir visualisieren, indem wir die Ecken E als benannte Punkte zeichnen, und dann genau die Punktpaare a b mit einer Linie verbinden, die eine Kante des Graphen bilden. Unsere Graphen sind nicht gerichtet, d. h. die Verbindungen sind keine Pfeile. Weiter gibt es keine Schlingen der Form a a ∈ K, und wir erlauben auch keine mehrfachen Verbindungen zwischen zwei Ecken.
Ein Beispiel für einen visualisierten Graphen zeigt das folgende Diagramm:
Einige wichtige spezielle Graphen sind die folgenden:
Definition (die Graphen Kn, Kn, m, Cn)
Wir definieren für alle n, m ≥ 1:
| Kn | = ({ 1, …, n }, { i j | 1 ≤ i < j ≤ n }), |
| Kn, m | = ({ 1, …, n + m }, { i j | 1 ≤ i ≤ n, n + 1 ≤ j ≤ n + m}), |
| Cn | = ({ 1, …, n }, { i (i + 1) | 1 ≤ i < n } ∪ { n 1 }), falls n ≥ 3. |
Der Leser visualisiere sich diese Graphen anhand von Diagrammen. Zu den Graphen Kn und Kn, m gehören die beiden folgenden Begriffsbildungen.
Definition (vollständig)
Ein Graph heißt vollständig, wenn je zwei seiner Ecken durch eine Kante verbunden sind.
Die Graphen Kn sind vollständig. Der Graph Kn wird oft auch als der kanonische vollständige Graph mit n Ecken bezeichnet.
Definition (bipartit, vollständig bipartit)
Ein Graph G = (E, K) heißt bipartit, wenn sich E derart in zwei Mengen E1 und E2 zerlegen lässt, dass jede Kante von G eine Ecke aus E1 mit einer Ecke aus E2 verbindet. (Die Mengen E1, E2 können leer sein.) G heißt vollständig bipartit, falls eine derartige Zerlegung existiert, sodass jede Ecke aus E1 mit jeder Ecke aus E2 verbunden ist.
Die Graphen Kn, m sind vollständig bipartit für die Zerlegung E1 = { 1, …, n } und E2 = { n + 1, …, n + m } der Eckenmenge { 1, …, n + m }.
Wir definieren:
Definition (Grad)
Sei G = (E, K) ein Graph. Dann setzen wir für alle a ∈ E
N(a) = { b ∈ E | a b ∈ K },
d(a) = „die Anzahl der Elemente von N(a)“,
und nennen d(a) den Grad der Ecke a in G.
Hierbei steht „d“ für „degree“. Es gilt folgende Summenregel:
Satz (Gradsumme)
Sei G = (E, K) ein Graph der Größe k. Dann gilt ∑a ∈ E d(a) = 2 · k.
Der Satz ist anschaulich klar, denn jede Kante trägt zwei „Einheiten“ zur linken Summe bei. Ein ausführlicher Beweis verläuft wie folgt:
Beweis
Für alle a ∈ E sei S(a) = { (a, b) | a b ∈ K }. Dann ist d(a) die Anzahl der Elemente von S(a), und die Mengen S(a), a ∈ E, sind paarweise disjunkt, da wir hier geordnete Paare verwenden. Damit haben wir
|⋃a ∈ E S(a)| = ∑a ∈ E |S(a)| = ∑a ∈ E d(a).
Andererseits ist
|⋃a ∈ E S(a)| = |{ (a, b) | ab ∈ K }| = 2 · |K| = 2 · k.
Isomorphe Graphen
Die Namen der Ecken sind für graphentheoretische Fragen unerheblich. Ein Beispiel ist: „Besitzt dieser Graph eine Ecke vom Grad 3?“ Diese Unerheblichkeit wird in folgendem Isomorphiebegriff ausgedrückt:
Definition (isomorph, Isomorphismus)
Zwei Graphen G1 = (E1, K1) und G2 = (E2, K2) heißen isomorph, falls es eine Bijektion f : E1 → E2 gibt, sodass für alle a, b ∈ E1 gilt:
a b ∈ K1 gdw f (a) f (b) ∈ K2.
Jede solche Bijektion f heißt dann ein Isomorphismus zwischen G1 und G2.
Zwei isomorphe Graphen haben die gleiche Ordnung und Größe, und sie stimmen weiter in allen Eigenschaften überein, die sich mit Hilfe von Ecken und Kanten formulieren lassen.
Ist G = (E, K) ein Graph der Ordnung n mit Eckenmenge E = { a1, …, an }, so setzen wir E′ = { 1, …, n } und K′ = { i j | ai aj ∈ K }. Dann ist G′ = (E′, K′) isomorph zu G, und die Funktion f : E → E′ mit f (ai) = i für alle 1 ≤ i ≤ n ist ein Isomorphismus. Diese Überlegung zeigt, dass es prinzipiell genügt, Graphen zu betrachten, deren Eckenmenge von der Form { 1, …, n } ist.