Inzidenzgraph
Als Inzidenzgraph oder Levi-Graph bezeichnet man in der Mathematik eine kombinatorische Struktur, die die Inzidenzen eines Blockplans oder einer projektiven Ebene kodiert.
Definition
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)
🔥 Top keywords: Wikipedia:HauptseiteSpezial:SucheFußball-Europameisterschaft 2024Sabine DöringKylian MbappéSpecial:MyPage/toolserverhelferleinconfig.jsAntoine GriezmannRalf RangnickFußball-EuropameisterschaftDomenico TedescoJodie DevosFußball-Europameisterschaft 2021Marko ArnautovićBastian SchweinsteigerDavid AlabaRomelu LukakuListe der größten AuslegerbrückenFußball-Weltmeisterschaft 2022SlowakeiMatija ŠarkićChristoph KramerStraßenbahnunfall in der Grüne (Iserlohn)Fußball-WeltmeisterschaftN’Golo KantéÖsterreichische BundeshymneFußball-Weltmeisterschaft 2026Aufstand vom 17. Juni 1953Der Garten der Finzi ContiniAlmuth SchultMarcel Sabitzer17. JuniDidier DeschampsHauptseiteChatGPTWikipedia:Wiki Loves Earth 2024/DeutschlandUrsula von der LeyenSchmökerJosef FritzlBettina Stark-Watzinger