Cycle finding

Eulerův graf

Cycle finding je algoritmus s asymptotickou složitostí $O(\vert U \vert + \vert H \vert)$ , jenž slouží k nalezení Eulerovského tahu v zadaném grafu. Eulerovský tah je tah, který projde každou hranu právě jednou.

Aby mohl graf obsahovat Eulerovský tah, tak musí být souvislý a zároveň musí mít buď všechny vrcholy sudého stupně (algoritmus nalezne uzavřený tah) nebo právě 2 vrcholy lichého stupně (algoritmus nalezne otevřený tah).

Nejznámějším případem hledání Eulerovského tahu je problém sedmi mostů města Královce.

Princip

Cycle finding algoritmus je založený na jednoduché myšlence – pokud z Eulerova grafu odebereme libovolnou kružnici, tak je jeho zbytek stále Eulerův. Proto stačí graf organizovaně procházet a odebírat postupně všechny kružnice.

Toto lze zajistit procedurou, která začne v počátečním uzlu a postupně rekurzivně navštěvuje, analogicky s procházením do hloubky (DFS), všechny sousedy. Na rozdíl od DFS ale může navštívit každý uzel vícekrát, každou hranu však pouze jednou.

Procedura vypíše při každém návratu z rekurze identifikátor zdrojového uzlu hrany (aktuálního uzlu). Po terminaci algoritmu pak otočené pořadí identifikátorů odpovídá Eulerovskému tahu.

Kód

Pseudocode

/**
 * @param u vychozi uzel - pokud graf obsahuje 2 uzly licheho stupne, tak libovolny z nich. Pokud obsahuje pouze uzly sudeho stupne, tak libovolny uzel.
 * @param G graf
 * @param tour zasobnik, ktery agreguje Eulerovsky tah
 */
findTour(u, G, tour)
    for each edge e=(u,v) in Edges(G) do
        remove e from Edges(G)
        findTour(v, G, tour)
    tour.push(u)

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (0): 0

Přečtěte si také

Diskuse

Pavel Mička6.2.2011

S tou vhodností "maximálně" máš asi pravdu...změnil jsem to na "právě" :-)...dík za připomínku

Malevolent Cat6.2.2011

Pravda, zapomněl jsem, že skóre grafu musí být sudé, ale stejně mi příjde použití slůvká "právě" vhodnější než "maximálně", takto to naznačuje, že by mohl mít jeden vrchol lichého stupně, což ve skutečnosti mít nemůže. :-) Jinak je to samozřejmě správně, má chyba. Omlouvám se za zbytečný komentář. :-)

Pavel Mička5.2.2011

Malevolent Cat:
Ještě mě napadlo, že možná narážíš na to, že není souvislý...ale ta věta je postavená jako

souvislý A (sudé_stupně XOR 2_liché_stupně)

ale pokud se mi ozve víc lidí, že je ta formulace zavádějící, tak to nějak změním :-)

Pavel Mička5.2.2011

Malevolent Cat:
"Aby mohl graf obsahovat Eulerovský tah, tak musí být souvislý a zároveň musí mít buď všechny vrcholy sudého stupně (algoritmus nalezne uzavřený tah) nebo maximálně 2 vrcholy lichého stupně (algoritmus nalezne otevřený tah)."

Přiznám se, že tam tu nepřesnost nevidím :-)...to by mělo pokrývat všechny případy...pokud má všecho sudý, tak první případ, pokud má maximálně (tj. přesně dva, protože jeden mít nemůže), tak druhý případ...

Kdyžtak pastni přímo část se kterou nesouhlasíš :-)

Malevolent Cat5.2.2011

Jen malá nepřesnost: eulerovský tah je otevřený <=> obsahuje právě 2 vrcholy lichého stupně a je souvislý. Viz třeba Wiki: http://cs.wikipedia.org/wiki/Eulerovský_tah