Hamiltoni gráf

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. június 18-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Hamilton-gráf  egy Hamilton - ciklust tartalmazó gráf [1] . Ebben az esetben a Hamilton-ciklus egy olyan ciklus (zárt út), amely az adott gráf minden csúcsán pontosan egyszer halad át [2] ; vagyis egy egyszerű hurok, amely a gráf összes csúcsát tartalmazza.

Szintén szorosan kapcsolódik a Hamilton-gráfhoz a Hamilton-út fogalma , amely egy egyszerű út (hurkok nélküli út), amely a gráf minden csúcsán pontosan egyszer halad át [1] . A Hamilton-pálya abban különbözik a ciklustól, hogy az út kezdő- és végpontja nem eshet egybe, ellentétben a ciklussal. A Hamilton-ciklus egy hamiltoni út.

A Hamiltoni út, ciklus és gráf mind W. Hamilton ír matematikusról nevezték el , aki először azonosította ezeket az osztályokat a dodekaéder „világkörüli utazásának” problémájának vizsgálatával . Ebben a feladatban a dodekaéder csúcsai olyan híres városokat jelképeztek, mint Brüsszel , Amszterdam , Edinburgh , Peking , Prága , Delhi , Frankfurt stb., a szélei pedig az őket összekötő utakat. Az utazónak "körbe kell járnia a világot", olyan utat kell találnia, amely pontosan egyszer halad át az összes csúcson [3] . A feladat érdekesebbé tétele érdekében a városok áthaladásának sorrendjét előre meghatározták. És hogy könnyebben megjegyezzük, mely városok kapcsolódnak már össze, a dodekaéder minden csúcsába szöget vertek, a kikövezett ösvényt pedig egy kis kötéllel jelölték ki, amit a szög köré lehetett tekerni. Ez a konstrukció azonban túlságosan körülményesnek bizonyult, és Hamilton a játék új verzióját javasolta, a dodekaéder helyett a dodekaéder éleire épített gráfra izomorf síkgráfot [4] .

A létezés feltételei

A Hamilton-ciklus létezésének egyszerű szükséges és elégséges feltétele ismert és bizonyított [5] .

Szükséges feltétele a Hamilton-ciklus létezésének egy irányítatlan gráfban : ha egy irányítatlan G gráf tartalmaz Hamilton-ciklust, akkor nincs benne lokális fokú csúcs . A bizonyítás a definícióból következik.

Posh feltétel: Legyen a G gráfnak csúcsa. Ha bármely , esetén az n-nél kisebb vagy azzal egyenlő fokú csúcsok száma kisebb, mint n, és páratlan számú fokos csúcs esetén nem haladja meg a -t, akkor G egy Hamilton-gráf. Ez az elégséges feltétel nem szükséges [6] .

A Posch-tétel következtében egyszerűbb és kevésbé erős elégséges feltételeket kapunk, amelyeket Dirac és Ore talált.

1952-ben megfogalmazták Dirac feltételét a Hamilton-ciklus létezésére : legyen  az adott gráf csúcsainak száma és ; ha az egyes csúcsok foka nem kisebb, mint , akkor az adott gráf Hamilton-féle [7] .

Ércfeltétel : legyen  az adott gráf csúcsainak száma és . Ha az egyenlőtlenség bármely nem szomszédos csúcspárra érvényes , akkor az adott gráf Hamilton-féle (más szóval: bármely két nem szomszédos csúcs fokszámának összege nem kisebb, mint a gráf csúcsainak teljes száma) [ 7] .

Bondi tétele  – Chvatala általánosítja Dirac és Ore állításait. Egy gráf akkor és csak akkor Hamilton-gráf, ha a lezárása egy Hamilton-gráf. Egy n csúcsú G gráf esetén a lezárást úgy állítjuk elő, hogy G -hez hozzáadunk egy élt ( u , v ) minden olyan u és v nem szomszédos csúcspárhoz , amelyek fokösszege legalább n [8] .

Algoritmus egy Hamilton-útvonal megtalálásához

