Inzidenzgraph
Als Inzidenzgraph oder Levi-Graph bezeichnet man in der Mathematik eine kombinatorische Struktur, die die Inzidenzen eines Blockplans oder 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 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
Die projektive Ebene über dem Körper 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)
Auf dieser Seite verwendete Medien
Fano plane binpoints.svg
Autor/Urheber: KlioKlein, Lizenz: CC BY-SA 3.0
Die projektive Fano-Ebene, visualisiert als gleichseitiges Dreieck mit Inkreis und Winkelhalbierenden. Die Dreiecksseiten, der Inkreis und die Winkelhalbierenden sind die 7 projektiven Geraden der Ebene, deren 7 Schnittpunkte, in denen sich immer genau drei dieser Geraden treffen, sind die 7 Punkte der Ebene. Die Ebene lässt sich als P^2(Z/2Z) mit dem Koordinatenvektorraum K^3 versehen, wobei K=Z/2Z der Körper mit 2 Elementen ist. Die in der Zeichnung angegebenen Punktkoordinaten sind die binären Abkürzungen für die Koordinatenvektoren, die den projektiven Punkt in K^3 erzeugen. Z.B. steht 011 für den Vektor (0,1,1).
Autor/Urheber: KlioKlein, Lizenz: CC BY-SA 3.0
Die projektive Fano-Ebene, visualisiert als gleichseitiges Dreieck mit Inkreis und Winkelhalbierenden. Die Dreiecksseiten, der Inkreis und die Winkelhalbierenden sind die 7 projektiven Geraden der Ebene, deren 7 Schnittpunkte, in denen sich immer genau drei dieser Geraden treffen, sind die 7 Punkte der Ebene. Die Ebene lässt sich als P^2(Z/2Z) mit dem Koordinatenvektorraum K^3 versehen, wobei K=Z/2Z der Körper mit 2 Elementen ist. Die in der Zeichnung angegebenen Punktkoordinaten sind die binären Abkürzungen für die Koordinatenvektoren, die den projektiven Punkt in K^3 erzeugen. Z.B. steht 011 für den Vektor (0,1,1).
Heawood graph 2COL.svg
Autor/Urheber: Koko90, Lizenz: CC BY-SA 3.0
The chromatic number of the Heawood graph is 2. Layout from LCF with Graphviz (and GAP + GRAPE + G-GRAPE).
Autor/Urheber: Koko90, Lizenz: CC BY-SA 3.0
The chromatic number of the Heawood graph is 2. Layout from LCF with Graphviz (and GAP + GRAPE + G-GRAPE).