Pansyklinen kaavio

Pansyklinen graafi on  suunnattu tai suuntaamaton graafi , joka sisältää kaikki mahdolliset pituudet kolmesta graafin kärkien määrään [ 1] . Pansykliset graafit ovat yleistys Hamiltonin graafista , graafista, jonka syklit ovat maksimipituisia.

Määritelmät

Graafi , jossa on pisteet, on pansyklinen, jos graafi sisältää jollekin sisäpuolelle syklin, jonka pituus on [1] . Graafi on vertex-pansyklinen , jos graafi sisältää minkä tahansa ja samoissa rajoissa olevan kärjen kohdalla pituussyklin, joka sisältää kärjen [2] . Samoin graafi on reuna-pansyklinen , jos se sisältää minkä tahansa reunan ja minkä tahansa samoissa rajoissa olevan pituussyklin, joka sisältää reunan [2] .

Kaksiosainen graafi ei voi olla pansyklinen, koska se ei sisällä parittoman pituisia syklejä, mutta graafin sanotaan olevan bipansyklinen , jos se sisältää kaikki parilliset syklit välillä 4 - [3] .

Tasokaaviot

Maksimaalinen ulkotasograafi  on graafi, joka on muodostettu tasossa olevasta yksinkertaisesta monikulmiosta triagularisoimalla sen sisäpuoli. Mikä tahansa maksimaalinen ulkotasograafi on pansyklinen, mikä voidaan näyttää induktiolla. Kuvaajan ulkopinta on sykli, jossa on n kärkeä, ja poistamalla mikä tahansa kolmio, joka on yhdistetty graafin loppuosaan vain yhdellä reunalla (puun lehti, joka muodostaa kaksoiskolmiograafin ), muodostaa maksimaalisen ulkotason graafin, jossa on yksi luku vähemmän. pisteistä, ja induktiivisen oletuksen mukaan tässä graafissa on kaikki jäljellä olevat syklit. Jos kiinnitetään enemmän huomiota poistettavan kolmion valintaan, niin samat argumentit osoittavat tiukemman tuloksen, että mikä tahansa maksimaalinen ulkotasograafi on vertex-pancyclic [4] . Sama pätee kuvaajiin, joissa on maksimaalinen ulkotason kuvaaja virittävänä osakuvaajana , erityisesti pyörille .

Maksimaalinen tasograafi  on tasograafi, jossa kaikki pinnat, mukaan lukien ulompi, ovat kolmioita. Maksimaalinen tasograafi on vertex-pansyklinen silloin ja vain, jos se sisältää Hamiltonin syklin [5]  – jos se ei ole Hamiltonin sykli, se ei todellakaan ole pansyklinen, ja jos se on Hamiltonin, niin Hamiltonin syklin sisäosa muodostaa ulkopinnan. maksimaalisen ulomman tason graafin samoissa pisteissä ja reunoissa, joihin voidaan soveltaa aiempia ulomman tason graafien argumentteja [6] . Esimerkiksi kuvassa[ mitä? ] osoittaa oktaedrigraafin pansyklisyyden , Hamiltonin maksimaalisen tasograafin, jossa on kuusi kärkeä. Tarkemmin sanottuna, samoista syistä, jos maksimaalisella tasograafilla on sykli, jonka pituus on , siinä on kaikki pienempiä pituisia jaksoja [7] .

Halin-graafit ovat tasokaavioita, jotka on muodostettu tasopiirroksesta puusta , jossa ei ole kakkosasteen kärkeä, lisäämällä puun lehtiä yhdistävä sykli. Halin-graafit eivät välttämättä ole pansyklisiä, mutta ne ovat melkein pansyklisiä siinä mielessä, ettei ole olemassa korkeintaan yhden pituista sykliä. Puuttuvan syklin pituus on välttämättä tasainen. Jos yhdelläkään Halin-graafin sisäisistä pisteistä ei ole aste kolmea, graafi on välttämättä pansyklinen [8] .

Vuonna 1971 todettiin [1] , että monet klassiset ehdot Hamiltonin syklin olemassaololle ovat riittäviä myös pansyklisyydelle, ja siksi oletettiin, että mikä tahansa 4-kytkentäinen tasograafi on pansyklinen, mutta vastaesimerkkien perhe löydettiin pian [ 9] .

Turnaukset

