Hamiltonsk graf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 juni 2022; verifiering kräver 1 redigering .

En Hamiltonsk graf  är en graf som innehåller en Hamiltonsk cykel [1] . I det här fallet är en Hamiltonsk cykel en sådan cykel (sluten bana) som passerar genom varje hörn av den givna grafen exakt en gång [2] ; det vill säga en enkel slinga som inkluderar alla hörn i grafen.

Också nära besläktat med en Hamiltonsk graf är konceptet med en Hamiltonsk bana , som är en enkel bana (en bana utan slingor) som passerar genom varje hörn av grafen exakt en gång [1] . En Hamiltonsk bana skiljer sig från en cykel genom att start- och slutpunkterna för en bana kanske inte sammanfaller, till skillnad från en cykel. En Hamiltonsk cykel är en Hamiltonsk väg.

Den Hamiltonska banan, cykeln och grafen är alla uppkallade efter den irländska matematikern W. Hamilton , som först identifierade dessa klasser genom att undersöka problemet med att "resa jorden runt" på en dodekaeder . I detta problem symboliserade dodekaederns hörn kända städer som Bryssel , Amsterdam , Edinburgh , Peking , Prag , Delhi , Frankfurt , etc., och kanterna symboliserade vägarna som förbinder dem. Resenären måste gå "jorden runt", hitta en väg som passerar genom alla hörn exakt en gång [3] . För att göra uppgiften mer intressant sattes ordningen för att passera städerna i förväg. Och för att göra det lättare att komma ihåg vilka städer som redan var anslutna, slogs en spik in i varje spik på dodekaedern, och den asfalterade stigen markerades med ett litet rep som kunde viras runt spiken. Denna konstruktion visade sig dock vara för besvärlig, och Hamilton föreslog en ny version av spelet, som ersatte dodekaedern med en plan graf som var isomorfisk mot grafen byggd på kanterna av dodekaedern [4] .

Villkor för existens

Ett enkelt nödvändigt och tillräckligt villkor för existensen av en Hamiltonsk cykel är känt och bevisat [5] .

Ett nödvändigt villkor för existensen av en Hamiltonsk cykel i en oriktad graf : om en oriktad graf G innehåller en Hamiltonsk cykel, så finns det inga hörn i den med lokal grad . Beviset följer av definitionen.

Posh villkor: Låt graf G ha hörn. Om för någon , , antalet hörn med grader mindre än eller lika med n är mindre än n, och för ett udda antal hörn med grad inte överstiger , då är G en Hamiltonsk graf. Detta tillräckliga villkor är inte nödvändigt [6] .

Som en konsekvens av Poschs teorem får vi enklare och mindre starka tillräckliga villkor som hittats av Dirac och Ore.

1952 formulerades Diracs villkor för existensen av en Hamiltonsk cykel : låt  vara antalet hörn i en given graf och ; om graden av varje vertex inte är mindre än , då är den givna grafen Hamiltonian [7] .

Malmvillkor : låt vara  antalet hörn i den givna grafen och . Om olikheten gäller för vilket par som helst av icke-angränsande hörn , är den givna grafen Hamiltonian (med andra ord: summan av graderna av två icke-angränsande hörn är inte mindre än det totala antalet hörn i grafen) [ 7] .

Bondis teorem  — Chvatala generaliserar påståendena från Dirac och Ore. En graf är Hamiltonsk om och endast om dess stängning är en Hamiltonsk graf. För en graf G med n hörn, konstrueras en stängning genom att lägga till en kant ( u , v ) till G för varje par av icke-intilliggande hörn u och v vars summa av grader är minst n [8] .

En algoritm för att hitta en Hamiltonsk väg

Heuristiska optimeringar

Med direkt uppräkning av varianter av hörn är en betydande ökning av den genomsnittliga komplexiteten för att hitta en Hamiltonsk bana på slumpmässiga grafer möjlig (om förekomsten av en Hamiltonsk bana i grafen är garanterad). För att förbättra denna metod är det möjligt att vid varje steg av uppräkningen för någon konstruerad del av kedjan kontrollera om de återstående hörnen bildar en sammanhängande graf (om de inte gör det, kan kedjan inte vara början på en Hamiltonsk kedja); vid varje iterationssteg, när du väljer nästa vertex, prova först hörn med den minsta restgraden (antalet kanter som leder till hörn som ännu inte har besökts). Dessutom, om detta träd är en kedja, är en Hamiltonsk cykel möjlig i den. Annars (om trädet har hörn med grader som inte är mindre än 3), är konstruktionen av en Hamiltonsk cykel omöjlig [9] .

Användningsexempel

Kryptografi

Hamiltonska cykeln används i ett system av så kallade nollkunskapsprotokoll .

Låt Peggy och Victor känna till samma Hamiltonska graf G, och Peggy känner till Hamiltons cykel i den. Hon vill bevisa det för Victor utan att avslöja själva cykeln för honom. Det finns en algoritm för hur den ska fungera [10] :

1. Peggy omvandlar slumpmässigt grafen G. Genom att flytta punkterna och ändra deras etiketter skapar hon en ny graf H som är topologiskt isomorf till G. Sedan, genom att känna till Hamiltons cykel i G, kan hon lätt hitta den i H. Om hon inte hade skapat H själv, skulle det vara en alltför komplex uppgift att bestämma isomorfism mellan grafer, vars lösning kräver oerhört mycket tid. Hon krypterar sedan H och får grafen H'.

2. Peggy händer Victor H'.

3. Victor ber Peggy att antingen:

  1. Bevisa att H' är en krypterad isomorf kopia av G, eller
  2. Visa Hamiltons cykel för H.