Heurisztikus optimalizálás

A csúcsváltozatok közvetlen számbavételével jelentősen megnőhet a Hamilton-útvonal véletlenszerű gráfokon történő megtalálásának átlagos bonyolultsága (ha garantált a Hamilton-út megléte a gráfban). A módszer javítása érdekében a felsorolás minden lépésében lehetőség van a lánc valamely megszerkesztett részének ellenőrzésére, hogy a fennmaradó csúcsok összefüggő gráfot alkotnak-e (ha nem, akkor a lánc nem lehet egy Hamilton-lánc kezdete); minden iterációs lépésnél a következő csúcs kiválasztásakor először a legkisebb maradékfokú (a még meg nem látogatott csúcsokhoz vezető élek száma) csúcsokat próbálja ki. Sőt, ha ez a fa egy lánc, akkor egy Hamilton-ciklus lehetséges benne. Ellenkező esetben (ha a fának legalább 3 fokos csúcsai vannak) lehetetlen Hamilton-ciklus felépítése [9] .

Használati példák

Kriptográfia

A Hamilton-ciklust az úgynevezett nulla tudás protokollok rendszerében használják .

Hadd ismerje meg Peggy és Victor ugyanazt a G Hamilton-gráfot, Peggy pedig ismerje benne a Hamilton-ciklust. Be akar bizonyítani Victornak anélkül, hogy felfedné neki a ciklust. Létezik egy algoritmus, hogyan kell működnie [10] :

1. Peggy véletlenszerűen átalakítja a G gráfot. A pontok mozgatásával és címkéik megváltoztatásával új H gráfot hoz létre, amely topológiailag izomorf G-vel. Ekkor a G-beli Hamilton-ciklus ismeretében könnyen megtalálhatja H-ben. nem maga hozta létre H-t, akkor a gráfok közötti izomorfizmus meghatározása túl bonyolult feladat lenne, aminek megoldása óriási időt vesz igénybe. Ezután titkosítja H-t, és megkapja a H' gráfot.

2. Peggy kezek Victor H'.

3. Victor megkéri Peggyt, hogy:

  1. Bizonyítsuk be, hogy H' G titkosított izomorf másolata, vagy
  2. Mutasd meg a Hamilton-ciklust H.

4. Peggy teljesíti kérését. Ő vagy:

  1. Bebizonyítja, hogy H' G titkosított izomorf másolata, amely transzformációkat tár fel és mindent megfejt anélkül, hogy G vagy H Hamilton-ciklust mutatna, vagy
  2. Hamilton-ciklust mutat H-re, csak azt fejti meg, hogy mi alkot Hamilton-ciklust, anélkül, hogy bebizonyítaná, hogy H és G topológiailag izomorf.

5. Peggy és Victor ismételje meg a lépéseket 1-4 n-szer.

Ha Peggy nem csal, akkor a 3. lépésben elmondhatja Victornak a bizonyítások bármelyikét. Ha azonban nem ismeri G Hamilton-ciklusát, nem tud olyan H'-t létrehozni, amely mindkét bizonyítást kielégíti. Igaz, Peggy vagy G-vel izomorf gráfot tud létrehozni, vagy ugyanannyi csúcsot és élt tartalmazó gráfot, megfelelő Hamilton-ciklussal. És bár 50%-os valószínűséggel kitalálja, hogy Victor milyen bizonyítást kér majd a 3. lépésben, Victor elégszer meg tudja ismételni a protokollt, amíg meg nem bizonyosodik arról, hogy Peggy ismeri a Hamilton-ciklust G-ben.

Extrém problémák a gráfelméletben: Az utazó eladó probléma

Az utazó eladónak egy adott területen belül minden várost meg kell látogatnia, és vissza kell térnie a kiindulópontra. Szükséges, hogy az út a lehető legrövidebb legyen. Így az eredeti probléma a minimális hossz (időtartam vagy költség) megtalálásának problémájává alakul át [11] .

