Voimakkaasti säännöllinen kaavio - Strongly regular graph

Paley kaavio järjestyksessä 13, voimakkaasti säännöllisesti kuvaajan parametrien srg (13,6,2,3).

Vuonna Graafiteoria , eli voimakkaasti säännöllinen graafi määritellään seuraavasti. Olkoon G = ( V , E ) säännöllinen graafi, jossa on v- kärkipisteet ja aste k . G: n sanotaan olevan voimakkaasti säännöllinen, jos on myös kokonaislukuja λ ja μ siten, että:

• Jokaisella kahdella vierekkäisellä kärjellä on λ yhteisiä naapureita.
• Jokaisella kahdella vierekkäisellä kärjellä on μ yhteistä naapuria.

Tällaisen kuvaajan sanotaan joskus olevan srg ( v , k , λ, μ). RC Bose esitteli voimakkaasti säännölliset kaaviot vuonna 1963.

Jotkut kirjoittajat sulkevat pois grafiikat, jotka täyttävät määritelmän triviaalisesti, nimittäin ne kaaviot, jotka ovat yhden tai useamman yhtä suurikokoisen täydellisen kuvaajan ja niiden täydennysten , täydelliset moniosaiset kaaviot, joissa on yhtä suuret itsenäiset joukot.

Myös srg: n komplementti ( v , k , λ, μ) on voimakkaasti säännöllinen. Se on srg ( v , v − k −1, v −2−2 k + μ, v −2 k + λ).

Voimakkaasti säännöllinen kaavio on etäisyydeltä säännöllinen käyrä, jonka halkaisija on 2 aina, kun μ ei ole nolla. Se on paikallisesti lineaarinen kaavio aina, kun λ = 1.

Ominaisuudet

Parametrien suhde

Srg: n neljä parametria ( v , k , λ, μ) eivät ole riippumattomia, ja niiden on noudatettava seuraavaa suhdetta:

${\ displaystyle (vk-1) \ mu = k (k- \ lambda -1)}$

Yllä oleva suhde voidaan johtaa hyvin helposti laskentaperusteen avulla seuraavasti:

1. Kuvittele, että kaavion kärjet ovat kolmella tasolla. Valitse mikä tahansa kärki juureksi tasolle 0. Sitten sen k naapurit ovat tasolla 1 ja kaikki muut kärjet ovat tasolla 2.
2. Tason 1 kärkipisteet ovat suoraan yhteydessä juuriin, joten niillä on oltava λ muita yhteisiä naapureita juuren kanssa, ja näiden yhteisten naapureiden on oltava myös tasolla 1. Koska jokaisella kärjellä on k- aste , kullekin tasolle 1 on jäljellä reunoja solmua yhteyden muodostamiseksi tason 2 solmuihin. Siksi tason 1 ja tason 2 välillä on reunoja.${\ displaystyle k- \ lambda -1}$${\ displaystyle k \ kertaa (k- \ lambda -1)}$
3. Tason 2 kärjet eivät ole suoraan yhteydessä juuriin, joten niillä on oltava μ yhteisiä naapureita juuren kanssa, ja kaikkien näiden yhteisten naapureiden on oltava tasolla 1. Tasolla 2 on pisteitä, ja kukin on liitetty tason μ solmuihin 1. Siksi reunojen lukumäärä tasojen 1 ja 2 välillä on .${\ displaystyle (vk-1)}$${\ displaystyle (vk-1) \ kertaa \ mu}$
4. Yhtälö tasojen 1 ja 2 välisten reunojen kaksi lauseketta, suhde seuraa.

Adjacency Matrix

Anna I : llä identiteettimatriisi ja anna J tarkoittavat ykkösmatriisi , molemmat matriisit tilauksen vastaan . Vierusmatriisi on voimakkaasti säännöllisesti kaavio täyttää kaksi yhtälöä. Ensimmäinen:

${\ displaystyle AJ = JA = kJ,}$

mikä on triviaali uudelleen säännöllisyysvaatimus. Tämä osoittaa, että k on rinnakkaismatriisin ominaisarvo all-one-ominaisvektorin kanssa. Toinen on asteen yhtälö,

${\ displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}$

