Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Spezielle Klassen von Graphen

Endliche Graphen besitzen eine endliche Knotenmenge und eine endliche Kantenmenge. Anderenfalls werden die Graphen unendlich genannt.
In regulären Graphen vom Grad r haben alle Knoten den Grad
Ein ungerichteter schlichter Graph mit der Knotenmenge heißt vollständiger Graph , wenn je zwei verschiedene Knoten aus durch eine Kante verbunden sind. Ein vollständiger Graph mit -elementiger Knotenmenge wird mit bezeichnet.
Kann man die Knotenmenge eines ungerichteten schlichten Graphen in zwei disjunkte Klassen und zerlegen, so daß jede Kante von einen Knoten aus mit einem Knoten aus verbindet, dann heißt ein paarer Graph .
Ein paarer Graph wird vollständiger paarer Graph genannt, wenn jeder Knoten aus mit jedem Knoten aus durch eine Kante verbunden ist. Ist eine -elementige und eine -elementige Menge, dann wird der Graph mit bezeichnet.

Beispiel

Die linke Abbildung zeigt einen vollständigen Graphen mit 5 Knoten.



Beispiel

Die rechte Abbildung zeigt einen vollständigen paaren Graphen mit 2-elementiger Knotenmenge und 3-elementiger Knotenmenge

Weitere spezielle Klassen von Graphen sind ebene Graphen , Bäume und Transportnetze . Ihre Eigenschaften werden jeweils in einem der folgenden Abschnitte angegeben.