Pyörä (graafiteoria)

Graafiteoriassa pyörä W n on graafi, jossa on n kärkeä (n ≥ 4), joka muodostuu yhden kärjen yhdistämisestä ( n -1) -syklin kaikkiin pisteisiin . Pyörien numeerinen nimitys kirjallisuudessa ei ole hyvin vakiintunut - jotkut kirjoittajat käyttävät n :tä syklin pituuden osoittamiseen, joten heidän W n tarkoittaa kuvaajaa W n+1 , kuten edellä on määritelty [1] . Pyörä voidaan määritellä samalla tavalla kuin 1-luuranko ( n -1 ) -hiilipyramidi .

Aseta esitys

Olkoon pistejoukko {1,2,3,…,v} annettu. Graafisen pyörän reunajoukko voidaan esittää joukona {{1,2},{1,3},…,{1,v},{2,3},{3,4},…, {v-1, v},{v,2}} [2] .

Ominaisuudet

Pyörät ovat tasokaavioita , ja siksi niillä on ainutlaatuinen upotus tasoon. Mikä tahansa pyörä on Halin-graafi . Ne ovat itsekaksoiskäyrät – minkä tahansa pyörän kaksoiskaavio on isomorfinen itse pyörän kanssa. Mikä tahansa muu maksimaalinen tasograafi kuin K 4 = W 4 sisältää joko W 5 tai W 6 aligraafina .

Pyörässä on aina Hamiltonin sykli ja syklien lukumäärä W n :ssä on (sekvenssi A002061 OEIS : ssä ).

Parittomille n:n arvoille W n on täydellinen graafi kromaattisella numerolla 3 – syklin kärjet voidaan värjätä kahdella värillä, ja keskipisteellä on kolmas väri. Jopa n W n :lle pyörän kromaattinen luku on 4 ja (jos n ≥ 6) ei ole täydellinen kuvaaja. W 7 on ainoa pyörä, joka on yksikköetäisyyskäyrä euklidisella tasolla [3] .

Pyörän W n kromaattinen polynomi on:

Matroiditeoriassa on kaksi erityisen tärkeää matroidin tyyppiä, pyörät ja pyörteet , jotka molemmat on johdettu pyörän kaavioista. K -pyörän matroidi on graafinen matroidipyörä W k+1 , ja k -pyörrematroidi saadaan k -pyörän matroidista julistamalla ulkosykli (vanne) yhtä itsenäiseksi kuin sen virittävät puut .

W 6 -pyörä tarjoaa vastaesimerkin Paul Erdősin olettamukselle Ramseyn teoriassa - hän arveli, että täydellisellä graafilla on pienin Ramsey-luku kaikista saman kromaattisen numeron omaavista graafista. Kuitenkin Faudree ja McKay (Faudree, McKay, 1993) osoittivat, että W 6 :n Ramsey-luku on 17, kun taas täydellisen graafin K 4 , jolla on sama kromaattinen luku, Ramsey-luku on 18 [4] . Siten minkä tahansa 17-pisteisen graafin G kohdalla joko G itse tai sen komplementti sisältää W 6 :n aligraafina, kun taas 17-pisteinen Paley-graafi tai sen komplementti eivät sisällä K4 : ää .

Muistiinpanot

1. ↑ Weisstein, Eric W. Wheel Graph  Wolfram MathWorld -verkkosivustolla .
2. ↑ Richard J. Trudeau. Johdatus graafiteoriaan. — Korjattu, laajennettu julkaisu. New York: Dover Pub. - S. 56. - ISBN 978-0-486-67870-2 .
3. ↑ Fred Buckley, Frank Harary. Pyörän euklidisesta ulottuvuudesta // Grafit ja kombinatoriikka. - 1988. - V. 4 , no. 1 . - S. 23-30 . - doi : 10.1007/BF01864150 .
4. ↑ Ralph J. Faudree, Brendan D. McKay. Arvaus Erdősistä ja Ramseyn luvusta r ( W 6 ) // J. Kombinatorinen matematiikka. ja Combinatorial Comput. - 1993. - T. 13 . — S. 23–31 .