Može li se nacrtati figura jednim potezom, bez podizanja olovke i bez prelaženja iste linije dva puta? To je pitanje da li graf ima Eulerov put – put koji prolazi kroz svaku granu tačno jednom. Odgovor zavisi samo od stepena čvorova, a sam put nalazi Hierholzerov algoritam.
Za neusmeren graf u kome su sve grane u jednoj komponenti:
| Broj čvorova neparnog stepena | Rezultat |
|---|---|
| 0 | postoji Eulerov ciklus (put se vraća u početni čvor) – kreće se iz bilo kog čvora |
| 2 | postoji Eulerov put – počinje u jednom, a završava se u drugom čvoru neparnog stepena |
| više od 2 | ne postoji |
Zašto: svaki put kada prođemo kroz čvor, koristimo jednu ulaznu i jednu izlaznu granu, pa unutrašnji čvorovi puta moraju imati paran stepen. Samo početak i kraj mogu biti neparni.
Za usmeren graf: ciklus postoji ako je za svaki čvor broj ulaznih grana jednak broju izlaznih; put postoji ako jedan čvor ima jednu izlaznu granu više (početak), jedan jednu ulaznu više (kraj), a svi ostali su uravnoteženi.
Čuveni problem sedam mostova Königsberga (Kenigsberga) nema rešenje jer sva četiri dela grada imaju neparan stepen.
Krećemo iz početnog čvora i idemo neiskorišćenim granama dok ne zaglavimo. Kada iz čvora više nema neiskorišćenih grana, on ide u rezultat i vraćamo se korak nazad – odatle eventualno krećemo u novi „krug“ koji se umeće u put. Rezultat se dobija obrnutim redom. Svaka grana se koristi jednom, pa je složenost O(n + m).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graf(n + 1); // (sused, redni broj grane)
vector<int> stepen(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graf[u].push_back({v, i});
graf[v].push_back({u, i});
stepen[u]++;
stepen[v]++;
}
// početak: čvor neparnog stepena, ako postoji; inače bilo koji čvor sa granom
int start = 1, neparnih = 0;
for (int v = 1; v <= n; v++) if (stepen[v] > 0) { start = v; break; }
for (int v = 1; v <= n; v++)
if (stepen[v] % 2 == 1) {
if (neparnih == 0) start = v;
neparnih++;
}
if (neparnih != 0 && neparnih != 2) {
cout << "NE POSTOJI" << endl;
return 0;
}
vector<bool> iskoriscena(m, false);
vector<size_t> sledeca(n + 1, 0); // od koje grane dalje gledamo listu čvora
vector<int> stek = {start}, put;
while (!stek.empty()) {
int v = stek.back();
while (sledeca[v] < graf[v].size() && iskoriscena[graf[v][sledeca[v]].second]) sledeca[v]++;
if (sledeca[v] == graf[v].size()) { // nema više grana iz v
put.push_back(v);
stek.pop_back();
} else {
auto [u, id] = graf[v][sledeca[v]];
iskoriscena[id] = true; // prelazimo granu v-u
stek.push_back(u);
}
}
if ((int)put.size() != m + 1) { // nisu sve grane u istoj komponenti
cout << "NE POSTOJI" << endl;
return 0;
}
reverse(put.begin(), put.end());
for (size_t i = 0; i < put.size(); i++) cout << put[i] << (i + 1 < put.size() ? " " : "\n");
return 0;
}
Algoritam je napisan sa sopstvenim stekom umesto rekurzije, jer put može imati milion grana. Niz sledeca čuva dokle smo stigli u listi suseda, da se iste (već iskorišćene) grane ne bi proveravale iznova.
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Figura je zadata kao neusmeren povezan graf (tačke i linije). Ispiši CIKLUS ako se može nacrtati jednim potezom tako da se završi u početnoj tački, PUT ako može, ali ne u početnoj tački, i NE ako ne može.
4 5
1 2
2 3
3 4
4 1
1 3PUT3 3
1 2
2 3
3 1CIKLUS4 3
1 2
1 3
1 4NE1. Kada neusmeren povezan graf ima Eulerov ciklus?
2. Graf ima 4 čvora neparnog stepena. Da li ima Eulerov put?
3. Koja je složenost Hierholzerovog algoritma?
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:
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.
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 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.
#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);
}
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)
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)
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
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)