Kubischer Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Ein einfacher Graph heißt in der Graphentheorie kubisch, falls alle seine Knoten den Grad 3 besitzen. Alternativ nennt man sie auch 3-regulär.

Kubische Graphen sind damit reguläre Graphen. Da 1-regulären Graphen lediglich eine Paarung darstellen und 2-regulären Graphen in disjunkte Zyklen zerfallen, sind kubische Graphen sogesehen die einfachsten nichttrivialen Fälle regulärer Graphen.

Da die Summe der Knotengrade in einfachen Graphen immer gerade sein muss, besitzen kubische Graphen immer gerade Knotenanzahl.