2.7 Ojlerovi i Hamiltonovi putevi

U nekim grafovskim problemima potrebno je pronaći put između dva čvora koji posećuje svaku granu grafa tačno jednom ili, dualno, put koji posećuje svaki čvor grafa tačno jednom. U ovom poglavlju bavićemo se problemima ispitivanja da li u grafu postoje ovakve vrste puteva. Iako ova dva problema na prvi pogled nalikuju, pokazaće se da se tehnike za njihovo rešavanje značajno razlikuju.

2.7.1 Ojlerovi putevi i ciklusi

Razmotrimo naredni problem: poštar treba da dostavi određen broj pisama na različite adrese u nekoliko susednih ulica. Poštar gleda u mapu i uočava na koji način su te ulice međusobno povezane. Crta pojednostavljenu mapu i pritom svaku od raskrsnica označava nekim brojem. Poštar želi da dostavi sva pisma, a da pritom svakim putem prođe tačno jednom. Postavlja se pitanje da li je to moguće uraditi. Ovaj problem moguće je modelovai u terminima grafova: svaka raskrsnica predstavlja čvor grafa, a put koji vodi od jedne raskrsnice do druge granu grafa. Dati problem se onda svodi na pitanje da li u grafu postoji put koji sadrži svaku granu grafa tačno jednom.

Ojlerov put (engl. Eulerian trail, Eulerian path) je put u grafu koji prolazi kroz svaku granu grafa tačno jednom (pri čemu neke čvorove može posetiti i više puta). Ojlerov ciklus (engl. Eulerian circuit, Eulerian cycle) je Ojlerov put čiji se početni i krajnji čvor poklapaju.

U nastavku ćemo se baviti određivanjem Ojlerovih puteva i ciklusa.

Pojam Ojlerovih grafova u vezi je sa, kako se smatra, prvim rešenim problemom teorije grafova. Švajcarski matematičar Leonard Ojler naišao je 1736. godine na sledeći zadatak. Grad Kenigsberg, danas Kalinjingrad, leži na obalama i na dva ostrva na reci Pregel, kao što je prikazano na slici 3, levo. Grad je povezan putem sedam mostova. Pitanje koje je mučilo mnoge tadašnje građane Kenigsberga bilo je da li je moguće početi šetnju iz bilo koje tačke u gradu i vratiti se u polaznu tačku, prelazeći pri tome svaki most tačno jednom. Ovaj problem se može formulisati kao sledeći problem iz teorije grafova: da li je moguće u neusmerenom povezanom grafu pronaći ciklus, koji svaku granu grafa sadrži tačno jednom, tj. Ojlerov ciklus. Drugim rečima, da li je moguće nacrtati graf sa slike 3, desno, ne dižući olovku sa papira, tako da olovka svoj put završi na mestu sa koga je i krenula. Napomenimo da ovaj graf ima višestruke grane između parova čvorova, pa strogo gledano po definiciji nije graf, već multigraf. Ojler je dokazao da je ovakav obilazak moguć ako i samo ako je graf povezan i svi njegovi čvorovi imaju paran stepen (teorema 2.7.1 u nastavku). Grafovi koji sadrže Ojlerov ciklus zovu se Ojlerovi grafovi. Pošto “graf” na slici 3, desno, ima čvorove neparnog stepena, zaključujemo da problem Kenigsberških mostova nema rešenje.

Pre nego što dokažemo karakterizaciju Ojlerovih grafova preko stepena čvorova, dokažimo jednu lemu.

Primetimo da Ojlerov put i Ojlerov ciklus može postojati i u nepovezanom grafu, ukoliko graf, pored jedne povezane komponente, sadrži samo izolovane čvorove (slika 4).

Dokaz. Lako je pokazati da ako u grafu postoji Ojlerov ciklus, onda svi čvorovi grafa moraju imati paran stepen. Naime, za vreme obilaska ciklusa, u svaki čvor se ulazi isto toliko puta koliko puta se iz njega izlazi. Pošto se svaka grana prolazi tačno jednom, broj grana susednih proizvoljnom čvoru mora biti paran.

