Inzidenzgraph

Als Inzidenzgraph o​der Levi-Graph bezeichnet m​an in d​er Mathematik e​ine kombinatorische Struktur, d​ie die Inzidenzen e​ines Blockplans o​der einer projektiven Ebene kodiert.

Der Inzidenzgraph der Fano-Ebene: rot gefärbte Knoten entsprechen den Punkten und blau gefärbte Knoten den Geraden der unten abgebildeten Fano-Ebene.

Definition

Die Fano-Ebene mit binären Punktnummern (rot), die abkürzend für homogene Koordinaten stehen.

Sei ${\displaystyle (P,B)}$ eine Inzidenzstruktur aus einer Menge von "Punkten" ${\displaystyle P}$ und "Blöcken" (oder "Geraden") ${\displaystyle B}$, dann wird ihr Inzidenzgraph konstruiert als bipartiter Graph mit Knotenmenge ${\displaystyle P\cup B}$, in dem zwei Knoten ${\displaystyle p\in P}$ und ${\displaystyle b\in B}$ genau dann durch eine Kante verbunden werden, wenn ${\displaystyle p\in b}$ gilt.

Beispiel

Die projektive Ebene über dem Körper ${\displaystyle F_{2}}$ ist die Fano-Ebene mit 7 Punkten und 7 Geraden. Ihr Inzidenzgraph ist der Heawood-Graph.

Literatur

• H. S. M. Coxeter: Self-Dual Configurations and Regular Graphs. Bull. Amer. Math. Soc. 56, 413–455, 1950.
• C. Godsil, G. Royle: Incidence Graphs. §5.1 in Algebraic Graph Theory. New York: Springer-Verlag, S. 78–79, 2001.
• T. Pisanski, M. Randić: Bridges between Geometry and Graph Theory. in Geometry at Work:A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., S. 174–194, 2000.

Weblinks

• Wolfram MathWorld: Incidence Graph (mit einer Auflistung der Inzidenzgraphen wichtiger Inzidenzstrukturen)