Etäisyys-säännöllinen kaavio

Distance-regular graph ( englanniksi distance-regular graph ) - sellainen säännöllinen graafi , jossa mille tahansa kahdelle ja samalla etäisyydellä toisistaan sijaitseville pisteille on totta, että pisteiden lukumäärä, jotka tulevat ja sijaitsevat samaan aikaan etäisyys kärjestä , riippuu vain kärkien välisestä etäisyydestä ja ; Lisäksi kärkipisteeseen tulevien ja siitä etäisyyden päässä olevien kärkien määrä riippuu myös vain etäisyydestä . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

Etäisyyssäännölliset kaaviot esitteli N. Biggs vuonna 1969 konferenssissa Oxfordissa [1] , vaikka termi itse ilmestyi paljon myöhemmin [2] .

Määritelmä

Etäisyys-säännöllisen graafin määritelmä [3] [4] :

Etäisyyssäännöllinen kuvaaja on suuntaamaton, yhdistetty, rajattu, säännöllinen valenssin ja halkaisijan kuvaaja, jolle seuraava pitää paikkansa. On luonnollisia lukuja $\Gamma =(V,E)$ $k$ $D$

b_{0}=k\quad b_{1},\,\dots \,,\,b_{D-1}\ ,\quad c_{1}=1,\quad c_{2},\ ,\pisteet ,\,c_{D}

siten, että jokaiselle etäisyyden päässä toisistaan olevalle kärkiparille on totta: $(u,v)$ $d(u,v)=j$

(1) kohtaavien ja etäisyyden päässä olevien kärkien lukumäärä on ( )

u

j-1

v

{\displaystyle c_{j))

1\leqslant j\leqslant D

(2) kohtaavien ja etäisyyden päässä olevien kärkien lukumäärä on ( ).

u

j+1

v

b_{j}

0\leqslant j\leqslant D-1

Sitten

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2 },\,\pisteet ,\,c_{D}\end{Bmatrix}}

on kaavion leikkauspisteiden joukko (katso § Leikkauspisteiden joukko ), ja se on leikkauspisteiden lukumäärä , jossa [3] [4] . $\Gamma$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$ ${\displaystyle a_{j}=k-b_{j}-c_{j))$

Joukko risteyksiä

Aluksi termit "leikkausten joukko" ja "leikkausten lukumäärä" otettiin käyttöön kuvaamaan etäisyystransitiivisia kuvaajia [5] [6] [7] .

Olkoon suuntaamaton, yhdistetty, rajoitettu graafi, jonka kaksi kärkeä ovat etäisyyden päässä toisistaan. Kaikki kärkeen tulevat kärjet voidaan jakaa kolmeen joukkoon ja riippuen niiden etäisyydestä kärkeen : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ ${\näyttötyyli j=d(u,v)}$ $w$ $u$ $A$ $B$ $C$ ${\näyttötyyli d(v,w)}$ $v$

\left\{w\in A\colon d(v,w)=j\right\},\quad \left\{w\in B\colon d(v,w)=j+1\right \},\quad \left\{w\in C\colon d(v,w)=j-1\right\}

Jos kuvaaja on etäisyystransitiivinen, niin joukkojen potenssit (kardiaaliluvut) eivät riipu huipuista , vaan riippuvat vain etäisyydestä . Olkoon , missä ovat leikkausnumerot . $\Gamma$ $|A|,\,|B|,\,|C|$ $u, v$ ${\näyttötyyli j=d(u,v)}$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$

Määritämme etäisyystransitiivisen graafin leikkaustaulukon seuraavasti: $\Gamma$

\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\dots &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_ {2}&\pisteet &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\pisteet &b_{d-1}&\ast \\\end{Bmatrix}}

Jos on kaavion valenssi, niin , ja . Lisäksi , silloin leikkaustaulukon kompakti muoto on: $k$ $b_{0}=k$ $c_{0}=0$ $c_{1}=1$ $a_{i}+b_{i}+c_{i}=k$

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2 },\,\pisteet ,\,c_{D}\end{Bmatrix}}

Etäisyyssäännölliset ja etäisyystransitiiviset kuvaajat