Da bismo indukcijom dokazali da je ovaj uslov i dovoljan da bi graf imao Ojlerov ciklus, moramo najpre da izaberemo parametar po kome će biti izvedena indukcija. Taj izbor treba da omogući smanjivanje problema, bez njegove promene. Ako uklonimo čvor ili granu iz grafa, stepeni čvorova u dobijenom grafu nisu više svi parni. Treba da uklonimo takav skup grana \(S\), da za svaki čvor \(u\) grafa \(G\) broj grana iz skupa \(S\) susednih sa \(u\) ostane paran (makar i \(0\)). Proizvoljan ciklus zadovoljava ovaj uslov, a na osnovu leme 2.7.1 svaki graf čiji su svi čvorovi parnog stepena sadrži neki ciklus. Sada možemo da formulišemo induktivnu hipotezu i dokažemo teoremu.

Induktivna hipoteza. Povezani neusmereni graf sa manje od \(m\) grana čiji svi čvorovi imaju paran stepen sadrži Ojlerov ciklus, koji se može efektivno pronaći.

Posmatrajmo graf \(G=(V,E)\) koji sadrži \(m\) grana u kom svi čvorovi imaju paran stepen. Neka je \(P\) neki ciklus u grafu \(G\) (koji postoji, na osnovu leme 2.7.1), i neka je \(G'\) graf dobijen uklanjanjem grana ciklusa \(P\) iz grafa \(G\). Stepeni svih čvorova u grafu \(G'\) su parni, jer je broj uklonjenih grana susednih bilo kom čvoru paran. Ipak se induktivna hipoteza ne može primeniti na graf \(G'\), jer on ne mora biti povezan (slika 5). Neka su \(G_1', G_2', \ldots, G_k'\) komponente povezanosti grafa \(G'\). U svakoj komponenti povezanosti stepeni svih čvorova su parni. Pored toga, broj grana u svakoj komponenti je manji od \(m\) jer je ukupan broj grana u svim komponentama manji od \(m\). Prema tome, induktivna hipoteza se može primeniti na svaku od komponenti posebno: u svakoj komponenti \(G_i'\) postoji Ojlerov ciklus \(P_i'\), i mi znamo da ga pronađemo. Potrebno je sada sve ove cikluse objediniti sa pomoćnim ciklusom \(P\) u jedan Ojlerov ciklus za graf \(G\). Polazimo iz proizvoljnog čvora ciklusa \(P\) (“magistralnog puta”) sve dok ne dođemo do nekog čvora \(v_j\) koji pripada nekoj komponenti \(G_j'\). Tada obilazimo komponentu \(G_j'\) ciklusom \(P_j'\) (“lokalnim putem”) i vraćamo se u čvor \(v_j\). Nastavljamo obilazak ciklusa \(P\) na taj način, obilazeći cikluse komponenti u trenutku nailaska na njih. Na kraju obilaska ćemo se vratiti u polazni čvor. U tom trenutku sve grane grafa \(G\) smo prošli tačno jednom, što znači da je konstruisan Ojlerov ciklus.

Ovaj dokaz sugeriše efikasan rekurzivni algoritam za konstrukciju Ojlerovog ciklusa u grafu. \(\Box\)

Videli smo da neusmereni graf može imati Ojlerov put, a da istovremeno nema Ojlerov ciklus (slika 1). Naredna lema (koja se dokazuje veoma jednostavno) daje potreban i dovoljan uslov da neusmeren graf ima Ojlerov put.

U grafu sa slike 1 čvorovi \(B\) i \(C\) su neparnog stepena, dok su ostali čvorovi parnog stepena, te čvorovi \(B\) i \(C\) predstavljaju početni i krajnji čvor Ojlerovog puta. Dodatno, u ovom grafu ne postoji Ojlerov ciklus.

Situacija je slična i u usmerenim grafovima. Naredna lema daje potreban i dovoljan uslov da u usmerenom grafu postoji Ojlerov put.