mikä ilmaisee vahvaa säännöllisyyttä. Ij : s elementti vasemmalla puolella on se määrä kaksivaiheisen polkuja i ja j . RHS: n ensimmäinen termi antaa itsepolkujen lukumäärän i: stä i: ään , ts. K reunaa ulos ja sisään. Toinen termi antaa kaksivaiheisten polkujen määrän, kun i ja j ovat suoraan yhteydessä. Kolmas termi antaa vastaavan arvon, kun i ja j eivät ole yhteydessä toisiinsa. Koska nämä kolme tapausta sulkevat toisensa pois ja ovat tyhjentäviä , seuraa yksinkertainen additiivinen tasa-arvo.

Vastaavasti kaavio, jonka vierekkäisyysmatriisi täyttää molemmat yllä olevat ehdot ja joka ei ole täydellinen tai tyhjä kaavio, on voimakkaasti säännöllinen kaavio.

Ominaisarvot

Kaavion vierekkäisyysmatriisissa on tarkalleen kolme ominaisarvoa :

• k , jonka moninkertaisuus on 1 (kuten yllä nähtiin)
• ${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ , \ oikea],}$ jonka moninaisuus on ${\ displaystyle {\ frac {1} {2}} \ vasen [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ oikea]}$
• ${\ displaystyle {\ frac {1} {2}} \ vasen [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ , \ oikea],}$ jonka moninaisuus on ${\ displaystyle {\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {\ sqrt {(\ lambda - \ mu ) ^ {2} +4 (k- \ mu)}}} \ oikea]}$

Koska kerrannaisuuksien on oltava kokonaislukuja, niiden lausekkeet rajoittavat v: n , k: n , μ : n ja λ : n arvoja , jotka liittyvät ns. Kerin-olosuhteisiin .

Voimakkaasti säännölliset kaaviot, joilla on kokonaislukuominaisarvot, joilla on eriarvoiset kerrannaisuudet. ${\ displaystyle 2k + (v-1) (\ lambda - \ mu) \ neq 0}$

Voimakkaasti säännölliset kaaviot, joita kutsutaan neuvottelugrafiikoiksi, koska ne ovat yhteydessä symmetrisiin kokousmatriiseihin . Niiden parametrit pienenevät arvoon ${\ displaystyle 2k + (v-1) (\ lambda - \ mu) = 0}$

${\ displaystyle {\ text {srg}} {\ iso (} v, {\ tfrac {1} {2}} (v-1), {\ tfrac {1} {4}} (v-5), { \ tfrac {1} {4}} (v-1) {\ iso)}.}$

Päinvastoin, yhdistetty säännöllinen kaavio, jossa on vain kolme ominaisarvoa, on voimakkaasti säännöllinen.

Esimerkkejä

• Sykli , jonka pituus on 5 on srg (5, 2, 0, 1).
• Petersen kaavio on srg (10, 3, 0, 1).
• Clebsch kaavio on srg (16, 5, 0, 2).
• Shrikhande kaavio on srg (16, 6, 2, 2), joka ei ole etäisyys-transitiivisia kuvaaja .
• N  x  n neliö torni on kaavio , eli linja kuvaaja tasapainottavat täydellinen kaksijakoinen verkko K _{n, n} , on srg ( n ² , 2 n  - 2, n  - 2, 2). Parametrit n = 4: lle ovat yhteneviä Shrikhande-kuvaajan parametrien kanssa, mutta nämä kaksi kuvaajaa eivät ole isomorfisia.
• Viivadiagrammi täydellisen kaavio K _n on srg ( ).${\ displaystyle {\ binom {n} {2}}, 2 (n-2), n-2,4}$
• Chang kuvaajat ovat srg (28, 12, 6, 4), on sama kuin linjan kuvaaja K ₈ , mutta nämä neljä kuvaajaa ei isomorfinen.
• Viivadiagrammi on yleisen nelikulmio GQ (2, 4) on srg (27, 10, 1, 5). Itse asiassa jokainen yleistetty järjestyksen (s, t) nelikulmio antaa tällä tavoin voimakkaasti säännöllisen kuvaajan: nokkeluuteen, srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
• Schläfli kaavio on srg (27, 16, 10, 8).
• Hoffman-Singleton kuvaaja on srg (50, 7, 0, 1).
• Sims-Gewirtz kuvaaja on (56, 10, 0, 2).
• M22 kaavio eli Mesner kaavio on srg (77, 16, 0, 4).
• Brouwer-Haemers kuvaaja on srg (81, 20, 1, 6).
• Higman-Sims kuvaaja on srg (100, 22, 0, 6).
• Paikallinen McLaughlin kaavio on srg (162, 56, 10, 24).
• Cameron kaavio on srg (231, 30, 9, 3).
• Berlekamp-van Nukkaantumaton Seidel kuvaaja on srg (243, 22, 1, 2).
• McLaughlin kaavio on srg (275, 112, 30, 56).
• Paley kaavio järjestyksen q on srg ( q , ( q  - 1) / 2, ( q  - 5) / 4, ( q  - 1) / 4). Pienin Paley-käyrä, jonka q = 5, on 5-sykli (yllä).
• itse täydentävät kaari-transitiiviset kaaviot ovat voimakkaasti säännöllisiä.

