Kubischer Graph

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 nichttrivalen Fälle regulärer Graphen.

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