Hamiltonský graf

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 18. června 2022; ověření vyžaduje 1 úpravu .

Hamiltonovský graf  je graf obsahující hamiltonovský cyklus [1] . Hamiltonovský cyklus je v tomto případě takový cyklus (uzavřená cesta), který prochází každým vrcholem daného grafu právě jednou [2] ; tedy jednoduchou smyčku, která zahrnuje všechny vrcholy grafu.

S hamiltonovským grafem úzce souvisí také koncept hamiltonovské cesty , což je jednoduchá cesta (cesta bez smyček) procházející každým vrcholem grafu právě jednou [1] . Hamiltonovská cesta se liší od cyklu v tom, že počáteční a koncový bod cesty se na rozdíl od cyklu nemusí shodovat. Hamiltonovský cyklus je hamiltonovská cesta.

Hamiltonovská cesta, cyklus a graf jsou všechny pojmenovány po irském matematikovi W. Hamiltonovi , který jako první identifikoval tyto třídy zkoumáním problému „cestování kolem světa“ na dvanáctistěnu . V tomto problému vrcholy dvanáctistěnu symbolizovaly slavná města jako Brusel , Amsterdam , Edinburgh , Peking , Praha , Dillí , Frankfurt atd. a okraje symbolizovaly silnice, které je spojují. Cestovatel musí jít „kolem světa“ a najít cestu, která prochází všemi vrcholy právě jednou [3] . Aby byl úkol zajímavější, bylo předem stanoveno pořadí projíždění měst. A aby bylo snazší si zapamatovat, která města již byla propojena, do každého vrcholu dvanáctistěnu byl zaražen hřebík a dlážděná cesta byla označena malým provazem, který se dal kolem hřebíku omotat. Tato konstrukce se však ukázala jako příliš těžkopádná a Hamilton navrhl novou verzi hry, nahrazující dvanáctistěn rovinným grafem izomorfním ke grafu postavenému na okrajích dvanáctistěnu [4] .

Podmínky existence

Jednoduchá nutná a postačující podmínka pro existenci hamiltonovského cyklu je známá a prokázána [5] .

Nutná podmínka existence hamiltonovského cyklu v neorientovaném grafu : obsahuje-li neorientovaný graf G hamiltonovský cyklus, pak v něm nejsou žádné vrcholy s lokálním stupněm . Důkaz vyplývá z definice.

Posh podmínka: Nechť má graf G vrcholy. Jestliže pro libovolné , je počet vrcholů se stupni menšími nebo rovnými n menší než n a pro lichý počet vrcholů se stupněm nepřesahuje , pak G je hamiltonovský graf. Tato dostatečná podmínka není nutná [6] .

V důsledku Poschovy věty získáváme jednodušší a méně silné postačující podmínky nalezené Diracem a Orem.

V roce 1952 byla formulována Diracova podmínka pro existenci hamiltonovského cyklu : nechť  je počet vrcholů v daném grafu a ; pokud stupeň každého vrcholu není menší než , pak je daný graf hamiltonovský [7] .

Rudná podmínka : nechť  je počet vrcholů v daném grafu a . Pokud nerovnost platí pro libovolnou dvojici nesousedících vrcholů , pak je daný graf hamiltonovský (jinými slovy: součet stupňů libovolných dvou nesousedících vrcholů není menší než celkový počet vrcholů v grafu) [ 7] .

Bondiho teorém  — Chvatala zobecňuje tvrzení Diraca a Orea. Graf je hamiltonovský právě tehdy, když jeho uzávěr je hamiltonovský graf. Pro graf G s n vrcholy se sestrojí uzávěr přidáním hrany ( u , v ) ke G pro každou dvojici nesousedících vrcholů u a v , jejichž součet stupňů je alespoň n [8] .

Algoritmus pro nalezení hamiltonovské cesty

Heuristické optimalizace

Při přímém výčtu variant vrcholů je možné výrazné zvýšení průměrné složitosti hledání hamiltonovské cesty na náhodných grafech (pokud je zaručena existence hamiltonovské cesty v grafu). Pro zlepšení této metody je možné v každém kroku výčtu u některé zkonstruované části řetězce zkontrolovat, zda zbývající vrcholy tvoří souvislý graf (pokud ne, pak řetězec nemůže být začátkem hamiltonovského řetězce); v každém kroku iterace při výběru dalšího vrcholu nejprve vyzkoušejte vrcholy s nejmenším zbytkovým stupněm (počet hran vedoucích k vrcholům, které ještě nebyly navštíveny). Navíc, pokud je tento strom řetězem, je v něm možný hamiltonovský cyklus. Jinak (pokud má strom vrcholy se stupněm ne menším než 3) je konstrukce hamiltonovského cyklu nemožná [9] .

Příklady použití

Kryptografie

Hamiltonovský cyklus se používá v systému tzv. protokolů s nulovou znalostí .

Nechť Peggy a Victor znají stejný hamiltonovský graf G a Peggy v něm zná hamiltonovský cyklus. Chce to Victorovi dokázat, aniž by mu odhalila samotný cyklus. Existuje algoritmus, jak by to mělo fungovat [10] :

1. Peggy náhodně transformuje graf G. Přesunutím bodů a změnou jejich označení vytvoří nový graf H, který je topologicky izomorfní s G. Poté, když zná Hamiltonův cyklus v G, může jej snadno najít v H. nevytvořila H sama, pak by bylo určení izomorfismu mezi grafy příliš složitým úkolem, jehož řešení vyžaduje enormní množství času. Poté zašifruje H a získá graf H'.

2. Peggy podává Victor H'.