Primer 2.7.2. U grafu prikazanom na slici 6 su ulazni i izlazni stepeni čvorova \(A\), \(E\) i \(D\) međusobno jednaki, ulazni stepen čvora \(B\) je veći za jedan od izlaznog, dok je ulazni stepen čvora \(C\) za jedan manji od izlaznog stepena. U ovom grafu postoji Ojlerov put koji počinje u čvoru \(C\), a završava se u čvoru \(B\) (npr. \((C,D,E,B,C,A,B)\)), dok Ojlerov ciklus ne postoji.

Hirholcerov algoritam

Iako se iz dokaza teoreme 2.7.1 može izdvojiti ideja za konstrukciju Ojlerovog ciklusa u povezanom neusmerenom grafu kod koga su stepeni svih čvorova parni, potrebno je precizirati detalje implementacije da bi se umesto rekurzivne dobila efikasna iterativna implementacija. Jedan efikasan način za konstruisanje Ojlerovog ciklusa u Ojlerovom grafu predstavlja Hirholcerov algoritam, zasnovan na ideji prikazanoj u dokazu teoreme 2.7.1. Algoritam se može primeniti i na neusmerene i na usmerene grafove. On se sastoji od nekoliko etapa, pri čemu se u svakoj etapi prethodno pronađeni ciklus proširuje narednim ciklusom u novi, veći ciklus. Postupak se zaustavlja kada se sve grane grafa dodaju u ciklus (i to je konačan, Ojlerov ciklus).

Polazi se iz proizvoljnog čvora \(u\) u grafu. U svakom koraku prelazi se proizvoljnom neposećenom granom do nekog suseda trenutnog čvora. Ovaj korak se ponavlja sve dok se ne vratimo u polazni čvor \(u\). U njega se moramo vratiti u nekom momentu, jer je stepen svakog čvora paran. Na ovaj način konstruiše se inicijalni ciklus. Ukoliko on prolazi skupom svih grana, Ojlerov ciklus je konstruisan. Inače, ciklus se proširuje na sledeći način: polazeći iz čvora \(u\) duž ciklusa pronalazi se prvi čvor \(v\) koji pripada tekućem ciklusu i koji ima granu koja nije uključena u ciklus (u slučaju usmerenog grafa vraćamo se unazad duž ciklusa i tražimo prvi čvor koji ima izlaznu granu koja nije uključena u ciklus). Tom granom se kreće u otkrivanje novog ciklusa koji se sastoji isključivo od grana koje još uvek nisu u prethodnom ciklusu. Put se pre ili kasnije vraća u čvor \(v\) i time se pronalazi novi ciklus koji dodajemo u tekući ciklus. Na ovaj način se od ova dva ciklusa konstruiše novi ciklus. Postupak se nastavlja dok pronađeni ciklus ne obuhvati sve grane grafa.

Čvorove inicijalnog ciklusa stavljamo na stek u redosledu obilaska. Naime, stek nam omogućava da se efikasno vraćamo unazad kroz ciklus tražeći čvor iz kog nisu sve grane posećene i iz kojeg možemo da započnemo novi ciklus. Ako je to čvor na vrhu steka, krećemo obilazak novog ciklusa dodajući njegove čvorove na vrh steka. U suprotnom, ako su sve grane čvora na vrhu steka posećene, završili smo obradu tog čvora i njega dodajemo na početak niza čvorova koji određuje Ojlerov ciklus. Primetimo da ni u jednom trenutku ne moramo eksplicitno da proveravamo da li smo se vratili u početni čvor tekućeg ciklusa. Kada stek postane prazan, to znači da smo za sve čvorove razmotrili sve grane koje polaze iz njih, tj. da su sve grane obrađene i da je Ojlerov ciklus konstruisan.

Ako graf \(G\) sadrži samo Ojlerov put, a ne i Ojlerov ciklus, algoritam započinje svoj rad iz čvora čiji je izlazni stepen za jedan veći od ulaznog. Alternativno, u graf \(G\) se može dodati grana kojom se postiže uslov da graf ima Ojlerov ciklus i zatim iskoristiti prethodni algoritam. Nakon pronalaska Ojlerovog ciklusa u dopunjenom grafu, ta grana se uklanja iz ciklusa i na taj način ostajemo sa Ojlerovim putem.

