Hrabě Levy

Levyho graf (též incidenční graf ) je bipartitní graf odpovídající struktuře incidence [1] [2] . Ze sady bodů a čar v geometrii dopadu nebo projektivní konfiguraci se vytvoří graf s jedním vrcholem pro každý bod, jedním vrcholem pro každou čáru a jednou hranou pro každý bod a dopad čáry (tj. „bod leží na čárový" vztah). Tato hrabata byla pojmenována po Friedrichu Levim, který je popsal v roce 1942 [1] [3] .

Leviho graf soustavy bodů a čar má obvykle obvod alespoň šest: každý cyklus délky 4 musí odpovídat dvěma úsečkám procházejícím stejnými dvěma body. Proto každý bipartitní graf s obvodem alespoň šest může být považován za Leviho graf abstraktní struktury incidence [1] . Levi grafy konfigurací jsou biregulárnía každý biregulární graf s obvodem alespoň šest může být považován za Leviho graf abstraktní konfigurace [4] .

Levyho grafy lze také definovat pro jiné typy incidenčních struktur, jako jsou dopady mezi body a rovinami v euklidovském prostoru . Pro jakýkoli graf Levi existuje ekvivalentní hypergraf a naopak.

Příklady

• Desarguesův graf je Leviho graf konfigurace Desargues , sestávající z 10 bodů a 10 čar. Na každé přímce jsou 3 body a každým bodem procházejí 3 čáry. Na Desarguesův graf lze také nahlížet jako na zobecněný Petersenův graf G (10,3) nebo jako bipartitní Kneserův graf s parametry 5,2. Jedná se o 3-běžný graf s 20 vrcholy.

• Heawoodův graf je Leviho graf Fanovy roviny . Také známý jako (3,6) -cell , je to 3-běžný graf se 14 vrcholy.

• Möbius–Cantorův graf je Lévyho graf Möbius–Cantorovy konfigurace , systém 8 bodů a 8 čar, které nelze realizovat pomocí přímek na euklidovské rovině. Je to 3-běžný graf a má 16 vrcholů.

• Pappusův graf je Leviho graf konfigurace Pappus sestávající z 9 bodů a 9 čar. Stejně jako v konfiguraci Desargues jsou na každém řádku 3 body a každým bodem procházejí 3 čáry. Graf je 3-pravidelný a má 18 vrcholů.

• Grayův graf je Leviho graf konfigurace, kterou lze získat v R 3 jako mřížku 3×3×3 27 bodů a 27 ortogonálních čar procházejících těmito body.

• 8článková Thatta je Leviho graf konfigurace Cremona-Richmond . Graf, známý také jako (3,8)-buňka, je 3-pravidelný a má 30 vrcholů.

• Graf čtyřrozměrné hyperkrychle Q 4 je Leviho graf Möbiovy konfigurace tvořený body a rovinami dvou vzájemně vepsaných čtyřstěnů. Zde je čtyřstěn považován za vepsaný do jiného, ​​pokud všechny jeho vrcholy leží na rovinách procházejících stěnami jiného čtyřstěnu (ne nutně na stěnách samotných).

• Ljubljanský graf se 112 vrcholy je Lévyho graf lublaňské konfigurace [5] .

Poznámky

1. ↑ 1 2 3 Branko Grünbaum. Coxeter Legacy. - Providence, RI: American Mathematical Society, 2006. - S. 179-225. Viz zejména str. 181 Archivováno 1. dubna 2018 na Wayback Machine .
2. ↑ Burkard Polster. Kniha s geometrickými obrázky. - New York: Springer-Verlag, 1998. - S. 5. - (Universitex). — ISBN 0-387-98437-2 . - doi : 10.1007/978-1-4419-8526-2 .
3. ↑ FW Levi. Konečné geometrické systémy. — Kalkata: Univerzita v Kalkatě, 1942.
4. ↑ Haraldova skupina. Příručka kombinatorických návrhů / Charles J. Colbourn, Jeffrey H. Dinitz. - Druhý. - Chapman & Hall / CRC, Boca Raton, FL, 2007. - S. 353-355. - (Diskrétní matematika a její aplikace (Boca Raton)).
5. ↑ M. Conder, A. Malnič, D. Marušič, T. Pisanski, Z. Potočnik. Lublaňský graf . — Univerzita v Lublani Katedra matematiky, 2002.

Odkazy

• Weisstein, Eric W. Levi Graph  (anglicky) na webových stránkách Wolfram MathWorld .