kerovac Ne znam da negdje postoji definirano al ovako sam ga ja shvatila:
1) Izrada zatvarača grafa
Prvo moraš napraviti zatvarač grafa. U auditornima kaže da se prvo dodaju unutarnji bridovi, a zatim vanjski ako je to moguće. No to se ne može raditi bilo kojim redoslijedom (u smislu, ne možeš samo doći i random povezivati npr. čvor A s F ili D jer su to unutarnji bridovi). Zapravo tražiš 2 vrha koja nisu susjedna (tj nisu spojeni bridom) a da zbroj njihovih stupnjeva bude barem jednak broju vrhova (u ovom slučaju 7). Ako pogledaš svi vrhovi imaju stupnjeve 2 (A, E) ili 3 (B, D, F, G) i njihov zbroj nikad neće biti jednak 7 (2+2 = 4, 2+3 = 5, 3+3 = 6). Osim C. C ima stupanj 4 i kad ga se zbraja s ovima koji imaju 3, to daje 7 (npr. deg© + deg(F) = 4+3 = 7). Super, našli smo koje čvorove bi mogli uzeti u obzir za dodavanje novog brida. Sad se vraćamo na ono “ne smiju biti susjedi”. Od ovih ponuđenih (B, D, F, G) C nije spojen jedino s G, dakle to nam je jedina opcije za dodavanje bridova. Dodamo brid cg i označimo ga brojem 1 jer je prvi dodan.
Nakon toga , gledamo dalje situaciju. Sad C ima stupanj 5, a njegov jedini ne-susjed je E sa stupnjem 2, dakle u zbroju je 7, možemo i njih spojiti i označiti taj brid brojem 2.
I tako se ide dalje ovisno o tome kako se situacija sa stupnjevima mijenja. Ako u nekom trenutku imaš više opcija koji brid možeš dodati, uvijek prije dodaj unutarnji a za kraj ostavi vanjske.
2) Odabir Hamiltonovog ciklusa
Uzmeš neki Hamiltonov ciklus, ja sam krenula od ovog vanjskog prstena.
3) Izgradnja Hamitonovog ciklusa iz početnog grafa
Cilj je što prije riješiti se ovih dodanih bridova. Zato se kao prvi uv brid uzima EF (ima prioritet 11). Zatim ideš dalje po ciklusu i biraš svoj pq brid. Nebitno je li E=u, a F=v ili obratno, samo kod biranja p i q moraš biti konzistentan (dakle ako si išao u smjeru kazaljke na satu pa je E=v, a F=u, onda obavezno ideš dalje u smjeru kazaljke na satu pa je npr. za odabrani brid AG, A=p i G=q). Ja sam išla u suprotnom smjeru, odabrala brid AG jer mi je to bio prvi brid na koji sam naišla a da je dodan kao dio zatvarača. Mogla sam odabrati i neki drugi brid (npr. AB), isto bi bilo dobro, ali evo odlučila sam se za ovaj. Mogla sam odabrat i neki koji nije naknadno dodan u zatvaraču, ali cilj nam je što prije riješiti se dodanih bridova (jer tražimo ciklus u originalnom grafu). Budući da se spajaju p i u te q i v, dodala sam bridove EG i AF (oba su manjeg prioriteta!) te izbrisala EF i AG. Nakon toga ide iduća iteracija u kojoj sam odabrala AB kao uv (brid s najvećim prioritetom) i EG (sljedeći brid po ciklusu koji je naknadno dodan u zatvaraču).
U 5. koraku kad je samo 1 brid naknadno dodan, njega se odabere kao uv, dakle A=u, F=v. Nakon toga gledaš dalje po ciklusu. Sljedeći brid je FG - njega ne možemo odabrati jer pq ne smije imati zajedničke vrhove s uv (a imao bi F).
Dakle gledamo dalje, sljedeća mogućnost je GB - njega bi teoretski mogli odabrati jer ne dijeli vrhove s AF, aali ima jedan problem. Ako GB odaberemo kao pq, onda će G=p a B=q, što zapravo znači da bi trebali spojiti A i G te B i F. No, ako se vratimo par koraka unazad, vidit ćemo da smo brid AG već maknuli + ima veći prioritet (9), nego AF (8). Čitaj: nema smisla to dodavati i vratit se u krug (nez ni jel bi smjeli zbog prioriteta).
Sljedeća mogućnost je BC, ali to je ista priča kao s AG, makli smo brid AB i taj brid je imao prioritet 10, dakle ćorak, ni to nije dobra opcija.
Sljedeći na redu je brid CD i s njim nemamo problema kao s ovim prethodnima: bridove CA i DF nismo još dodavali (+ DF ima prioritet 6, što je manje od 8).
Mislim da su ovim načinom razmišljanja došli do toga da u tom koraku odaberu baš CD brid kao pq.
Dakle kad tako ostane samo 1 brid koji je naknadno dodan, za ovaj sljedeći je bitno pripaziti da:
- ne dijeli vrhove s uv bridom i
- da bridove koje bi trebali dodati nisu već micani (tj. da nemaju veći prioritet od našeg uv brida)
Dalje se samo nastavlja s algoritmom.
Evo nadam se da je pomoglo, malo mi je teško natipkati objašnjenje. 😅
