Kubischer Graph

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

Ein einfacher Graph heißt in der Graphentheorie kubisch oder 3-regulär, falls alle seine Knoten den Grad 3 besitzen. Kubische Graphen sind damit reguläre Graphen. Da 1-reguläre Graphen lediglich eine Paarung darstellen und 2-reguläre Graphen in disjunkte Zyklen zerfallen, sind kubische Graphen sogesehen die einfachsten nichttrivialen Fälle regulärer Graphen.

Anzahl kubischer Graphen[Bearbeiten | Quelltext bearbeiten]

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

n # Zusammenhängende kubische Graphen mit n Knoten[1] # Kubische Graphen mit n Knoten[2]
2 0 0
4 1 1
6 2 2
8 5 6
10 19 21
12 85 94

Beispiele[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Folge A005638 in OEIS
  2. Folge A002851 in OEIS