Ungerichtete Graphen/Einführung/Textabschnitt

Definition

Ein ungerichteter Graph auf einer Menge $V$ (die die Eckpunktmenge des Graphen heißt) besteht aus einer gewissen Auswahl an zweielementigen Teilmengen (die die Kantenmenge des Graphen heißt) von $V$ .

Man spricht auch kurz von einem Graphen. Ein Graph ist nichts anderes als eine symmetrische Relation auf $V$ ohne Selbstbezug (ohne Schleifen). Typischerweise ist die Grundmenge, zu der man auch Knotenmenge oder Punktmenge oder Vertexmenge sagt, endlich. Grundsätzlich könnte man immer $V = {1, \dots, n}$ nehmen, doch ist dies nicht immer sinnvoll. Eine typische Darstellung eines Graphen ist ein Diagramm aus $n$ Punkten, von denen manche miteinander durch eine Kante verbunden sind, manche nicht. Die Menge der Kanten bildet eine Teilmenge der Potenzmenge von $V$ , und zwar eine, wo sämtliche Teilmengen zweielementig sind. Im Sinne der obigen Definition darf $(v, v)$ keine Kante sein. Die Menge aller Kanten wird häufig mit $E$ bezeichnet und man schreibt kurz $u v \in E$ für den Sachverhalt, dass ${u, v}$ eine Kante des Graphen ist. Ein Graph wird oft kurz in der Form $(V, E)$ angegeben. Wenn man zu einer Menge $V$ mit $𝔓_{2} (V)$ die Menge aller zweielementigen Teilmengen von $V$ bezeichnet, so kann man die Kantenmenge als $E \subseteq 𝔓_{2} (V)$ auffassen.

Definition

Zu einem Punkt $v \in V$ in einem Graphen $G = (V, E)$ nennt man

N (v) = {u \in V ∣ {u, v} \in E}

die Nachbarschaft von $v$ .

Wenn zwei Punkte benachbart sind, also durch eine Kante verbunden, so sagt man auch, dass sie adjazent sind. Ferner sagt man, dass eine Kante mit einem Knoten inzident ist, wenn der Knoten in der Kante vorkommt. Die Kante ${u, v}$ ist also inzident zu $u$ und zu $v$ und sonst zu keinem Punkt. Zwei Kanten nennen wir koinzident, wenn ihr Durchschnitt nicht leer ist, wenn sie also inzident zu einem gemeinsamen Punkt sind. Für eine Teilmenge $S \subseteq V$ setzt man $N (S) = ⋃_{s \in S} N (s)$ und nennt dies die Nachbarschaftsmenge von $S$ .