U nastavku je prikazana implementacija Hirholcerovog algoritma koji pronalazi Ojlerov ciklus u usmerenom grafu. Pretpostavlja se da su svi čvorovi parnog stepena, pa obilazak može da krene iz proizvoljnog čvora (u implementaciji obilazak uvek kreće od čvora 0).

vector<int> pronadjiOjlerovCiklus() {
  // rezultujuci ciklus, odredjen cvorovima kroz koje se prolazi 
  vector<int> ojlerovCiklus;
   
  // stek na koji stavljamo cvorove u redosledu obilaska
  stack<int> tekuciPut;

  // na stek dodajemo polazni cvor
  tekuciPut.push(0);

  // sve dok postoji neki cvor na tekucem putu
  while (!tekuciPut.empty()) {
    int tekuciCvor = tekuciPut.top();
    
    // ako iz tekuceg cvora postoji jos neka grana koju nismo posetili
    if (listaSuseda[tekuciCvor].size() > 0) {
      // pronalazimo cvor do koga postoji grana iz tekuceg cvora;
      // uzimamo poslednji iz liste povezanosti jer je njega lako
      // ukloniti iz liste povezanosti
      int naredniCvor = listaSuseda[tekuciCvor].back();
      // brisemo granu iz tekuceg ka narednom cvoru
      listaSuseda[tekuciCvor].pop_back();
      
      // napredujemo ka narednom cvoru
      tekuciCvor = naredniCvor;
      tekuciPut.push(naredniCvor);
    }
    // ako iz tog cvora ne postoji neposecena grana
    else {
      // cvor dodajemo u Ojlerov ciklus
      ojlerovCiklus.push_back(tekuciCvor);
      // vracamo se unazad da bismo nasli preostale cikluse
      tekuciPut.pop();
    }
  }
  // obrcemo cvorove u ciklusu
  reverse(begin(ojlerovCiklus), end(ojlerovCiklus));
  
  return ojlerovCiklus;
}

Vreme izvršavanja Hirholcerovog algoritma u usmerenom grafu koji je predstavljen listama povezanosti iznosi \(O(|E|)\). Naime, ukoliko je \(|V|>|E|\), onda graf ima izolovane čvorove koji se tokom algoritma ne razmatraju. Istaknimo i to da ukoliko je graf neusmeren, onda prilikom brisanja neke grane, treba obrisati obe njene kopije: \((u,v)\) i \((v,u)\), što je operacija koja se ne izvršava efikasno u slučaju reprezentacije grafa listama povezanosti. Stoga je Hirholcerov algoritam u slučaju neusmerenog grafa manje efikasan.

Ako se traži Ojlerov put (a ne ciklus), algoritam se primenjuje u istom obliku, jedino što izvršavanje mora da počne od čvora čiji je izlazni stepen za jedan veći od ulaznog.

Flerijev algoritam

Drugi poznati algoritam za konstrukciju Ojlerovih ciklusa ili puteva u grafu, pored Hirholcerovog, je i Flerijev algoritam (engl. Fleury’s algorithm). On kreće od proizvoljnog čvora i u svakom koraku tekući put proširuje nekom granom iz tekućeg čvora, koju zatim uklanja iz grafa. Ako je moguće, bira se grana koja nije most tj. grana koja ne razbija graf na više komponenata povezanosti. Ako takva grana ne postoji, onda se put proširuje granom koja jeste most. Naime, ako bismo izabrali granu koja je most kada iz tog čvora postoji još neka grana, prešli bismo u komponentu povezanosti kojoj ne pripada taj čvor i ne bismo mogli da se vratimo do njega i da prođemo tom granom. Naglasimo da iako polazni Ojlerov graf sigurno nema mostova, oni se mogu pojaviti tokom izvršavanja algoritma, jer se grafu izbacuju grane.

