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 von einem ungerichteten Graphen. Ein Graph ist nichts anderes als eine symmetrische Relation auf ${}V$. Typischerweise ist die Grundmenge, zu der man auch Knotenmenge oder Punktmenge oder Vertexmenge sagt, endlich, und oft wählt man ${}V={\{1,\ldots ,n\}}$. 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 ${}uv\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 ${}{\mathfrak {P}}_{2}\,(V)$ die Menge aller zweielementigen Teilmengen von ${}V$, bezeichnet, so kann man die Kantenmenge als ${}E\subseteq {\mathfrak {P}}_{2}\,(V)$ auffassen.

Definition

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

${}N(v)={\left\{u\in V\mid \{u,v\}\in E\right\}}\,$

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)=\bigcup _{s\in S}N(s)$ und nennt dies die Nachbarschaftsmenge von ${}S$.