Kubischer Graph

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

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

Commons: 3-regular graphs – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise

  1. Folge A005638 in OEIS
  2. Folge A002851 in OEIS
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.