Barnette-sejtés

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)

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.

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

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

Akiyama, Takanori; Nishizeki, Takao & Saito, Nobuji (1980), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing 3 (2): 73–76, <https://ipsj.ixsq.nii.ac.jp/ej/index.php?action=pages_view_main&active_action=repository_action_common_download&item_id=59994&item_no=1&attribute_id=1&file_no=1&page_id=13&block_id=8>.
Aldred, R. E. L.; Bau, S. & Holton, D. A. et al. (2000), "Nonhamiltonian 3-connected cubic planar graphs", SIAM Journal on Discrete Mathematics 13 (1): 25–32, DOI 10.1137/S0895480198348665
Barnette, David W. (1969), "Conjecture 5", in Tutte, W. T., Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, New York: Academic Press.
Feder, Tomas & Subi, Carlos (2006), On Barnette's conjecture, <https://eccc.weizmann.ac.il/report/2006/015/>.
Florek, Jan (2010), "On Barnette's conjecture", Discrete Mathematics 310 (10-11): 1531–1535, DOI 10.1016/j.disc.2010.01.018.
Goodey, P.R. (1975), "Hamiltonian circuits in polytopes with even sided faces", Israel Journal of Mathematics 22 (1): 52–56, DOI 10.1007/BF02757273
Hertel, Alexander (2005), A survey & strengthening of Barnette’s conjecture, <http://www.cs.toronto.edu/~ahertel/WebPageFiles/Papers/StrengtheningBarnette'sConjecture10.pdf>.
Holton, D. A.; Manvel, B. & McKay, B. D. (1985), "Hamiltonian cycles in cubic 3-connected bipartite planar graphs", Journal of Combinatorial Theory, Series B 38 (3): 279–297, DOI 10.1016/0095-8956(85)90072-3.
Horton, J. D. (1982), "On two-factors of bipartite regular graphs", Discrete Mathematics 41 (1): 35–41, DOI 10.1016/0012-365X(82)90079-6.
Kelmans, A. K. (1994), "Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles", in Kelmans, A. K., Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar 1972–1990, vol. 158, American Mathematical Society Translations, Series 2, pp. 127–140.
Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series 17: 30–46. Reprinted in Scientific Papers, Vol. II, pp. 85–98.
Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98, <http://jlms.oxfordjournals.org/cgi/reprint/s1-21/2/98.pdf>.
Tutte, W. T. (1971), "On the 2-factors of bicubic graphs", Discrete Mathematics 1 (2): 203–208, DOI 10.1016/0012-365X(71)90027-6.

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.

[1] (Tutte 1971); (Horton 1982).

[FOOTNOTEFlorek2010-2] Florek (2010).

[3] (Holton, Manvel & McKay 1985); (Hertel 2005).

[4] (Feder & Subi 2006).

[5] (Akiyama, Nishizeki & Saito 1980).

[6] (Aldred et al. 2000).

[1]

[2]

[3]

[4]

[5]

[6]