Ungerichtete Graphen/Konstruktionen/Einführung/Textabschnitt

Definition

Zu einem Graphen ${}G=(V,E)$ nennt man den Graphen ${}(V,{\mathfrak {P}}_{2}\,(V)\setminus E)$ den komplementären Graphen (oder Komplementärgraph). Er wird mit ${}G^{c}$ bezeichnet.

Es wird also die Knotenmenge übernommen und eine zweielementige Teilmenge ${}\{u,v\}$ ist genau dann eine Kante des komplementären Graphen, wenn sie keine Kante des Ausgangsgraphen ist. Dabei entsprechen sich der vollständige Graph und der kantenfreie Graph. Wenn ${}G$ ${}n$ Punkte und ${}m$ Kanten besitzt, so besitzt ${}G^{c}$ gerade ${}{\binom {n}{2}}-m$ Kanten. Der komplementäre Graph des komplementären Graphes ist wieder der Ausgangsgraph, also ${}{\left(G^{c}\right)}^{c}=G$.

Definition

Zu einem Graphen ${}G=(V,E)$ und einer Teilmenge ${}F\subseteq E$ der Kantenmenge versteht man unter ${}G\setminus F$ denjenigen Graphen, dessen Punktemenge ${}V$ ist und dessen Kantenmenge aus ${}E\setminus F$ besteht.

Für ${}F=\{e\}$ schreibt man abkürzend ${}G\setminus e$ für ${}G\setminus \{e\}$.

Definition

Es sei ${}G=(V,E)$ ein Graph. Man nennt denjenigen Graphen, dessen Knotenmenge die Kantenmenge ${}E$ von ${}G$ ist und bei dem zwei Knoten ${}L_{1}$ und ${}L_{2}$ (also Kanten aus ${}G$) genau dann durch eine Kante verbunden werden, wenn ${}L_{1}$ und ${}L_{2}$ einen gemeinsamen Punkt in ${}V$ besitzen, den Kantengraphen zu ${}G$.

Beispiel

Der Kantengraph zu einem Sterngraph mit ${}n+1$ Punkten, also einem Zentrum mit daran anliegenden ${}n$ Blättern, ist ein vollständiger Graph mit ${}n$ Punkten.

Lemma

Es sei ${}G=(V,E)$ ein Graph und ${}K$ der zugehörige Kantengraph. Dann gelten folgende Aussagen.

1. Die Anzahl der Punkte von ${}K$ ist gleich der Anzahl der Kanten von ${}G$.
2. Der Grad eines Punktes ${}\{u,v\}$ von ${}K$ (also einer Kante von ${}G$) ist

   $d(u)+d(v)-2.$

3. Die Anzahl der Kanten von ${}K$ ist

   ${\frac {1}{2}}\sum _{v\in V}d(v)(d(v)-1).$

Beweis

1. Dies folgt unmittelbar aus der Definition des Kantengraphen.
2. Es sei ${}\{u,v\}$ eine Kante von ${}G$, aufgefasst als Punkt im Kantengraph ${}K$. Dieser Punkt ist mit einem anderen Punkt des Kantengraphen, also einer Kante ${}\{r,s\}$ des Ausgangsgraphen, genau dann verbunden, wenn diese Kante an ${}u$ oder an ${}v$ anliegt, wobei nur eines der Fall sein kann. Die Anzahl der an ${}u$ anliegenden Kanten ist ${}d(u)$, allerdings dürfen wir die Kante ${}\{u,v\}$ nicht mitzählen.
3. Nach Fakt ist die gesuchte Anzahl der Kanten in ${}K$ unter Verwendung von Teil (2) gleich

   ${\frac {1}{2}}\sum _{\{u,v\}\in E}{\left(d(u)+d(v)-2\right)}={\frac {1}{2}}\sum _{\{u,v\}\in E}{\left(d(u)-1+d(v)-1\right)}={\frac {1}{2}}\sum _{v\in V}d(v)(d(v)-1)\,,$

   da in der mittleren Summe der Term ${}d(v)-1$ so oft vorkommt, wie es ${}d(v)$ angibt.

$\Box$