Ensi silmäyksellä etäisyyden transitiivinen kuvaaja ja etäisyyden säännöllinen graafi ovat hyvin läheisiä käsitteitä. Itse asiassa jokainen etäisyystransitiivinen graafi on etäisyyssäännöllinen. Niiden luonne on kuitenkin erilainen. Jos etäisyystransitiivinen graafi määritellään graafin symmetrian perusteella automorfismiehdon kautta, niin etäisyyssäännöllinen graafi määritellään sen kombinatorisen säännönmukaisuuden ehdosta [3] .

Etäisyystransitiivisen graafin automorfismin seuraus on sen säännöllisyys. Vastaavasti säännölliselle kaaviolle voidaan määrittää leikkausnumerot . Toisaalta etäisyyssäännöllisellä graafilla on kombinatorinen säännöllisyys, ja sille on myös määritelty leikkausnumerot (katso § Leikkaustaulukko ), mutta tämä ei tarkoita automorfismia [8] [9] .

Graafin etäisyystransitiivisuus tarkoittaa sen etäisyys-säännöllisyyttä, mutta päinvastoin ei pidä paikkaansa [8] . Tämän todisti vuonna 1969, jo ennen termin "etäisyystransitiivinen graafi" käyttöönottoa, ryhmä neuvostomatemaatikoita ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [10] [8] . Pienin säännöllinen etäisyyskaavio, joka ei ole etäisyystransitiivinen, on Shrikhande-graafi . Ainoa tämän tyyppinen kolmiarvoinen graafi on Tattan 12-soluinen graafi, jossa on 126 kärkeä [8] .

Ominaisuudet

Etäisyyssäännöllinen kuvaaja, jonka halkaisija on 2, on vahvasti säännöllinen , ja päinvastoin on myös totta (edellyttäen, että kuvaaja on yhdistetty ) [3] .

Etäisyyssäännöllisen graafin leikkaustaulukon ominaisuudet

Etäisyyssäännöllisen graafin leikkaustaulukolla on seuraavat ominaisuudet [11] [12] :

Jokaisella kärjellä on vakiomäärä pisteitä etäisyyden päässä siitä ja kaikille ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\pisteet ,\,D-1$
Kaavion järjestys on ; $n$ ${\displaystyle n=k_{0}+k_{1}+\,\pisteet \,+k_{D))$
Niiden kärkien lukumäärä, jotka ovat etäisyyden päässä kustakin pisteestä, ilmaistaan leikkauspisteiden lukumääränä, kuten kaikilla ; $j+1$ ${\displaystyle k_{j+1}={\frac {b_{0}b_{1}\dots b_{j}}{c_{1}c_{2}\dots c_{j+1))))$ $j=0,\,1,\,\pisteet ,\,D-1$
Mielivaltaisesta kärjestä etäisyyden päässä olevien pisteiden lukumäärän tulo graafin järjestyksessä on parillinen arvo kaikille ; $k_{j}\cdot n$ $j$ $j=1,\,2,\,\pisteet ,\,D$
Mielivaltaisesta kärjestä etäisyyden päässä olevien pisteiden lukumäärän tulo leikkauspisteiden lukumäärällä on parillinen arvo kaikille ; ${\displaystyle k_{j}\cdot a_{j))$ $j$ $a_{j}$ $j=1,\,2,\,\pisteet ,\,D$
Leikkausten lukumäärän , graafin järjestyksen ja sen valenssin tulo on jaollinen 6:lla; $a_{1}\cdot n\cdot k$ $a_{1}$
Risteysnumeroille , ; ${\displaystyle c_{j))$ ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D))$
Risteysnumeroille , ; $b_{j}$ ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1))$
Jos , niin ; $i+j\leqslant D$ ${\displaystyle c_{i}\leqslant b_{j))$
On sellainen, että ja . $i$ ${\displaystyle k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i))$ ${\displaystyle k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D))$

Transitiivis-säännöllisen graafin etäisyysmatriisit

Olkoon graafi transitiivisesti säännöllinen halkaisijaltaan , sen kärkien lukumäärä ja graafin valenssi. Määritellään joukko etäisyysmatriiseja , joiden koko on [ 3 ] : ${\näyttötyyli \Gamma (V,E)}$ $D$ $n=|V|$ $k$ $n\ kertaa n$ ${\displaystyle \left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\oikea\))$

