Barnette-sejtés

A Barnette-sejtés a matematika, azon belül a gráfelmélet egy megoldatlan kérdése, ami gráfok Hamilton-köreivel foglalkozik. Nevét David W. Barnette-ről, a Davisi Kaliforniai Egyetem (UCD) professor emeritusáról kapta. A sejtés állítása szerint az olyan páros poliédergráfok, melyek minden csúcsából 3 él indul ki, minden esetben rendelkeznek Hamilton-körrel.

A matematika megoldatlan problémája: Található-e minden páros egyszerű poliéderben Hamilton-kör? (A matematika további megoldatlan problémái)

Definíciók

Egy síkbarajzolható gráf olyan irányítatlan gráf, ami beágyazható az euklideszi síkba anélkül, hogy az élek metszenék egymást. Egy síkbarajzolható gráf pontosan akkor poliédergráf, ha 3-szorosan csúcsösszefüggő, tehát ha két csúcs eltávolításával nem lehet elérni a gráf szétesését, hárommal viszont igen. Egy gráf páros, ha csúcsai két színnel kiszínezhetők úgy, hogy minden él két végpontja különböző színű. Egy gráf akkor 3-reguláris, ha minden csúcsában pontosan három él végződik. Végül, egy gráf akkor hamiltoni, ha létezik olyan köre, ami minden csúcsán pontosan egyszer halad át. Barnette sejtése szerint minden 3-reguláris páros poliédergráf hamiltoni.

A Steinitz-tétel alapján egy síkbarajzolható gráf pontosan akkor feleltethető meg egy konvex poliéder csúcsainak és éleinek, ha poliédergráf. Egy háromdimenziós poliédernek pontosan akkor van 3-reguláris poliédergráfja, ha egyszerű poliéder. Továbbá, egy síkbarajzolható gráf pontosan akkor páros, ha a gráfnak létezik olyan síkba ágyazása, mely minden tartományának köre páros hosszúságú. Ezért a Barnette-sejtés kimondható ebben az alakban is: ha egy háromdimenziós egyszerű konvex poliéder minden lapján páros számú él található, akkor a poliéder gráfjának van Hamilton-köre.

Történet

A P. G. Tait (1884)-ben megjelent sejtés szerint minden 3-reguláris poliédergráf hamiltoni; ez Tait-sejtés néven vált ismertté, és W. T. Tutte (1946) cáfolta meg egy 46 csúcsból álló ellenpélda konstruálásával, aminél később kisebb ellenpéldákat is sikerült találni. Ezek közül az ellenpéldák közül azonban egyik sem páros. Tutte maga azt sejtette, hogy minden 3-reguláris 3-összefüggő páros gráf hamiltoni, azonban ezt is cáfolták egy ellenpélda, a Horton-gráf megtalálásával.^[1] Ezek után David W. Barnette (1969) javasolta Tait és Tutte sejtéseinek egy gyengített kombinációját, miszerint minden páros 3-reguláris páros poliédergráfnak van Hamilton-köre, vagy másként fogalmazva, hogy Tait sejtésének egyetlen ellenpéldája sem páros gráf.

Ekvivalens megfogalmazások

(Kelmans 1994) megmutatta, hogy Barnette sejtése ekvivalens a következő, látszólag erősebb kijelentéssel: egy páros 3-reguláris poliéder ugyanazon lapján található tetszőlegesen választott e és f élekhez található olyan Hamilton-kör, ami tartalmazza e-t, de nem tartalmazza f-et. Ha ez az állítás igaz, nyilvánvaló, hogy minden páros 3-reguláris poliéder tartalmaz Hamilton-kört: csak tetszés szerint ki kell választani egy e és f élt. A másik irányban Kelmans megmutatta, hogy egy ellenpélda az eredeti Barnette-sejtés ellenpéldájává lenne átalakítható.

Barnette sejtése elvivalens azzal az állítással is, hogy minden 3-reguláris páros poliédergráf duálisának csúcsai két olyan részhalmazba particionálhatók, melyek feszített részgráfjai fák. A duális gráfbeli partíció által meghatározott vágás megfelel az eredeti gráf Hamilton-körének.^[2]

Részeredmények

Bár a Barnette-sejtés még bizonyítatlan, számítási kísérletek megmutatták, hogy nem létezik 86 csúcsnál kisebb ellenpélda.^[3]

Ha a Barnette-sejtés hamisnak bizonyulna, akkor megmutatható, hogy a 3-reguláris páros poliédergráfok hamiltoniságának tesztelése NP-teljes feladat.^[4] Ha egy síkbarajzolható gráf páros és 3-reguláris, de csak kétszeresen összefüggő, akkor előfordulhat, hogy nincs Hamilton-köre, és ennek tesztelése NP-teljes nehézségű..^[5]

Kapcsolódó problémák

Barnette egy kapcsolódó sejtése szerint minden 3-reguláris poliédergráf, amiben az összes tartomány hat vagy kevesebb élből áll, hamiltoni. Számítási kísérletek alapján megmutatták, hogy ha létezik ellenpélda, annak több mint 177 csúcsból kell állnia.^[6]

A két sejtés metszetét, miszerint az olyan páros 3-reguláris poliédergráfok, melyek tartományai 4 vagy 6 élből állnak, rendelkeznek Hamilton-körrel, (Goodey 1975) bizonyította.

Fordítás

• Ez a szócikk részben vagy egészben a Barnette's conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. (Tutte 1971); (Horton 1982).
2. Florek (2010).
3. (Holton, Manvel & McKay 1985); (Hertel 2005).
4. (Feder & Subi 2006).
5. (Akiyama, Nishizeki & Saito 1980).
6. (Aldred et al. 2000).

• .
• .
• .
• .
• .
• .
• .
• .
• . Reprinted in Scientific Papers, Vol. II, pp. 85–98.
• .
• .

További információk

• Weisstein, Eric W.: Barnette's Conjecture (angol nyelven). Wolfram MathWorld
• Barnette's Conjecture in the Open Problem Garden, Robert Samal, 2007.