Ungerichtete Graphen/Konstruktionen/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Zu einem Graphen nennt man den Graphen den komplementären Graphen (oder Komplementärgraph). Er wird mit bezeichnet.

Es wird also die Knotenmenge übernommen und eine zweielementige Teilmenge 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 Punkte und Kanten besitzt, so besitzt gerade Kanten. Der komplementäre Graph des komplementären Graphes ist wieder der Ausgangsgraph, also .


Definition  

Zu einem Graphen und einer Teilmenge der Kantenmenge versteht man unter denjenigen Graphen, dessen Punktemenge ist und dessen Kantenmenge aus besteht.

Für schreibt man abkürzend für .

Line graph construction 1.svg
Line graph construction 2.svg
Line graph construction 3.svg
Line graph construction 4.svg


Definition  

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


Beispiel  

Der Kantengraph zu einem Sterngraph mit Punkten, also einem Zentrum mit daran anliegenden Blättern, ist ein vollständiger Graph mit Punkten.




Lemma  

Es sei ein Graph und der zugehörige Kantengraph. Dann gelten folgende Aussagen.

  1. Die Anzahl der Punkte von ist gleich der Anzahl der Kanten von .
  2. Der Grad eines Punktes von (also einer Kante von ) ist
  3. Die Anzahl der Kanten von ist

Beweis  

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

    da in der mittleren Summe der Term so oft vorkommt, wie es angibt.