Hamiltonin laajennus

Tietyn graafin Hamiltonin dekompositio on graafin reunojen jako Hamiltonin sykleiksi . Hamiltonin hajotuksia on tutkittu sekä suuntaamattomille että suunnatuille graafeille . Suuntaamattoman graafin tapauksessa Hamiltonin hajoamista voidaan kuvata graafin 2-tekijäistyksenä siten, että jokainen tekijä on yhdistetty. Jotta tällainen jaottelu olisi olemassa suuntaamattomalle graafille, sen on oltava yhdistetty säännöllinen graafi, jonka aste on parillinen . Suunnatun graafin, jolla on tällainen hajoaminen, tulee olla vahvasti kytketty ja kaikilla pisteillä on oltava samat sisään- ja lähtöasteet, mutta näiden asteiden ei tarvitse olla parillisia [1] .

Tiedetään, että jokaisella täydellisellä graafilla , jossa on pariton määrä pisteitä, on Hamiltonin hajoaminen. Tämän tuloksen, joka on erikoistapaus Oberwolfach-ongelmasta, joka koskee täydellisten graafien hajottamista isomorfisiksi 2-tekijöiksi, Eduard Luca katsoi vuonna 1892 Waleckin ansioksi. Walecki-konstruktio asettaa kärjet säännölliseen monikulmioon ja kattaa koko graafin tässä kärkiosien osajoukossa Hamiltonin poluilla, jotka kulkevat monikulmion läpi kutakin polkua kierrettäessä moninkertaisen kulman verran. Polut voidaan sitten täydentää Hamiltonin sykleihin yhdistämällä niiden päät jäljellä olevan kärjen kautta [2] . $n$ $n-1$ $(n-1)/2$ $\pi /(n-1)$

Tapauskohtaiset täydelliset kaaviot ovat turnauksia . Vastatessaan Kellyn vuoden 1968 olettamukseen Daniela Kühn ja Dirik Oestus osoittivat vuonna 2012, että kaikissa riittävän suurissa säännöllisissä turnauksissa on Hamiltonin hajoaminen [3] .

Sen tarkistaminen, onko mielivaltaisella graafilla Hamiltonin hajoaminen, on NP-täydellinen tehtävä sekä suunnatuille että suuntaamattomille graafille [4] .

Muistiinpanot

↑ Bermond J.-C. Graafeiden, suunnattujen graafien ja hypergraafien Hamiltonin hajotukset // Diskreetin matematiikan Annals. - 1978. - T. 3 . — S. 21–28 . - doi : 10.1016/S0167-5060(08)70494-1 .
↑ Brian Alspach. Upea Walecki-rakennus // Kombinatoriikkainstituutin tiedote ja sen sovellukset. - 2008. - T. 52 . - S. 7-20 .
↑ Daniela Kühn, Deryk Osthus. Hamiltonin säännöllisten laajennusten hajotukset: todiste Kellyn olettamuksesta suurille turnauksille // Advances in Mathematics. - 2013. - T. 237 . — S. 62–146 . - doi : 10.1016/j.aim.2013.01.005 . - arXiv : 1202.6219 .
↑ Péroche B. Joidenkin osiointi- ja kattausongelmien NP-täydellisyys kaavioissa // Discrete Applied Mathematics. - 1984. - T. 8 , no. 2 . — S. 195–208 . - doi : 10.1016/0166-218X(84)90101-X .