4. Peggy uppfyller sin begäran. Hon antingen:

  1. Bevisar att H' är en krypterad isomorf kopia av G, som avslöjar transformationer och dechiffrerar allt, utan att visa en Hamiltonsk cykel för G eller H, eller
  2. Visar en Hamiltonsk cykel för H, dechiffrerar endast vad som utgör en Hamiltonsk cykel, utan att bevisa att H och G är topologiskt isomorfa.

5. Peggy och Victor upprepar steg 1-4 n gånger.

Om Peggy inte fuskar, kommer hon att kunna berätta för Victor något av bevisen i steg 3. Men om hon inte känner till Hamiltons cykel för G, kommer hon inte att kunna skapa ett H' som uppfyller båda bevisen. Det är sant att Peggy kan skapa antingen en graf som är isomorf till G, eller en graf med samma antal hörn och kanter och en riktig Hamiltonsk cykel. Och även om hon med 50 % sannolikhet kan gissa vilket bevis Victor kommer att begära vid steg 3, kan Victor upprepa protokollet tillräckligt många gånger tills han är säker på att Peggy känner till Hamiltons cykel i G.

Extrema problem i grafteorin: The travelling salesman problem

Den resande försäljaren behöver besöka varje stad inom ett visst territorium och återvända till utgångspunkten. Det krävs att vägen är så kort som möjligt. Därmed förvandlas det ursprungliga problemet till problemet att hitta minimilängden (varaktighet eller kostnad) [11] .

Problemet kan omformuleras i termer av grafteori - att konstruera en graf G(X, A), vars hörn motsvarar städer, och kanterna motsvarar kommunikationer mellan städer. Lösningen på detta problem söks bland Hamiltons cykler i den konstruerade grafen.

Det finns många sätt att lösa detta problem. De metoder som utvecklats av Bellmore och Nemhauser [12] , Garfinkel och Nemhauser [13] , Held och Karp [14] , Stekhan [15] kan särskiljas . Även kända lösningar på resandeförsäljarproblemet är branch and bound- metoden och metoden för successiv förbättring av lösningen [16] .

Relaterade termer

En semi-hamiltonsk [17] graf är en graf som innehåller en enkel kedja som passerar genom var och en av dess hörn exakt en gång. Dessutom är varje Hamiltonsk graf semi-hamiltonsk. Hamiltons cykel är en enkel spänncykel [ 18] .

Kärnan i Hamiltons cykelproblem  är att ta reda på om en given graf G har en Hamiltonsk cykel. Detta problem är NP-komplett [19] .

Hamiltonska orkedjan av en digraf [20]  är en enkel bana som passerar genom varje hörn av digrafen exakt en gång.

En Hamiltonian orcycle [20] är en orcycle [20] av en digraph som passerar genom var och en av dess hörn .

En digraf kallas semi -Hamiltonsk [20] om den har en Hamiltonsk eller Hamiltonsk kedja, och Hamiltonsk [20] om den har en Hamiltonsk ellercykel.

Se även

Anteckningar

  1. ↑ 1 2 M. O. Asanov, V. A. Baransky, V. V. Rasin. Diskret matematik: grafer, matroider, algoritmer. - Izhevsk: Regular and Chaotic Dynamics, 2001. - S. 41. - ISBN 5-93972-076-5 .
  2. ↑ Swami, Thulasiraman, 1984 , sid. 55.
  3. ↑ Harari, 2003 , sid. 16-17.
  4. ↑ O. Ore. Grafer och deras tillämpning. - Moskva: Mir, 1965. - S. 40-41.
  5. ↑ Dmitrij Maksimov. Vägar och vägar  // Vetenskap och liv . - 2020. - Nr 2 . - S. 81-86 .
  6. ↑ Harari, 2003 , sid. 86.
  7. ↑ 1 2 Harari, 2003 , sid. 87.
  8. ↑ Swami, Thulasiraman, 1984 , sid. 61.
  9. ↑ Grafer och algoritmer: Föreläsning 8: Euler och Hamiltons cykler . KÄNNA Intuit. Hämtad 20 november 2014. Arkiverad från originalet 29 november 2014.
  10. ↑ Schneier, 2002 , sid. 89-90.
  11. ↑ Mainika, 1981 , sid. 241-264.
  12. ↑ Bellmore M., Nemhuser G.L. The Travelling Salesman Problem: A. Survey. — ORSA vol. 16, 1968. - S. 538-558.
  13. ↑ Garfinkel R., Namhauser GL Heltalsprogrammering. - New York: John Wiley, Inc., 1972. - S. 354-360.
  14. ↑ Höll M., Karp R. Resande-försäljarproblemet och minsta spännande träd, del II // Math. Programmering. - 1971. - Vol. 1. - S. 6-25. - doi : 10.1007/BF01584070 .
  15. ↑ Steckhan H.A.-sats om symmetriska resande försäljarproblem. — ORSA, vol. 18, 1970. - S. 1163-1167.
  16. ↑ Mainika, 1981 , sid. 255-264.
  17. ↑ Wilson I.R., Eddiman A.M. En praktisk introduktion till Pascal. - Moskva: Radio och kommunikation, 1983. - S. 143.
  18. ↑ Tutt, 1988 .
  19. ↑ T. Cormen, C. Leizerson, R. Rivest. Algoritmer. Konstruktion och analys. - Moskva: MTSNMO, 2002. - S. 845-846.
  20. ↑ 1 2 3 4 5 Dolgikh, Petrenko, 2007 .

Litteratur

Länkar