Lineare Algebra I, WS 2020/21

Inhalt

13.1 Definition

Definition 13.1

Ein (endlicher) Graph \(G= (\mathbb E, \mathbb K)\) ist ein Paar, das besteht aus

  1. einer Menge \(\mathbb E\), deren Elemente die Ecken oder Knoten des Graphen genannt werden,

  2. einer Menge \(\mathbb K\) von zweielementigen Teilmengen von \(\mathbb E\), deren Elemente die Kanten des Graphen \(G\) genannt werden.

Wir können einen Graphen durch eine Zeichnung visualisieren, indem wir die Ecken des Graphen als »dicke Punkte« zeichnen, und zwei Ecken \(P_1\), \(P_2\) genau dann verbinden, wenn die Teilmenge \(\{ P_1, P_2 \} \) ein Element der Menge \(\mathbb K\) ist. Die Abbildung zeigt einen Graphen mit \(6\) Ecken. Man beachte aber: Nicht jeder Graph lässt sich »überschneidungsfrei« in der Ebene zeichnen. Siehe Abschnitt 13.6.
\includegraphics[width=4.9cm]{figures/graph1}

Der hier definierte Begriff des Graphen hat nichts mit Funktionsgraphen zu tun.

Bemerkung 13.2

In unserer Definition

  • kann keine Kante einen Knoten mit sich selbst verbinden,

  • gibt es zwischen zwei Knoten entweder keine oder eine Kante (aber nicht mehrere).

Je nachdem, wozu man die Theorie benutzen möchte, könnte man die Definition abändern und allgemeinere Formen von Graphen erlauben, als wir es hier tun.

Eine andere nützliche Variante ist der Begriff des gerichteten Graphen, in dem jede Kante des Graphen mit einer Richtung versehen wird (und dann auch erlaubt ist, dass zwei Knoten durch je eine Kante in die beiden möglichen Richtungen miteinander verbunden sind). Die Netzwerke in Frage 2.7 kann man als gerichtete Graphen betrachten.

Wie genau die Ecken eines Graphen benannt werden (ob mit \(1, 2, 3, \dots \) oder \(A, B, C, \dots \), oder noch anders) spielt für uns keine Rolle. Wir definieren deshalb:

Definition 13.3

Seien \(G= (\mathbb E, \mathbb K)\) und \(G^\prime = (\mathbb E^\prime , \mathbb K^\prime )\) Graphen. Ein Isomorphimus ist eine Bijektion \(\varphi \colon \mathbb E\to \mathbb E^\prime \), so dass für alle \(i, j\in \mathbb E\) gilt: \(\{ i,j\} \in \mathbb K\Leftrightarrow \{ \varphi (i), \varphi (j)\} \in \mathbb K^\prime \). Zwei Graphen heißen isomorph, wenn es einen Isomorphismus zwischen ihnen gibt.

Alle Eigenschaften von Graphen, die wir im folgenden betrachten, werden durch Isomorphismen erhalten.

Es ist allerdings mitunter nicht leicht festzustellen, ob zwei gegebene Graphen zueinander isomorph sind oder nicht. (Natürlich gibt es prinzipiell die Möglichkeit, alle Bijektionen zwischen den Eckenmengen durchzuprobieren und zu testen, ob es sich um Isomorphismen von Graphen handelt. Wenn die Anzahl der Ecken nicht sehr klein ist, ist das aber nicht praktikabel.)

Definition 13.4

Sei \(G= (\mathbb E, \mathbb K)\) ein Graph. Ein Graph \(G^\prime = (\mathbb E^\prime , \mathbb K^\prime )\) heißt ein Teilgraph von \(G\), wenn \(\mathbb E^\prime \subseteq \mathbb E\) und \(\mathbb K^\prime \subseteq \mathbb K\).