Kubischer Graph

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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
Commons: 3-regular graphs – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Folge A005638 in OEIS
  2. Folge A002851 in OEIS