Leiterstränge

Leiterstränge, singular Leiterstrang, ist ein Begriff aus der Graphentheorie, der in der deutschsprachigen Fachliteratur häufig eine ladder-like Struktur bezeichnet. Er bezieht sich typischerweise auf eine Klasse von Graphen, die zwei parallele Pfade durch Querrippen verbinden und dadurch eine Leiterform erzeugen. In der Standarddarstellung besteht ein Leiterstrang L_n aus zwei Reihen von n Vertices, wobei jeder i-te Vertex der oberen Reihe mit dem entsprechenden i-ten Vertex der unteren Reihe durch eine Kante verbunden ist. Formal entspricht L_n dem kartesischen Produkt P_n ☐ K_2. Es enthält 2n Vertices und 3n−2 Kanten; die Kanten umfassen die beiden Pfadkanten und n Querrippen. Der Graph ist planar und bipartit. Die Endknoten haben Grad 2, alle inneren Knoten Grad 3; der Durchmesser wächst linear mit n.

In der Literatur wird der Begriff Leiterstrang häufig als deutsche Bezeichnung für den Ladder-Graph verwendet. Varianten und Verallgemeinerungen umfassen breitere Leiterstränge (mit mehr als zwei parallelen Pfaden) bzw. Verwandte wie die Prism-Graphen. Leiterstränge finden Anwendung in der Kombinatorik, etwa bei der Untersuchung von Zählproblemen für Matchings oder unabhängige Mengen, sowie in der Physik als einfache Modelle quasi-eindimensionaler Systeme (Spin-Laddern). In der Netzwerktheorie dienen sie gelegentlich als einfaches Beispielnetzwerk, zum Beispiel für Widerstandsberechnungen.

Siehe auch: Ladder-Graph, kartesisches Produkt, P_n, Grid-Graph.