Vahvasti säännöllistä kuvaajaa kutsutaan primitiiviseksi, jos sekä käyrä että sen komplementti ovat yhteydessä toisiinsa. Kaikki yllä olevat graafit ovat primitiivisiä, koska muuten μ = 0 tai λ = k.

Conwayn 99-graafinen ongelma pyytää rakentamaan srg: n (99, 14, 1, 2). Ei tiedetä, onko näiden parametrien kaavio olemassa, ja John Horton Conway on tarjonnut 1000 dollarin palkinnon tämän ongelman ratkaisusta.

Kolmiosta vapaat kaaviot, Moore-kaaviot ja geodeettiset kaaviot

Voimakkaasti säännölliset kaaviot, joissa λ = 0, ovat kolmiovapaita . Lukuun ottamatta täydellisiä kaavioita alle kolmella kärjellä ja kaikkia täydellisiä kahdenvälisiä kuvaajia, seitsemän yllä lueteltua (viisikulmio, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 ja Higman-Sims) ovat ainoat tunnetut. Voimakkaasti säännölliset kaaviot, joissa λ = 0 ja μ = 1, ovat Moore-graafit, joiden ympärysmitta on 5. Jälleen kolme edellä esitettyä kuvaajaa (viisikulmio, Petersen ja Hoffman-Singleton), parametreilla (5, 2, 0, 1), (10, 3, 0, 1) ja (50, 7, 0, 1) ovat ainoat tunnetut. Ainoa muu mahdollinen parametrijoukko, jolla saadaan Moore-kaavio, on (3250, 57, 0, 1); ei tiedetä, onko tällainen kaavio olemassa, ja jos on, onko se ainutlaatuinen vai ei.

Jokainen voimakkaasti säännöllinen kaavio, jossa on geodeettinen kaavio , on graafi, jossa jokaisella kahdella kärjellä on ainutlaatuinen painottamaton lyhin polku . Ainoat tunnetut voimakkaasti säännölliset kaaviot ovat Moore-kuvaajat. Tällaisen kuvaajan ei ole mahdollista , mutta muita parametrien yhdistelmiä, kuten (400, 21, 2, 1), ei ole vielä suljettu pois. Huolimatta käynnissä olevasta tutkimuksesta ominaisuuksista, joita voimakkaasti säännöllisen kuvaajan kanssa olisi, ei tiedetä, onko niitä enää olemassa tai edes onko niiden lukumäärä rajallinen. ${\ displaystyle \ mu = 1}$${\ displaystyle \ mu = 1}$${\ displaystyle \ lambda = 1}$${\ displaystyle \ mu = 1}$

Katso myös

• Osittainen geometria
• Seidel-vierekkäisyysmatriisi
• Kaksikaavio

Huomautuksia

Viitteet

• AE Brouwer, AM Cohen ja A. Neumaier (1989), Etäisyyden säännölliset kaaviot . Berliini, New York: Springer-Verlag. ISBN  3-540-50619-5 , ISBN  0-387-50619-5
• Chris Godsil ja Gordon Royle (2004), algebrallinen graafiteoria . New York: Springer-Verlag. ISBN  0-387-95241-1

Ulkoiset linkit

• Eric W.Weisstein , Mathworld-artikkeli lukuisilla esimerkeillä.
• Gordon Royle , Luettelo suuremmista kaavioista ja perheistä.
• Andries E.Brouwer , voimakkaasti säännöllisten kuvaajien parametrit.
• Brendan McKay , Jotkut kuvaajakokoelmat.
• Ted Spence , voimakkaasti säännölliset kaaviot enintään 64 kärjessä.