A probléma újrafogalmazható gráfelméleti szempontból – olyan G(X, A) gráf megalkotása, amelynek csúcsai városoknak, élei pedig városok közötti kommunikációnak felelnek meg. Ennek a problémának a megoldását a megszerkesztett gráf Hamilton-ciklusai között keresik.

A probléma megoldásának számos módja van. Bellmore és Nemhauser [12] , Garfinkel és Nemhauser [13] , Held és Karp [14] , Stekhan [15] által kidolgozott módszerek különböztethetők meg . Szintén ismert megoldások az utazó eladók problémájára az elágazó és kötött módszer, valamint a megoldás egymás utáni javításának módszere [16] .

Kapcsolódó kifejezések

A félig Hamiltoni [17] gráf egy olyan gráf, amely egy egyszerű láncot tartalmaz, amely minden csúcsán pontosan egyszer halad át. Ráadásul minden Hamilton gráf félig Hamilton-gráf. A Hamilton- ciklus egy egyszerű feszítőciklus [18] .

A Hamilton-ciklusprobléma lényege,  hogy megtudjuk, van-e egy adott G gráfnak Hamilton-ciklusa. Ez a probléma NP-teljes [19] .

A digráf [20] Hamilton -orlánca  egy egyszerű út, amely a digráf minden csúcsán pontosan egyszer halad át.

A Hamilton-féle orciklus [ 20] egy digráf orciklusa [20], amely áthalad annak minden csúcsán .

Egy digráfnak fél -Hamilton-féle [20] -nak nevezzük , ha van Hamilton-orlánca, és Hamilton -nak [20] -nak nevezzük, ha Hamiltoni orciklusa van.

Lásd még

Jegyzetek

  1. ↑ 1 2 M. O. Asanov, V. A. Baransky, V. V. Rasin. Diszkrét matematika: gráfok, matroidok, algoritmusok. - Izhevsk: Regular and Chaotic Dynamics, 2001. - P. 41. - ISBN 5-93972-076-5 .
  2. ↑ Swami, Thulasiraman, 1984 , p. 55.
  3. ↑ Harari, 2003 , p. 16-17.
  4. ↑ O. Érc. Grafikonok és alkalmazásuk. - Moszkva: Mir, 1965. - S. 40-41.
  5. ↑ Dmitrij Maksimov. Utak és utak  // Tudomány és élet . - 2020. - 2. sz . - S. 81-86 .
  6. ↑ Harari, 2003 , p. 86.
  7. ↑ 1 2 Harari, 2003 , p. 87.
  8. ↑ Swami, Thulasiraman, 1984 , p. 61.
  9. ↑ Grafikonok és algoritmusok: 8. előadás: Euler- és Hamilton-ciklusok . ISMERJE Intuit. Letöltve: 2014. november 20. Az eredetiből archiválva : 2014. november 29..
  10. ↑ Schneier, 2002 , p. 89-90.
  11. ↑ Mainika, 1981 , p. 241-264.
  12. ↑ Bellmore M., Nemhuser G.L. Az utazó értékesítő probléma: A. Felmérés. — ORSA köt. 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 Travelling-Salesman Problem and Minimum Spanning Trees, Part II // Math. Programozás. - 1971. - 1. évf. 1. - P. 6-25. - doi : 10.1007/BF01584070 .
  15. ↑ Steckhan H.A. tétel a szimmetrikus utazó értékesítői problémákról. — ORSA, vol. 18, 1970. - S. 1163-1167.
  16. ↑ Mainika, 1981 , p. 255-264.
  17. ↑ Wilson I.R., Eddiman A.M. Gyakorlati bevezetés Pascalhoz. - Moszkva: Rádió és kommunikáció, 1983. - S. 143.
  18. ↑ Tutt, 1988 .
  19. ↑ T. Cormen, C. Leizerson, R. Rivest. Algoritmusok. Építés és elemzés. - Moszkva: MTSNMO, 2002. - S. 845-846.
  20. ↑ 1 2 3 4 5 Dolgikh, Petrenko, 2007 .

Irodalom

Linkek