Leviho graf - Levi graph

Leviho graf
The Pappusův graf, graf Levi s 18 vrcholy vytvořenými z Konfigurace Pappus. Vrcholy označené jednoduchými písmeny odpovídají bodům v konfiguraci; vrcholy označené třemi písmeny odpovídají čarám procházejícím třemi body.
Obvod	≥ 6
Tabulka grafů a parametrů

v kombinatorická matematika, a Leviho graf nebo graf výskytu je bipartitní graf spojené s struktura výskytu.^[1][2] Ze sbírky bodů a čar v an geometrie dopadu nebo a projektivní konfigurace, vytvoříme graf s jedním vrcholem na bod, jedním vrcholem na čáru a hranou pro každý výskyt mezi bodem a přímkou. Jsou pojmenovány pro Friedrich Wilhelm Levi, který o nich psal v roce 1942.^[1][3]

Leviho graf systému bodů a čar obvykle má obvod alespoň šest: Jakékoli 4cykly odpovídá dvěma liniím ve stejných dvou bodech. Naopak jakýkoli bipartitní graf s obvodem nejméně šesti lze považovat za Leviho graf abstraktní struktury dopadu.^[1] Levi grafy konfigurací jsou biregular a každý biregulární graf s obvodem nejméně šesti lze považovat za Leviho graf abstraktní konfigurace.^[4]

Leviho grafy lze definovat také pro jiné typy struktury dopadů, jako jsou výskyty mezi body a rovinami v Euklidovský prostor. Pro každý graf Levi existuje ekvivalent hypergraf a naopak.

Příklady

• The Desargues graf je Leviho graf Odstraňuje konfiguraci, složený z 10 bodů a 10 řádků. Na každém řádku jsou 3 body a každý bod prochází 3 řádky. Graf Desargues lze také zobrazit jako zobecněný Petersenův graf G (10,3) nebo bipartitní Kneserův graf s parametry 5,2. Je 3-pravidelný s 20 vrcholy.
• The Heawoodův graf je Leviho graf Fano letadlo. Je také známý jako (3,6) -klec, a je 3-pravidelný se 14 vrcholy.
• The Möbius – Kantorův graf je Leviho graf Konfigurace Möbius – Kantor, systém 8 bodů a 8 čar, které nelze realizovat přímkami v euklidovské rovině. Je 3-pravidelný s 16 vrcholy.
• The Pappusův graf je Leviho graf Konfigurace Pappus, složený z 9 bodů a 9 řádků. Stejně jako konfigurace Desargues existují 3 body na každé linii a 3 linie procházející každým bodem. Je 3 pravidelný s 18 vrcholy.
• The Šedý graf je Leviho graf konfigurace, kterou lze realizovat v ${ displaystyle mathbb {R} ^ {3}}$ jako ${ displaystyle 3 krát 3 krát 3}$ mřížka 27 bodů a 27 kolmých čar skrz ně.
• The Tutte osm klec je Leviho graf Konfigurace Cremona – Richmond. Je také známá jako klec (3,8) a je 3 pravidelná s 30 vrcholy.
• Čtyřrozměrný hyperkrychlový graf ${ displaystyle Q_ {4}}$ je Leviho graf Möbiova konfigurace tvořené body a rovinami dvou vzájemně se vyskytujících čtyřstěnů.
• The Lublaňský graf na vrcholech 112 je graf Levi konfigurace Lublaně.^[5]

Reference

externí odkazy

• Weisstein, Eric W. "Levi Graph". MathWorld.