Ovaj algoritam se zasniva na detekciji mostova u grafu u svakom koraku i manje je efikasan – njegova složenost iznosi \(O(|E|^2)\). Postoje inkrementalni aloritmi za detekciju mostova čijom se upotrebom složenost algoritma može popraviti, ali Flerijev algoritam i dalje ostaje složeniji i neefikasniji od Hirholcerovog, pa ga nećemo dalje analizirati.

2.7.2 Hamiltonovi putevi i ciklusi

Jedan od važnih problema u bioinformatici jeste mapiranje genoma, gde je zadatak iskombinovati veliki broj malih fragmenata genetskog koda u jedinstvenu genomsku sekvencu. Ovaj problem se može razmatrati kao grafovski: svaki od fragmenata odgovara čvoru grafa, a svako preklapanje (poklapanje kraja nekog fragmenta sa početkom nekog drugog) grani grafa. Pitanje koje se postavlja jeste da li je moguće napraviti prost put u grafu koji prolazi kroz svaki čvor grafa tačno jednom.

Hamiltonov put (engl. Hamiltonian path) je put koji posećuje svaki čvor grafa tačno jednom. Ako Hamiltonov put počinje i završava se u istom čvoru on se naziva Hamiltonov ciklus (engl. Hamiltonian cycle, Hamiltonian circuit).

Graf koji sadrži Hamiltonov ciklus zove se Hamiltonov graf (engl. Hamiltonian graph). Hamiltonovi ciklusi dobili su ime u čast Vilijama Hamiltona koji je 1857. godine izumeo slagalicu koja uključuje potragu za ovom vrstom ciklusa u grafu sačinjenom od ivica dodekaedra.

Prirodno se razmatra problem određivanja Hamiltonovih ciklusa.

Za razliku od problema Ojlerovih ciklusa, problem nalaženja Hamiltonovih ciklusa (odnosno karakterizacije Hamiltonovih grafova) je vrlo težak. Da bi se proverilo da li je graf Ojlerov, dovoljno je znati stepene njegovih čvorova. Za utvrđivanje da li je graf Hamiltonov to nije dovoljno. Zaista, dva grafa prikazana na slici 9 imaju po \(16\) čvorova stepena \(3\) (dakle imaju isti broj čvorova i iste stepene čvorova), ali je prvi Hamiltonov, a drugi očigledno nije. Problem ispitivanja da li je dati graf Hamiltonov spada u klasu NP-kompletnih problema, pa nije poznato da li postoji subeksponencijalni algoritam za njegovo rešavanje.

Algoritam grube sile podrazumeva proveru svih permutacija čvorova i njegova složenosti je \(O(|V|!)\), što je izrazito neefikasno.

Moguće je dizajnirati algoritam zasnovan na dinamičkom programiranju čija bi složenost bila donekle bolja \(O(|V|\cdot 2^{|V|})\). Osnovna ideja je da se rešavaju potproblemi oblika: “Za fiksirani početni čvor \(u\), skup čvorova \(S\) i završni čvor \(v\), da li postoji put koji počinje iz čvora \(u\), prolazi kroz sve čvorove iz \(S\) i završava se čvorom \(v\)”. Obeležimo ovu logičku vrednost sa \(\mathit{DP}(S, v)\). Bazu čini prazan skup \(S\) i tada \(\mathit{DP}(\emptyset, v)\) važi tačno za čvorove \(v\) za koje postoji grana \((u, v)\). Za neprazne skupove \(S\) važi \(\mathit{DP}(S, v)\) ako i samo ako postoji \(v' \in S\) tako da važi \(\mathit{DP}(S \setminus \{v\}, v')\) i postoji grana \((v', v)\). Na kraju, Hamiltonov ciklus postoji ako postoji neki čvor \(v\) takav da važi \(\mathit{DP}(V \setminus \{u\}, v)\) i postoji grana \((v, u)\).

Mi se u ovom udžbeniku nećemo detaljnije baviti Hamiltonovim putevima i ciklusima.

Zadaci:

• De Brujnov niz