Perhonen (graafiteoria)

Graafiteoriassa perhosgraafi (tunnetaan myös nimellä rusetti tai tiimalasi ) on tasomainen suuntaamaton graafi , jossa on 5 kärkeä ja 6 reunaa [1] [2] . Graafi voidaan rakentaa yhdistämällä kaksi kopiota syklistä C 3 yhteen yhteiseen kärkeen, ja siksi graafi on isomorfinen ystävyysgraafin F 2 kanssa .

Perhosen halkaisija  on 2 ja ympärysmitta  3, säde 1, kromaattinen luku  3, kromaattinen indeksi  4, ja se on sekä Euler että yksikköetäisyyskäyrä . Kaavio on yhdistetty 1 kärkipisteeseen ja 2 reunaan yhdistetty .

On vain 3 yksinkertaista graafia, joissa on viisi kärkeä ja joissa ei ole hienoa merkintää . Yksi niistä on perhonen. Kaksi muuta ovat sykli C 5 ja täydellinen graafi K 5 [3] .

Perhosvapaat kaaviot

Kaaviossa ei ole perhosia , jos siinä ei ole perhosta generoituna aligraafina . Kolmiottomat kaaviot ovat perhosvapaita kaavioita, koska perhoskaavio sisältää kolmioita.

Huippupisteessä k - kytketyssä graafissa reunan sanotaan olevan k -supistuva, jos reunan supistuminen johtaa k - liittyneeseen graafiin. Ando, ​​​​Kaneko, Kawarabayashi ja Yoshimoto osoittivat, että jokaisella k -vertex -liitetyllä perhosvapaalla graafilla on k - sisäänvetävä reuna [4] .

Algebralliset ominaisuudet

Perhosgraafin täydellinen automorfismiryhmä on 8:n asteen isomorfinen ryhmä D 4 :n kanssa, neliön symmetriaryhmä , mukaan lukien kierto ja heijastukset.

Perhosgraafimatriisin ominaispolynomi on .

Muistiinpanot

1. ↑ Weisstein, Eric W. Butterfly Graph  Wolfram MathWorld -verkkosivustolla .
2. ↑ ISGCI: Tietojärjestelmä graafiluokista ja niiden sisällyttämisestä. " List of Small Graphs arkistoitu 22. heinäkuuta 2012 Wayback Machinessa ".
3. ↑ Weisstein, Eric W. Graceful kaavio  Wolfram MathWorld -verkkosivustolla .
4. ↑ Ando, ​​2007 , s. 10-20.

Kirjallisuus

• Kiyoshi Ando. Diskreetti geometria, kombinatoriikka ja graafiteoria. - Springer, Berliini, 2007. - T. 4381. - S. 10–20. - (Luentomuistiinpanot in Comput. Sci.). - doi : 10.1007/978-3-540-70666-3_2 .