3. Victor požádá Peggy, aby:

  1. Dokažte, že H' je zašifrovaná izomorfní kopie G, popř
  2. Ukažte Hamiltonův cyklus pro H.

4. Peggy splní jeho požadavek. Ona buď:

  1. Dokazuje, že H' je zašifrovaná izomorfní kopie G, odhalující transformace a dešifrující vše, aniž by ukazoval hamiltonovský cyklus pro G nebo H, popř.
  2. Ukazuje hamiltonovský cyklus pro H, dešifruje pouze to, co tvoří hamiltonovský cyklus, aniž by dokázal, že H a G jsou topologicky izomorfní.

5. Peggy a Victor opakují kroky 1-4 nkrát.

Pokud Peggy nepodvádí, pak bude moci sdělit Victorovi kterýkoli z důkazů v kroku 3. Pokud však nezná hamiltonovský cyklus pro G, nebude schopna vytvořit H', které splňuje oba důkazy. Pravda, Peggy dokáže vytvořit buď graf izomorfní k G, nebo graf se stejným počtem vrcholů a hran a správným hamiltonovským cyklem. A ačkoli dokáže s 50% pravděpodobností odhadnout, jaký důkaz bude Victor žádat v kroku 3, Victor může opakovat protokol tolikrát, dokud si nebude jistý, že Peggy zná Hamiltonův cyklus v G.

Extrémní problémy v teorii grafů: Problém cestujícího obchodníka

Obchodní cestující musí navštívit každé město na určitém území a vrátit se do výchozího bodu. Je nutné, aby cesta byla co nejkratší. Původní problém se tak transformuje na problém nalezení minimální délky (trvání nebo nákladů) [11] .

Problém lze přeformulovat z hlediska teorie grafů - sestrojit graf G(X, A), jehož vrcholy odpovídají městům a hrany odpovídají komunikacím mezi městy. Řešení tohoto problému se hledá mezi hamiltonovskými cykly sestrojeného grafu.

Existuje mnoho způsobů, jak tento problém vyřešit. Lze rozlišit metody vyvinuté Bellmorem a Nemhauserem [12] , Garfinkelem a Nemhauserem [13] , Heldem a Karpem [14] , Stekhanem [15] . Známá řešení problému obchodního cestujícího jsou také metoda větvení a vazby a metoda postupného zlepšování řešení [16] .

Související pojmy

Semi-hamiltonovský [17] graf je graf obsahující jednoduchý řetězec procházející každým jeho vrcholem právě jednou. Navíc každý hamiltonovský graf je semi-hamiltonovský. Hamiltonovský cyklus je jednoduchým překlenutím [18] .

Podstatou problému hamiltonovského cyklu  je zjistit, zda daný graf G má hamiltonovský cyklus. Tento problém je NP-úplný [19] .

Hamiltonovský řetězec digrafu [20]  je jednoduchá cesta procházející každým vrcholem digrafu právě jednou .

Hamiltonovský orcyklus [20] je orcyklus [20] digrafu , který prochází každým z jeho vrcholů .

Digraf se nazývá semi -hamiltonský [20] , pokud má hamiltonovský orchain, a hamiltonovský [20] , pokud má hamiltonovský orcyklus.

Viz také

Poznámky

  1. ↑ 1 2 M. O. Asanov, V. A. Baranský, V. V. Rašín. Diskrétní matematika: grafy, matroidy, algoritmy. - Iževsk: Regular and Chaotic Dynamics, 2001. - S. 41. - ISBN 5-93972-076-5 .
  2. ↑ Svámí, Thulasiraman, 1984 , str. 55.
  3. ↑ Harari, 2003 , str. 16-17.
  4. ↑ O. Rud. Grafy a jejich aplikace. - Moskva: Mir, 1965. - S. 40-41.
  5. ↑ Dmitrij Maksimov. Cesty a cesty  // Věda a život . - 2020. - č. 2 . - S. 81-86 .
  6. ↑ Harari, 2003 , str. 86.
  7. ↑ 1 2 Harari, 2003 , str. 87.
  8. ↑ Svámí, Thulasiraman, 1984 , str. 61.
  9. ↑ Grafy a algoritmy: Přednáška 8: Eulerovy a Hamiltonovské cykly . POZNAT Intuit. Získáno 20. listopadu 2014. Archivováno z originálu 29. listopadu 2014.
  10. ↑ Schneier, 2002 , str. 89-90.
  11. ↑ Mainika, 1981 , s. 241-264.
  12. ↑ Bellmore M., Nemhuser G.L. Problém cestujícího obchodníka: A. Průzkum. — ORSA sv. 16, 1968. - S. 538-558.
  13. ↑ Garfinkel R., Namhauser GL Integer Programming. - New York: John Wiley, Inc., 1972. - S. 354-360.
  14. ↑ Held M., Karp R. The Traveling-Salesman Problem and Minimum Spanning Trees, Part II // Math. Programování. - 1971. - Sv. 1. - S. 6-25. - doi : 10.1007/BF01584070 .
  15. ↑ Steckhan H.A. Věta o problémech symetrického cestujícího obchodníka. — ORSA, sv. 18, 1970. - S. 1163-1167.
  16. ↑ Mainika, 1981 , s. 255-264.
  17. ↑ Wilson I.R., Eddiman A.M. Praktický úvod do Pascalu. - Moskva: Rádio a komunikace, 1983. - S. 143.
  18. ↑ Tutt, 1988 .
  19. ↑ T. Cormen, C. Leizerson, R. Rivest. Algoritmy. Konstrukce a analýza. - Moskva: MTSNMO, 2002. - S. 845-846.
  20. ↑ 1 2 3 4 5 Dolgikh, Petrenko, 2007 .

Literatura

Odkazy