Turnaus  on suunnattu graafi, jossa on yksi suunnattu kaari minkä tahansa kärkiparin välillä. Turnausta voidaan käyttää intuitiivisesti simuloimaan round robin -peliä piirtämällä kaari voittajalta häviäjälle jokaisessa kilpailun pelissä. Turnauksen sanotaan olevan vahvasti yhteydessä tai yksinkertaisesti vahva silloin ja vain, jos sitä ei voida jakaa kahteen ei-tyhjään häviäjien ja voittajien osajoukkoon, jolloin jokainen osallistuja voittaa minkä tahansa osallistujan [10] . Kaikki vahvat turnaukset ovat pansyklisiä [11] ja vertex pancyclic [12] . Jos turnaus on säännöllinen (jollakin osallistujalla on sama määrä voittoja ja tappioita kuin muilla osallistujilla), se on myös reunapansyklinen [13] , mutta vahvat turnaukset, joissa on neljä kärkeä, eivät voi olla reunapansyklisiä.

Kuvaajat, joissa on suuri määrä reunoja

Mantelin lause sanoo, että mikä tahansa suuntaamatonkärkigraafi, jossa on vähintäänreunat ja jossa ei ole useita reunoja tai silmukoita, sisältää joko kolmion tai on täydellinen kaksiosainen graafi . Tätä lausetta voidaan vahvistaa - mikä tahansa suuntaamaton Hamiltonin graafi, jossa on vähintäänreunat, on joko pansyklinen tai se on [1] .

On olemassa Hamiltonin suuntaisia ​​graafisia pisteitä ja kaaria, jotka eivät ole pansyklisiä, mutta mikä tahansa Hamiltonin suunnattu graafi, jossa on vähintään kaaria, on pansyklinen. Lisäksi tiukasti yhdistetty kärkigraafi, jossa jokaisella kärjellä on vähintään aste (saapuvat ja lähtevät kaaret lasketaan yhteen), on joko pansyklinen tai täydellinen kaksiosainen graafi [14] .

Kuvaajan asteet

Minkä tahansa graafin kohdalla sen graafin aste määritellään graafiksi samassa pistejoukossa, jolla on reuna minkä tahansa kahden kärjen välillä, joiden välinen etäisyys in ei ylitä . Jos kärki 2 on kytketty , niin Fleischnerin lauseen mukaan on Hamiltonin graafi. Väitettä voidaan vahvistaa: graafi on välttämättä vertex-pancyclic [15] . Tarkemmin sanottuna, jos se on Hamiltonin, se on myös pansyklinen [16] .

Laskennallinen monimutkaisuus

Graafin pansyklisyyden testaus on NP-täydellinen ongelma jopa 3-liitettävien kuutiograafien erikoistapauksessa . On myös NP-täydellinen ongelma testata graafia huippupisteiden pansyklisyyden suhteen jopa monitahoisten graafien erikoistapauksessa [17] . Lisäksi NP-täydellinen tehtävä on testata graafin neliötä Hamiltonin ja siten myös pansyklisyyden testaamiseksi [18] .

Historia

Pansyklisyyttä tutkivat ensin Harari ja Moser turnausten yhteydessä [19] sekä Muun [20] ja Alpach [13] . Pansyklisyyden käsitteen nimesi Bondi, joka laajensi käsitteen suuntaamattomiin graafisiin [1] .

Muistiinpanot

  1. ↑ 1 2 3 4 5 Bondy, 1971 .
  2. ↑ 1 2 Randerath, Schiermeyer, Tewes, Volkmann, 2002 .
  3. ↑ Schmeichel, Mitchem, 1982 .
  4. ↑ Li, Corneil, Mendelsohn, 2000 , lause 2.5.
  5. ↑ Helden, 2007 , Seuraus 3.78.
  6. ↑ Bernhart, Kainen, 1979 .
  7. ↑ Hakimi, Schmeichel, 1979 .
  8. ↑ Skowrońska, 1985 .
  9. ↑ Malkevitš, 1971 .
  10. ↑ Harary ja Moser, 1966 , Seuraus 5b.
  11. ↑ Harary ja Moser, 1966 , Lause 7.
  12. ↑ Kuu, 1966 , Lause 1.
  13. ↑ 12 Alspach , 1967 .
  14. ↑ Häggkvist, Thomassen, 1976 , s. 20-40.
  15. ↑ Hobbs (1976) .
  16. ↑ Fleischner, 1976 .
  17. ↑ Li, Corneil, Mendelsohn, 2000 , Lauseet 2.3 ja 2.4.
  18. ↑ Underground (1978) .
  19. ↑ Harary, Moser, 1966 .
  20. ↑ Kuu, 1966 .

Kirjallisuus

Linkit