Kreivi Levy

Levy-graafi (myös ilmaantuvuusgraafi ) on ilmaantuvuusrakennetta vastaava kaksiosainen graafi [1] [2] . Pisteiden ja viivojen joukosta tulogeometriassa tai projektitiivisessa konfiguraatiossa muodostetaan kuvaaja, jossa on yksi kärki kullekin pisteelle, yksi kärki kullekin suoralle ja yksi reuna jokaiselle pisteelle ja viivan tulolle (eli "piste sijaitsee rivi"-suhde). Nämä kreivit on nimetty Friedrich Levin mukaan, joka kuvaili niitä vuonna 1942 [1] [3] .

Piste- ja suorajärjestelmän Levi-graafin ympärysmitta on yleensä vähintään kuusi: minkä tahansa syklin , jonka pituus on 4, tulee vastata kahta saman kahden pisteen kautta kulkevaa suoraa. Siksi mitä tahansa kaksiosaista graafia, jonka ympärysmitta on vähintään kuusi, voidaan pitää abstraktin esiintymisrakenteen Levi-graafina [1] . Konfiguraatioiden Levi-kaaviot ovat kaksinkertaisiaja mitä tahansa kaksisäännöllistä kuvaajaa, jonka ympärysmitta on vähintään kuusi, voidaan pitää abstraktin konfiguraation Levi-graafina [4] .

Levy-graafit voidaan määrittää myös muun tyyppisille insidenssirakenteille, kuten pisteiden ja tasojen välisille tuloille euklidisessa avaruudessa . Jokaiselle Levi-graafille on olemassa vastaava hypergraafi ja päinvastoin.

Esimerkkejä

• Desargues-graafi on Desargues-konfiguraation Levi- graafi , joka koostuu 10 pisteestä ja 10 viivasta. Jokaisella viivalla on 3 pistettä ja kunkin pisteen läpi kulkee 3 viivaa. Desargues-graafia voidaan tarkastella myös yleistettynä Petersen-graafina G (10,3) tai kaksiosaisena Kneser-graafina parametreilla 5,2. Se on 3-säännöllinen graafi, jossa on 20 kärkeä.

• Heawood-graafi on Fanon tason Levi-graafi . Tunnetaan myös nimellä (3,6) -solu , se on 3-säännöllinen graafi, jossa on 14 kärkeä.

• Möbius–Cantor-graafi on Möbius–Cantor-konfiguraation Lévy-graafi , 8 pisteen ja 8 viivan järjestelmä, jota ei voida toteuttaa suorilla viivoilla euklidisella tasolla. Se on 3-säännöllinen graafi ja siinä on 16 kärkeä.

• Pappus -graafi on Pappus-konfiguraation Levi-graafi , joka koostuu 9 pisteestä ja 9 viivasta. Kuten Desargues-kokoonpanossa, jokaisella rivillä on 3 pistettä ja kunkin pisteen läpi kulkee 3 viivaa. Graafi on 3-säännöllinen ja siinä on 18 kärkeä.

• Gray -graafi on Levi-graafi konfiguraatiosta, joka voidaan saada R3 :ssa 27 pisteen 3 ×3×3 hilana ja 27 ortogonaalista viivaa näiden pisteiden läpi.

• 8-soluinen Thatta on Cremona-Richmond-konfiguraation Levi-kaavio . Graafi, joka tunnetaan myös nimellä (3,8)-solu, on 3-säännöllinen ja siinä on 30 kärkeä.

• Neliulotteisen hyperkuution Q 4 kuvaaja on Möbius-konfiguraation Levi -graafi, joka muodostuu kahden toisiinsa merkityn tetraedrin pisteistä ja tasoista. Tässä tetraedrin katsotaan piirretyksi toiseen, jos kaikki sen kärjet sijaitsevat tasoilla, jotka kulkevat toisen tetraedrin pintojen läpi (ei välttämättä itse pinnoilla).

• 112 - pisteinen Ljubljana-graafi on Ljubljana-konfiguraation Lévy-graafi [5] .

Muistiinpanot

1. ↑ 1 2 3 Branko Grünbaum. Coxeterin perintö. - Providence, RI: American Mathematical Society, 2006. - P. 179-225. Katso erityisesti s. 181 Arkistoitu 1. huhtikuuta 2018 Wayback Machinessa .
2. ↑ Burkard Polster. Geometrinen kuvakirja. - New York: Springer-Verlag, 1998. - P. 5. - (Universitex). — ISBN 0-387-98437-2 . - doi : 10.1007/978-1-4419-8526-2 .
3. ↑ FW Levi. Äärilliset geometriset järjestelmät. - Kalkutta: Kalkutan yliopisto, 1942.
4. ↑ Harald Group. Kombinatorisen suunnittelun käsikirja / Charles J. Colbourn, Jeffrey H. Dinitz. — Toiseksi. - Chapman & Hall / CRC, Boca Raton, FL, 2007. - P. 353-355. - (Diskreetti matematiikka ja sen sovellukset (Boca Raton)).
5. ↑ M. Conder, A. Malnič, D. Marušič, T. Pisanski, Z. Potočnik. Ljubljanan kaavio . — Ljubljanan yliopiston matematiikan laitos, 2002.

Linkit

• Weisstein, Eric W. Levi Graph  (englanniksi) Wolfram MathWorld -verkkosivustolla .