Als Inzidenzgraph oder Levi-Graph bezeichnet man in der Mathematik eine kombinatorische Struktur, die die Inzidenzen eines Blockplans oder einer projektiven Ebene kodiert.
Definition Bearbeiten
Sei eine Inzidenzstruktur aus einer Menge von „Punkten“ und „Blöcken“ (oder „Geraden“) , dann wird ihr Inzidenzgraph konstruiert als bipartiter Graph mit Knotenmenge , in dem zwei Knoten und genau dann durch eine Kante verbunden werden, wenn gilt.
Beispiel Bearbeiten
Die projektive Ebene über dem Körper ist die Fano-Ebene mit 7 Punkten und 7 Geraden. Ihr Inzidenzgraph ist der Heawood-Graph.
Literatur Bearbeiten
- 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 Bearbeiten
- Wolfram MathWorld: Incidence Graph (mit einer Auflistung der Inzidenzgraphen wichtiger Inzidenzstrukturen)