A matematika, azon belül a gráfelmélet területén G gráf akkor hipohamiltoni (hypohamiltonian), azaz „majdnem Hamilton-körös”, ha nem rendelkezik Hamilton-körrel, de tetszőleges csúcsát eltávolítva már lesz benne Hamilton-kör. Hasonlóan, egy hypotraceable, azaz „majdnem Hamilton-utas” gráf nem tartalmaz Hamilton-utat, de bármely n − 1 csúcsból álló részhalmazát Hamilton-út köti össze.; ; ; .
Történet A hipohamiltoni gráfokat először vizsgálta. a korai cikkek közül -t és -t említi, további korai munka a .
a kutatási terület nagy részét a következőképp összegzi: „az ilyen gráfokat taglaló cikkek általában hipohamiltoni vagy hipotraceable gráfok egy-egy új osztályát mutatják be, megmutatva hogy léteznek n rendű ilyen gráfok, vagy hogy különös és meglepő tulajdonságokkal rendelkeznek”.
Alkalmazások A hipohamiltoni gráfok előfordulnak az utazó ügynök problémájának egészértékű programozási megoldásaiban: bizonyos fajta hipohamiltoni gráfok az „utazóügynök-politóp” hiperlapjait határozzák meg; ez az alak az utazó ügynök problémája lehetséges megoldásai halmazának konvex burka, a hiperlapokat pedig a probléma vágási módszerrel való megoldásában használják.; ; . megfigyelése szerint egy gráf hipohamiltonisága meghatározásának számítási bonyolultsága, bár nem ismert a pontos értéke, de valószínűleg magas, ezért a hiperlapok megkeresése is nehéz az egészen kicsi hipohamiltoni gráfokén kívül; szerencsére a legkisebb gráfokból nyerhetők ki a legerősebb egyenlőtlenségek, melyeket ez az alkalmazás igényel..
a hipohamiltonisághoz közel álló fogalmakkal operálva mérik meg a párhuzamos számítástechnika által használt hálózati topológiák hibatűrését.
Tulajdonságok Minden hipohamiltoni gráf 3-szorosan összefüggő, hiszen két tetszőleges csúcs eltávolítása után egy Hamilton-út marad, ami összefüggő. Léteznek olyan, n-csúcsú hipohamiltoni gráfok, melyek maximális fokszáma n/2, éleik száma pedig kb. n2/4.. Nem ismert, hogy létezik-e négyszeresen összefüggő hypohamiltonian gráf, mint ahogy az sem, hogy létezik-e olyan, amelynek nincs 3 fokú csúcsa. Minden síkbarajzolható hipohamiltoni gráfban van viszont legalább egy olyan csúcs, amelyből csak három él indul ki..
sejtése szerint a hypohamiltonian gráfok girthparamétere 5 vagy több, de ezt cáfolta , aki talált 3 és 4 bőségű ellenpéldákat is.
Az 1970-es évek elején ismert hypohamiltonian gráfok többnyire a Petersen-gráf általánosításaként, illetve Chvátal flip-flopjainak segítségével álltak elő, és egyikük sem volt síkbarajzolható. Ez motiválta Chvátalt, amikor felvetette, hogy léteznek-e egyáltalán síkbarajzolható hypohamiltonian gráfok ( 5 dollárt ajánlott fel annak, aki konstruál egyet) és ha igen, vannak-e köztük 3-regulárisak.
Az első síkbarajzolható hypohamiltonian gráfot a Grinberg-tétel felhasználásával 1976-ban találta , ennek 105 csúcsa volt; talált 3, 4 és 5 bőségű ilyen gráfokat és megmutatta, hogy végtelen sok létezik belőlük. 1979-ben talált egy 57 csúcsú hypohamiltonian síkgráfot. 1993-ban tette fel a kérdést, hogy létezik-e ennél kisebb hypohamiltonian síkgráf. 48 csúcsú példát, 42 csúcsút találtak, az eddigi legkisebbet pedig, 40 csúccsal, , a Grinberg-tétel alapján végzett számítógépes kereséssel.
2011-ig nem volt ismert, hogy minden elegendően nagy n-re létezik-e n csúcsú hypohamiltonian, illetve hypotraceable síkgráf. megmutatta, hogy minden n ≥ 76 esetén létezik n csúcsú síkbarajzolható hypohamiltonian gráf, illetve minden n ≥ 180 esetén létezik n csúcsú síkbarajzolható hypotraceable gráf. Ezeket a becsléseket 2014-ben 42-re, illetve 156-ra javította. A legkisebb ismert síkbarajzolható hypotraceable gráf 138 csúcsból áll, almost hypohamiltonian gráfból kiinduló konstrukciója alapján.
A 3-reguláris, síkbarajzolható, hypohamiltonian gráfok közül az elsőt találta, ennek 94 csúcsa van. 2011-ig nem is sikerült ennél kisebb példát találni és az sem volt ismert, hogy kellően nagy páros n-ekre mindig létezik-e n csúcsú 3-reguláris, hypohamiltonian síkgráf. Mindkét kérdés cikkében még a megoldatlan problémák között szerepel. cikkéből azonban következett, hogy nem létezik 42 vagy kevesebb csúcsú ilyen gráf. 2011-ben mindkét kérdést megválaszolta : bemutatott egy 70 csúcsú 3-reguláris hypohamiltonian síkgráfot, ami jelenleg is a legkisebb ismert ilyen tulajdonságú gráf és bizonyította, hogy n ≥ 86 esetén mindig létezik n csúcsú 3-reguláris hypohamiltonian síkgráf; utóbbi korlátot 74-re javította.
Minden páros n ≥ 356 esetre létezik 3-reguláris, síkbarajzolható, hypotraceable gráf (sőt: poliédergráf), ahogy azt megmutatta.
Ha egy 3-reguláris gráfnak van Hamilton-köre, élei kiszínezhetők három színnel: a Hamilton-kör éleit váltakozó színekkel kiszínezzük (ezt megtehetjük, mert a kézfogás-lemma miatt páros a hosszúsága), a maradék élekre pedig felhasználjuk a harmadik színt. Így aztán egyetlen snarknak (összefüggő, hídmentes, 3-reguláris gráf, 4-es kromatikus számmal) sem lehet Hamilton-köre, és számos ismert snark hipohamiltoni. Minden hipohamiltoni snark ún. bikritikus: bármely két csúcsát eltávolítva a maradék részgráf éleinek színezéséhez három szín elegendő.; . A részgráf 3-színezése egyszerűen megadható: egy csúcs eltávolításával a maradék csúcsok Hamilton-kört alkotnak. A második csúcs eltávolításával a körből egy út marad, melynek éleit két színnel váltakozva kiszínezhetjük. A maradék élek párosítást alkotnak, ezért a harmadik szín elegendő hozzájuk.
Egy 3-reguláris gráf 3-színezésének a színosztályai olyan három párosítást alkotnak, melyben minden él pontosan egy párosításhoz tartozik.. A hipohamiltoni snarkoknak nincs ilyen párosításuk, de sejtése szerint éleik hat párosításba oszthatók oly módon, hogy minden él pontosan két párosításba tartozzon. Ez a Berge–Fulkerson-sejtés speciális esete, mely kimondja, hogy bármely snarknak hat ilyen tulajdonságú párosítása van.
A hipohamiltoni gráfok nem lehetnek párosak: egy páros gráfban egy csúcs törlésével csak akkor jön létre Hamilton-körű részgráf, ha a gráf két színosztálya közül a nagyobbikba tartozik. Minden páros gráf előáll azonban valamely hipohamiltoni gráf feszített részgráfjaként..
Példák A legkisebb hypohamiltonian gráf a Petersen-gráf . Általánosabban, a GP(n,2) általánosított Petersen-gráf akkor hypohamiltonian, amikor n kongruens 5 (mod 6); igazolta, hogy ezeknek a gráfoknak nincs Hamilton-körük, pedig egyszerűen ellenőrizhető, hogy az egy csúcs kitörlésével kapott gráfoknak viszont van. Lásd munkáját a Hamilton-kör nélküli általánosított Petersen-gráfok osztályozásáról. maga a Petersen-gráf az n = 5 esetben áll elő.
talált egy másik végtelen hipohamiltoni gráfosztályt, melyben a csúcsok száma kongruens 4 (mod 6). Lindgren konstrukciója egy 3 (mod 6) hosszúságú körből és egyetlen központi csúcsból áll; a központi csúcsot összeköti a kör minden harmadik csúcsával (ezeket nevezi küllőknek) és a küllő-végpontoktól kettő-kettő távolságra lévő csúcsokat pedig egymással. Lindgren konstrukciója esetében is a legkisebb előállítható gráf a Petersen-gráf.
További végtelen családokat ír le , és .
Leszámlálás Václav Chvátal 1973-as bizonyítása szerint elegendően nagy n-re létezik n csúcsú hipohamiltoni gráf. A későbbi felfedezéseket is figyelembe véve,; . jelenlegi tudásunk szerint az „elegendően nagy” azt jelenti, hogy minden n ≥ 18 értékre léteznek ilyen gráfok. A legfeljebb 17 csúcsú hipohamiltoni gráfok teljes listája ismert:. Lásd még . ezek a 10 csúcsú Petersen-gráf, a számítógépes keresése által fellelt 13, illetve 15 csúcsú gráf és négy 16 csúcsú gráf. Legalább tizenhárom 18 csúcsú hipohamiltoni gráf létezik. flip-flop módszerét a Petersen-gráfra és a virág-snarkra alkalmazva megmutatható, hogy a hypohamiltonian gráfok, azon belül is a hypohamiltonian snarkok száma a csúcsok számának exponenciális függvényében növekszik.; .
Hypotraceable gráfok Az első, 40 csúcsú hypotraceable gráfot Horton találta 1976-ban , az eddigi legkisebb, 34 csúcsú hypotraceable gráf felfedezése érdeme. A legkisebb hypotraceble gráf méretére nincs jó alsó becslés, részben azért, mert ezeket a gráfokat eddig Thomassen két módszerét felhasználva hypohamiltonian gráfokból állították elő. Az ugyanakkor alapján ismert, hogy az n ≥ 42 esetekre létezik n csúcsú hypotraceable gráf.
Általánosítások A hipohamiltoni és hypotraceable gráfok irányított gráf-analógiáival több szerző is foglalkozott már.; ; ; .
A hipohamiltoni gráfok egy ekvivalens definíciója szerint ezek a gráfok, melyek leghosszabb köre n − 1 hosszúságú és az összes leghosszabb kör metszete üres. azokat a gráfokat vizsgálta, melyekben a leghosszabb körök metszete szintén üres, de leghosszabb kör rövidebb n − 1-nél. úgy definiálja egy gráf cyclability paraméterét, mint az a legnagyobb k szám, melyre bármely k csúcs ugyanabba a körbe tartozik; a hypohamiltonian gráfok pontosan azok a gráfok, melyek cyclability paramétere n − 1. Hasonlóan definíciója szerint egy gráf ƒ-fault hamiltonian (ƒ hibával hamiltoni), ha a legfeljebb ƒ csúcs eltávolításával kapott részgráfnak van Hamilton-köre. azokat a gráfokat vizsgálja, melyekben a cyclability értéke n − 2.
Foglalkoznak továbbá almost hypohamiltonian és almost hypotraceable gráfokkal is.
Fordítás
Jegyzetek
. . . . . . . . . . . . . . . . . . . . Häggkvist, R. (2007), "Problem 443. Special case of the Fulkerson Conjecture", in Mohar, B.; Nowakowski, R. J.; West, D. B., Research problems from the 5th Slovenian Conference (Bled, 2003), ''Discrete Mathematics 307 (3–5): 650–658, . . . . . . . . . . . . . . . . As cited by . . . . . . . . . . . . . . .
További információk
http://www.cs.bme.hu/~wiener/tezisfuzet.pdf
Kategória:Gráfcsaládok Kategória:Hamilton-utak és -körök