Leitergraph

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

Ein Leitergraph (englisch ladder graph) ist in der Graphentheorie eine Klasse von Graphen mit der Struktur einer Leiter. Ein Leitergraph besteht aus zwei linearen Graphen gleicher Länge (die Holme), wobei je zwei einander entsprechende Knoten durch eine Kante (die Sprossen) miteinander verbunden sind. Jeder Leitergraph ist das kartesische Produkt zweier linearer Graphen, von denen einer genau eine Kante hat, und damit ein spezieller Gittergraph.

Definition[Bearbeiten | Quelltext bearbeiten]

Ein Leitergraph ist ein ungerichteter Graph bestehend aus den Knoten

und den Kanten

.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

2-Färbung eines Leitergraphen

Ein Leitergraph ist das kartesische Produkt

der beiden linearen Graphen und und damit ein spezieller Gittergraph .

Weitere Eigenschaften sind:

Zyklische Erweiterungen[Bearbeiten | Quelltext bearbeiten]

Zwei Ansichten eines Möbius-Leitergraphen

Werden in einem Leitergraphen zudem der erste und der vorletzte sowie der zweite und der letzte Knoten jeweils durch eine zusätzliche Kante miteinander verbunden, bildet man also

,

dann erhält man einen zyklischen Leitergraph (englisch circular ladder graph) . Ein zyklischer Leitergraph ist das kartesische Produkt eines linearen Graphen mit einem Kreisgraphen und damit für 3-regulär. Zyklische Leitergraphen sind die Polyedergraphen von Prismen und werden daher auch Prismengraphen (englisch prism graphs) genannt.

Werden die vier Knoten stattdessen kreuzweise miteinander verbunden, bildet man also

,

erhält man als Graph einen sogenannten Möbiusleitergraph (englisch Möbius ladder graph) , der an ein Möbiusband erinnert und ebenfalls 3-regulär ist. Möbiusleitergraphen sind für nicht mehr planar und weisen einige interessante graphentheoretische Eigenschaften auf.[2]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Commons: Ladder graphs – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Ralph Grimaldi: Fibonacci and Catalan Numbers: An Introduction. John Wiley & Sons, 2012, ISBN 1-118-15976-4, S. 64.
  2. Jonathan L. Gross: Combinatorial Methods With Computer Applications (= Discrete Mathematics and its Applications. Band 54). CRC Press, 2008, ISBN 1-58488-743-5, S. 376–377.