Hamiltonin kaavio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18.6.2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Hamiltonin graafi  on graafi , joka sisältää Hamiltonin syklin [1] . Tässä tapauksessa Hamiltonin sykli on sellainen sykli (suljettu polku), joka kulkee annetun graafin jokaisen kärjen läpi täsmälleen kerran [2] ; eli yksinkertainen silmukka, joka sisältää kaikki graafin kärjet.

Hamiltonin graafiin liittyy läheisesti myös Hamiltonin polun käsite , joka on yksinkertainen polku (polku ilman silmukoita), joka kulkee graafin kunkin kärjen läpi täsmälleen kerran [1] . Hamiltonin polku eroaa syklistä siinä, että polun alku- ja loppupisteet eivät välttämättä ole samat, toisin kuin syklin. Hamiltonin sykli on Hamiltonin polku.

Hamiltonin polku, sykli ja graafi on nimetty irlantilaisen matemaatikon W. Hamiltonin mukaan, joka ensin tunnisti nämä luokat tutkimalla "maailman ympäri matkustamisen" ongelmaa dodekaedrin avulla . Tässä tehtävässä dodekaedrin kärjet symboloivat kuuluisia kaupunkeja, kuten Brysseliä , Amsterdamia , Edinburghia , Pekingiä , Prahaa , Delhiä , Frankfurtia jne., ja reunat symboloivat niitä yhdistäviä teitä. Matkustajan on kierrettävä "maailman ympäri" ja löydettävä polku, joka kulkee kaikkien kärkien läpi täsmälleen kerran [3] . Tehtävän kiinnostavuuden lisäämiseksi kaupunkien ohitusjärjestys asetettiin etukäteen. Ja jotta olisi helpompi muistaa, mitkä kaupungit olivat jo yhteydessä, naula lyötiin dodekaedrin jokaiseen kärkeen ja päällystetty polku oli merkitty pienellä köydellä, joka voitiin kääriä naulan ympärille. Tämä konstruktio osoittautui kuitenkin liian hankalaksi, ja Hamilton ehdotti pelistä uutta versiota, joka korvasi dodekaedrin tasograafilla, joka oli isomorfinen dodekaedrin reunoihin rakennetun graafin kanssa [4] .

Olemassaoloehdot

Yksinkertainen välttämätön ja riittävä ehto Hamiltonin syklin olemassaololle on tunnettu ja todistettu [5] .

Välttämätön ehto Hamiltonin syklin olemassaololle suuntaamattomassa graafissa : jos suuntaamaton graafi G sisältää Hamiltonin syklin, siinä ei ole paikallisastetta olevia pisteitä . Todistus seuraa määritelmästä.

Hieno ehto: Olkoon graafilla G kärjet. Jos jollakin , , pisteiden lukumäärä, joiden aste on pienempi tai yhtä suuri kuin n, on pienempi kuin n, ja parittomalla määrällä pisteitä, joiden aste ei ylitä , niin G on Hamiltonin graafi. Tämä riittävä ehto ei ole välttämätön [6] .

Poschin lauseen seurauksena saamme Diracin ja Oren löytämät yksinkertaisemmat ja vähemmän vahvat riittävät ehdot.

Vuonna 1952 muotoiltiin Diracin ehto Hamiltonin syklin olemassaololle : Olkoon  graafin pisteiden lukumäärä ja ; jos kunkin kärjen aste ei ole pienempi kuin , niin annettu graafi on Hamiltonin [7] .

Malmiehto : Olkoon pisteiden  lukumäärä annetussa graafissa ja . Jos epäyhtälö pätee mille tahansa ei-vierekkäisten kärkien parille , niin annettu graafi on Hamiltonin (toisin sanoen: minkä tahansa kahden ei-viereisen kärjen asteiden summa ei ole pienempi kuin graafin kärkien kokonaismäärä) [ 7] .

Bondin lause  – Chvatala yleistää Diracin ja Oren väitteet. Graafi on Hamiltonin, jos ja vain, jos sen sulkeminen on Hamiltonin graafi. Graafille G , jossa on n kärkeä , sulkeminen muodostetaan lisäämällä reuna ( u , v ) G :hen kullekin ei-vierekkäiselle pisteparille u ja v , jonka asteiden summa on vähintään n [8] .

