Grinberg-tétel

A matematika, azon belül a gráfelmélet területén a Grinberg-tétel annak egy szükséges feltétele, hogy egy síkgráf Hamilton-kört tartalmazzon, a síkbarajzolás tartományaiban található körök hosszúságai alapján. A tételt széles körben felhasználták olyan, Hamilton-kört nem tartalmazó síkbarajzolható gráfok konstruálására, melyek egyéb tulajdonságokkal rendelkeznek, például a (W.T. Tutte által 1946-ban elsőként cáfolt) Tait-sejtésre új ellenpéldákat kerestek vele. A tételt Emanuels Grinbergs lett matematikus 1968-ban bizonyította.

Egy gráf, mely a Grinberg-tétel szerint nem rendelkezik Hamilton-körrel

A tétel kimondása

Legyen G véges síkbarajzolható gráf C Hamilton-körrel, tekintsük ennek a gráfnak egy rögzített síkba rajzolását. Jelölje ƒ_k és g_k a C-n belül, illetve kívül található k-szögű tartományok számát. Ekkor

$\sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0.$

A bizonyítás egyszerűen következik az Euler-formulából.

A tétel következménye, hogy ha egy síkbarajzolható gráf síkba rajzolható úgy, hogy egy kivételével az összes tartomány oldalainak száma 2 mod 3, a megmaradó tartomány oldalainak száma pedig nem 2 mod 3, akkor a gráfnak nem lehet Hamilton-köre. Például az ábrán látható gráf összes korlátos tartományának 5 vagy 8 oldala van, a külső, nem korlátos tartománynak viszont 9, tehát az iménti feltételnek eleget tesz, ezért nincs Hamilton-köre. Bármely síkgráf azon tartományai, melyeknek 2 mod 3 oldala van, 0 mod 3-ot ad hozzá a Grinberg-tételben szereplő összeghez, hiszen k − 2 szorzótényező szerepel az összegben. A többi tartomány azonban nemnulla mod 3-at ad hozzá, függetlenül attól, hogy a feltételezett Hamilton-körön kívül vagy belül találhatók. Tehát ha csak egy tartomány ad hozzá nemnulla értéket, nem lehetséges, hogy az összeg nulla legyen, ezért a gráf nem tartalmazhat Hamilton-kört.

Alkalmazásai

Grinberg arra használta tételét, hogy olyan, Hamilton-körmentes 3-reguláris poliédergráfokat keressen, melyeknek magas a ciklikus élösszefüggősége (cyclic edge connectivity). Egy gráf ciklikus élösszefüggősége az élek minimális száma, melyek törlése után a gráfnak egynél több kör komponense lesz. A 46 csúcsú Tutte-gráf, és a belőle származtatott kisebb, Hamilton-kör nélküli 3-reguláris poliédergráfok ciklikus élösszefüggősége három. Grinberg tétele segítségével talált Hamilton-kör nélküli 3-reguláris gráfot, melynek 44 csúcsa és, 24 tartománya van, ciklikus élösszefüggősége pedig 4, továbbá az ábrán is látható másikat, melynek 46 csúcsa és 25 tartománya van, ciklikus élösszefüggősége pedig 5, ami a maximális lehetséges ciklikus élösszefüggőség a 3-reguláris síkgráfoknak a K₄ kivételével. Az ábrán látható gráf összes korlátos tartományának 5 vagy 8 oldala van, mindkettő 2 mod 3, a külső, nem korlátos tartománynak viszont 9, ami nem 2 mod 3. Ezért a Grinberg-tétel következményeként a gráfnak nem lehet Hamilton-köre.

A Grinberg-tétel segítségével találtak síkba rajzolható hipohamiltoni gráfokat, szintén azzal a módszerrel, hogy egy kivételével az összes tartomány oldalainak számát 2 mod 3-ra állították be (Thomassen 1976, Wiener & Araya 2009). (Thomassen 1981) a tételt bonyolultabban alkalmazva keresett 3-reguláris síkbarajzolható hipohamiltoni gráfot: az általa konstruált gráfban található egy 4 oldal határolta tartomány, ami négy, 7 oldalú tartománnyal szomszédos, az összes többi tartomány pedig 5 vagy 8 oldalú. Ahhoz, hogy a Grinberg-tételnek eleget tegyen, egy Hamilton-körnek el kéne határolnia a 4 vagy 7 oldalú tartományt a másik négytől, ami nem lehetséges.

Korlátai

Léteznek olyan síkbarajzolható, Hamilton-kört nem tartalmazó gráfok, melyek lerajzolásában minden tartománynak 5 vagy 8 oldala van. Ezekben a gráfokban a modulo 3 vett Grinberg-tétel követelményét a tartományok bármilyen két részhalmazba osztása kielégíti, így a tétel segítségével nem bizonyítható, hogy a gráfnak nincs Hamilton-köre (Zaks 1977).

Nem használható a Grinberg-tétel a Barnette-sejtés ellenpéldáinak kereséséhez sem; Barnette sejtése szerint minden 3-reguláris páros poliédergráfnak van Hamilton-köre. Az ilyen gráfok esetében a tartományoknak mindig létezik olyan két részhalmazra osztása, ami kielégíti a Grinberg-tételt, attól függetlenül, hogy van-e gráfnak Hamilton-köre (Krooss 2004).

Fordítás

• Ez a szócikk részben vagy egészben a Grinberg's theorem 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

• Grinberg, È. Ja. (1968), "Plane homogeneous graphs of degree three without Hamiltonian circuits", Latvian Math. Yearbook 4, Riga: Izdat. “Zinatne”, pp. 51–58. English translation by Dainis Zeps, Sablon:Arxiv.
• Krooss, André (2004), "Die Barnette'sche Vermutung und die Grinberg'sche Formel", Analele Universităţii din Craiova. Seria Matematică-Informatică 31: 59–65.
• Malkevitch, Joseph (January 2005), Euler's Polyhedral Formula: Part II, Feature Column, American Mathematical Society, <http://www.ams.org/featurecolumn/archive/eulers-formulaII.html>.
• Thomassen, Carsten (1976), "Planar and infinite hypohamiltonian and hypotraceable graphs", Discrete Mathematics 14 (4): 377–389, DOI 10.1016/0012-365X(76)90071-6.
• Thomassen, Carsten (1981), "Planar cubic hypo-Hamiltonian and hypotraceable graphs", Journal of Combinatorial Theory, Series B 30 (1): 36–44, DOI 10.1016/0095-8956(81)90089-7.
• Wiener, Gábor & Araya, Makoto (2009), The ultimate question.
• Tutte, W. T. (1998), "Chapter 2: Knights Errant", Graph theory as I have known it, vol. 11, Oxford Lecture Series in Mathematics and its Applications, New York: The Clarendon Press Oxford University Press, ISBN 0-19-850251-6.
• Zaks, Joseph (1977), "Non-Hamiltonian non-Grinbergian graphs", Discrete Mathematics 17 (3): 317–321, DOI 10.1016/0012-365X(77)90165-0.

További információk

• Grinberg Graphs, from MathWorld.