\left(\mathbf {A} _{h}\right)_{r,s}={\begin{cases}1&:\,d(v_{r},v_{s})=h, \\0&:\,d(v_{r},v_{s})\neq h\end{cases}}

Etäisyysmatriisien ominaisuudet

Etäisyysmatriiseilla on seuraavat ominaisuudet [3] :

${\displaystyle \mathbf {A} _{0}=\mathbf {I} _{n))$ , missä on identiteettimatriisi ; $\mathbf {I} _{n}$
$\mathbf {A} _{1}=\mathbf {A}$ on tavallinen graafin viereisyysmatriisi ; ${\näyttötyyli \Gamma (V,E)}$
$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\pisteet +\mathbf {A} _{D}=\mathbf {J }_{n}$ , missä on yksiköiden matriisi $\mathbf {J} _{n}$
$\mathbf {A} \mathbf {A} _{i}=b_{i-1}\mathbf {A} _{i-1}+a_{i}\mathbf {A} _{i}+ c_{i+1}\mathbf {A} _{i+1}$ , jossa on joukko etäisyys-säännöllisen kaavion leikkauspisteitä ja ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots , \,c_{d}\end{Bmatrix}}$ ${\displaystyle a_{i}=k-b_{i}-c_{i))$
on olemassa reaalilukuja siten, että kaikki , Ja siellä on määrä risteyksiä, eli määrä vertices, jotka ovat etäisyydellä kärkipisteestä ja etäisyydellä vertex , Koska etäisyys vertices ja . Huomaa, että , , . $p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\pisteet ,\,D)$ $\mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}$ ${\näyttötyyli (i,\,j=0,\,1,\,\pisteet ,\,D)}$ ${\displaystyle p_{i,j}^{h))$ $j$ $v$ $i$ $w$ $h$ $v$ $w$ $p_{1,i-1}^{i}=c_{i}$ $p_{1,i}^{i}=a_{i}$ $p_{1,i+1}^{i}=b_{i}$

Muistiinpanot

↑ Biggs, 1971 .
↑ Brouwer, Cohen ja Neumaier 1989 , s. 128.
↑ 1 2 3 4 5 6 Biggs, 1993 , s. 159.
↑ 1 2 Brouwer, Cohen ja Neumaier, 1989 , s. 126.
↑ Biggs, 1971 , s. kahdeksantoista.
↑ Lauri ja Scapelatto, 2016 , s. 33.
↑ Biggs, 1993 , s. 157.
↑ 1 2 3 4 Brouwer, Cohen ja Neumaier, 1989 , s. 136.
↑ Cohen, 2004 , s. 232.
↑ Adelson-Velsky, Weisfeler, Leman ja Faradzhev, 1969 .
↑ van Dam, Koolen ja Tanaka, 2006 , s. kahdeksan.
↑ van Dam, Koolen ja Tanaka, 2006 , s. yksitoista.

Kirjallisuus

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Esimerkki kaaviosta, jossa ei ole transitiivista automorfismiryhmää // Tiedeakatemian raportit . - 1969. - T. 185 , nro 5 . - S. 975-976 .
Biggs N. L. Lineaaristen graafien leikkausmatriisit // Kombinatorinen matematiikka ja sen sovellukset : Oxfordin Mathematical Institutessa 7.-10. heinäkuuta 1969 pidetyn konferenssin julkaisut / toimittanut DJA Welsh. - Lontoo: Academic Press, 1971. - S. 15-23 .
Biggs N. L. Algebrallinen graafiteoria . – 2. painos. - Cambridge University Press , 1993. - 205 s.
Brouwer A., Cohen A. M., Neumaier A. Säännölliset etäisyyskaaviot . - Berliini, New York: Springer Verlag , 1989. - ISBN 3-540-50619-5 , 0-387-50619-5.
Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (englanti) / toimittanut LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Voi. 102. - s. 222-249. - (Matematiikan tietosanakirja ja sen sovellukset).
van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (englanniksi) // The Electronic Journal of Combinatorics : Dynamic surveys. - 2006. - Ei. DS22 .
Lauri J. , Scapelatto R. Graph Automorphisms and Reconstruction -aiheet . – 2. painos. - Combridge: Combridge University Press, 2016. - 188 s.