Algoritmi Hamiltonin polun löytämiseksi

Heuristiset optimoinnit

Huippupisteiden varianttien suoralla luettelemalla Hamiltonin polun löytämisen keskimääräinen monimutkaisuus satunnaisgraafista on mahdollista merkittävästi (jos Hamiltonin polun olemassaolo graafissa on taattu). Tämän menetelmän parantamiseksi on mahdollista jokaisessa laskentavaiheessa jollekin ketjun rakennetulle osalle tarkistaa, muodostavatko loput kärjet yhdistetyn graafin (jos eivät, niin ketju ei voi olla Hamiltonin ketjun alku); jokaisessa iteraatiovaiheessa, kun valitset seuraavaa kärkeä, kokeile ensin pisteitä, joilla on pienin jäännösaste (särmien määrä, jotka johtavat kärkipisteisiin, joita ei ole vielä käyty). Lisäksi, jos tämä puu on ketju, niin Hamiltonin sykli on mahdollista siinä. Muuten (jos puun kärjet ovat vähintään 3), Hamiltonin syklin rakentaminen on mahdotonta [9] .

Käyttöesimerkkejä

Kryptografia

Hamiltonin sykliä käytetään ns. nollatietoprotokollien järjestelmässä .

Anna Peggyn ja Victorin tietää sama Hamiltonin graafi G, ja Peggy tietää Hamiltonin syklin siinä. Hän haluaa todistaa sen Victorille paljastamatta itse kiertokulkua hänelle. On olemassa algoritmi, kuinka sen pitäisi toimia [10] :

1. Peggy muuntaa satunnaisesti graafin G. Siirtämällä pisteitä ja muuttamalla niiden otsikoita hän luo uuden graafin H, joka on topologisesti isomorfinen G:n kanssa. Sitten hän voi helposti löytää sen G:stä, kun hän tietää Hamiltonin syklin G:stä. ei olisi itse luonut H:tä, silloin isomorfismin määrittäminen graafien välillä olisi liian monimutkainen tehtävä, jonka ratkaiseminen vaatii valtavasti aikaa. Sitten hän salaa H:n ja saa graafin H'.

2. Peggy kädet Victor H'.

3. Victor pyytää Peggyä jompaankumpaan:

  1. Todista, että H' on G:n salattu isomorfinen kopio, tai
  2. Näytä Hamiltonin sykli H:lle.

4. Peggy täyttää hänen pyyntönsä. Hän joko:

  1. Todistaa, että H' on G:n salattu isomorfinen kopio, joka paljastaa muunnoksia ja tulkitsee kaiken näyttämättä Hamiltonin sykliä G:lle tai H:lle, tai
  2. Näyttää Hamiltonin syklin H:lle, tulkitseen vain sen, mikä muodostaa Hamiltonin syklin, todistamatta, että H ja G ovat topologisesti isomorfisia.

5. Peggy ja Victor toistavat vaiheet 1-4 n kertaa.

Jos Peggy ei petä, hän voi kertoa Victorille minkä tahansa todistuksen vaiheessa 3. Jos hän ei kuitenkaan tiedä Hamiltonin sykliä G:lle, hän ei pysty luomaan H':tä, joka tyydyttää molemmat todisteet. Totta, Peggy voi luoda joko G:n kanssa isomorfisen graafin tai graafin, jolla on sama määrä pisteitä ja kulmia ja oikea Hamiltonin sykli. Ja vaikka hän voi arvata 50 %:n todennäköisyydellä, mitä todistusta Victor pyytää vaiheessa 3, Victor voi toistaa protokollan riittävän monta kertaa, kunnes hän on varma, että Peggy tietää Hamiltonin syklin G:ssä.

Äärimmäiset ongelmat graafiteoriassa: matkustava myyjä -ongelma

Matkamyyjän tulee käydä jokaisessa kaupungissa tietyllä alueella ja palata lähtöpisteeseen. Polun on oltava mahdollisimman lyhyt. Alkuperäinen ongelma muuttuu siis minimipituuden (keston tai kustannusten) löytämisen ongelmaksi [11] .

