Satz 3.5. Sei \(G = (E, K)\) ein (Multi-)Graph. Dann gilt:
\(\sum_{v \in E} \deg{v} = 2 |K|\)
Die Anzahl der Ecken mit ungeradem Grad ist gerade.

Zusammenhängende Graphen #

Definition 3.10. Ein (Multi-)Graph \(G = (E, K)\) heißt zusammenhängend, wenn je zwei Ecken \(u, v \in E\) durch einen Weg verbunden werden können, d.h. es gibt einen Weg \(u_1, \dots, u_s\) in G mit \(u_1 = u\) und \(u_s = v\).

Der Beste weg zu zeigen, dass ein Graph zusammenhängend ist, ist ihn zu malen.

Eulersche Graphen #

Satz 3.11. Sei \(G\) ein zusammenhängender Graph. Dann sind folgende Aussagen äquivalent:
\(G\) ist eulersch.
Jede Ecke von \(G\) hat geraden Grad.

Um zu zeigen dass ein Graph eulersch ist, muss man einfach zeigen dass jede Ecke einen gerade Grad hat.

Hamiltonsche Graphen #

Definition 3.12. Ein (Multi-)Graph heißt hamiltonsch, wenn es einen Kreis in \(G\) gibt, der jede Ecke von \(G\) enthält. Ein solcher Kreis heißt dann Hamilton-Kreis (oder auch hamiltonscher Kreis).

Prüfercodes #

Der Prüfercode ist immer 2 kürzer als die Knoten vom Baum.

Code zu Baum #

Mahle die \(n\) Knoten des Baumes
Erstelle eine Liste \(1, \dots, n\)
Starte mit der ersten Zahl des Codes: finde die kleinste Zahl in der Liste welche nicht im Code enthalten ist. Verbinde diese Knoten und streiche beide aus ihren sequenzen.
Wiederhole Schrtt 3 bis die letzten Zahlen in der Liste stehen. Diese werden miteinander verbunden.

Der Algorithmus ist nicht schwer, aber es empfehlt sich zu üben, üben, üben!

Baum zu Code #

Streiche das kleinste Blatt im Baum und notiere sein Elternknoten.
Wiederhole Schritt 1 bis die letzten zwei Knoten im Baum vorhanden sind. Diese werden nicht notiert.

Adjazenzmatrizen #

Wege der Länge \(\ell\) #

Satz 3.18. Sei \(G = (E, K)\) ein Graph mit Eckenmenge \(E = \{u_1, \dots, u_n\}\) und sei \(A\) die Adjazenzmatrix von \(G\). Für jede Zahl \(\ell \in \mathbb{N}\) ist die Anzahl der Wege in \(G\) von \(u_i\) nach \(u_j\) mit Länge \(\ell\) gegeben durch den \((i, j)\)-Eintrag der Matrix \(A^\ell\).

Um alle Wege der Länge \(\ell\) zu berechnen, muss man die potenzierte Adjazenzmatrix aufsummieren.

# Beispiel um alle Wege der Länge 2 zu berechnen
A = [0 1 0 0 0; 1 0 1 1 1; 0 1 0 1 0; 0 1 1 0 1; 0 1 0 1 0]
l = sum(A^2)
println(l)