Eulerovi putevi i ciklusi
Eulerovi putevi i ciklusi predstavljaju osnovu teorije grafova. Koriste se u problemima gde prolazimo kroz svaku granu tačno jednom.
Ovi koncepti imaju značajnu primenu u:
- planiranju ruta
- optimizaciji dostava
- prolasku kroz lavirinte
- rekonstrukciji DNK sekvenci (Eulerov graf De Bruinovih nizova)
Definicije
Eulerov put → put koji prolazi kroz svaku granu tačno jednom.
Eulerov ciklus → Eulerov put koji počinje i završava se u istom čvoru.
Uslovi postojanja:
| Tip | Uslov |
|---|---|
| Eulerov ciklus | Svi čvorovi imaju parnu stepen (degree) |
| Eulerov put | Tačno 0 ili 2 čvora imaju neparan stepen |
Ako ima više od 2 čvora neparnog stepena → nema Eulerovog puta.
Primer grafa
Posmatrajmo sledeći neusmeren graf:
(A)----(B)
| \ |
| \ |
| \ |
(D)----(C)----(E)
Stepeni čvorova:
A=3, B=2, C=4, D=3, E=1
Čvorovi sa neparnom stepenom su: A, D i E → nema Eulerovog puta jer ih je 3.
Fleuryjev algoritam
Fleuryjev algoritam gradi put tako što izbegava "mostove" dokle god je moguće.
1. Izaberi startni čvor (ako postoji, jedan od neparnih).
2. Dok ima neprolaženih grana:
a) ako postoji, biraj granu koja NIJE most
b) inače uzmi bilo koju
3. Kreni tom granom i ukloni je iz grafa.
C++ Implementacija
#include
using namespace std;
vector> g;
vector visited;
int degreeNonZero(){
for(int i=0;i " << v << endl;
g[u][v] = g[v][u] = 0;
fleury(v);
}
}
}
int main(){
int n = 5;
g.assign(n, vector(n,0));
g[0][1]=g[1][0]=1;
g[0][3]=g[3][0]=1;
g[0][2]=g[2][0]=1;
g[1][2]=g[2][1]=1;
g[2][3]=g[3][2]=1;
fleury(0);
}
Python verzija
g = {
0:[1,3,2],
1:[0,2],
2:[0,1,3],
3:[0,2]
}
def fleury(u):
while g[u]:
v = g[u].pop()
g[v].remove(u)
print(u, "->", v)
u = v
fleury(0)
Hierholzerov algoritam (za Eulerov ciklus)
Efikasniji i koristi se kada je poznato da graf ima Eulerov ciklus.
1. Kreni iz bilo kog čvora
2. Prati grane dok se ne vratiš u početni čvor → formira se ciklus
3. Ako postoje grane koje nisu posećene:
pronađi čvor tog ciklusa koji ima neiskorišćene grane
ponovi postupak i "ubaci" novi ciklus u postojeći
Vreme izvođenja: O(V + E)
Primer (Python)
def hierholzer(g, start):
stack = [start]
path = []
while stack:
u = stack[-1]
if g[u]:
v = g[u].pop()
g[v].remove(u)
stack.append(v)
else:
path.append(stack.pop())
return path
graph = {
0:[1,3], 1:[0,2], 2:[1,3], 3:[0,2]
}
print(hierholzer(graph,0)) # eulerov ciklus
Zadaci za vežbu
- Proveriti da li dati graf ima Eulerov put ili ciklus.
- Naći pravi redosled obilaska na primerima sa takmičenja.
- Napisati Fleury + detekcija mostova (napredno).
- Hierholzer za usmerene grafove.
Zaključak
Eulerovi putevi i ciklusi su ključni za dalje gradivo: Hamiltonovi putevi, mostovi, artikulisani čvorovi, SCC.
□ Sledeća preporučena lekcija: Mostovi i artikulisani čvorovi (Tarjan)