Ongelma voidaan muotoilla uudelleen graafiteorian kannalta - rakentaa graafi G(X, A), jonka kärjet vastaavat kaupunkeja ja reunat kaupunkien välistä viestintää. Tämän ongelman ratkaisua etsitään konstruoidun graafin Hamiltonin syklien joukosta.

On monia tapoja ratkaista tämä ongelma. Bellmoren ja Nemhauserin [12] , Garfinkelin ja Nemhauserin [13] , Heldin ja Karpin [14] , Stekhanin [15] kehittämät menetelmät voidaan erottaa . Myös tunnettuja ratkaisuja matkustava myyjä -ongelmaan ovat haara ja sidottu menetelmä sekä ratkaisun peräkkäisen parantamisen menetelmä [16] .

Aiheeseen liittyvät termit

Semi-Hamiltonin [17] graafi on graafi, joka sisältää yksinkertaisen ketjun, joka kulkee kunkin kärjensä läpi tarkalleen kerran. Lisäksi jokainen Hamiltonin graafi on puolihamiltoninen. Hamiltonin sykli on yksinkertainen virittävä sykli [18] .

Hamiltonin sykliongelman ydin  on selvittää, onko tietyllä graafilla G Hamiltonin sykli. Tämä ongelma on NP-täydellinen [19] .

Digraafin Hamiltonin ketju [20]  on yksinkertainen polku, joka kulkee digraafin jokaisen kärjen läpi tasan kerran.

Hamiltonin orcycle [20] on orcycle [20] digrafista, joka kulkee kunkin kärjensä läpi .

Digraafia kutsutaan semi -Hamiltonin muotoiseksi [20] , jos sillä on Hamiltonin ketju, ja Hamiltonin muotoiseksi [ 20] , jos sillä on Hamiltonin orsykli .

Katso myös

Muistiinpanot

  1. ↑ 1 2 M. O. Asanov, V. A. Baransky, V. V. Rasin. Diskreetti matematiikka: graafit, matroidit, algoritmit. - Izhevsk: Regular and Chaotic Dynamics, 2001. - S. 41. - ISBN 5-93972-076-5 .
  2. ↑ Swami, Thulasiraman, 1984 , s. 55.
  3. ↑ Harari, 2003 , s. 16-17.
  4. ↑ O. Malmi. Kaaviot ja niiden sovellus. - Moskova: Mir, 1965. - S. 40-41.
  5. ↑ Dmitri Maksimov. Tiet ja reitit  // Tiede ja elämä . - 2020. - Nro 2 . - S. 81-86 .
  6. ↑ Harari, 2003 , s. 86.
  7. ↑ 1 2 Harari, 2003 , s. 87.
  8. ↑ Swami, Thulasiraman, 1984 , s. 61.
  9. ↑ Graafit ja algoritmit: Luento 8: Eulerin ja Hamiltonin syklit . TIEDÄ Intuit. Haettu 20. marraskuuta 2014. Arkistoitu alkuperäisestä 29. marraskuuta 2014.
  10. ↑ Schneier, 2002 , s. 89-90.
  11. ↑ Mainika, 1981 , s. 241-264.
  12. ↑ Bellmore M., Nemhuser G.L. The Travelling Salesman Problem: A. Survey. — ORSA voi. 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, Osa II // Math. Ohjelmointi. - 1971. - Voi. 1. - s. 6-25. - doi : 10.1007/BF01584070 .
  15. ↑ Steckhan H.A. Lause symmetrisistä matkustavien myyntimiesongelmista. — ORSA, voi. 18, 1970. - S. 1163-1167.
  16. ↑ Mainika, 1981 , s. 255-264.
  17. ↑ Wilson I.R., Eddiman A.M. Käytännön johdatus Pascaliin. - Moskova: Radio ja viestintä, 1983. - S. 143.
  18. ↑ Tutt, 1988 .
  19. ↑ T. Cormen, C. Leizerson, R. Rivest. Algoritmit. Rakentaminen ja analyysi. - Moskova: MTSNMO, 2002. - S. 845-846.
  20. ↑ 1 2 3 4 5 Dolgikh, Petrenko, 2007 .

Kirjallisuus

Linkit