Fleuryjev algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Vsebina

Opis Fleuryjevega algoritma za Eulerjev obhod

  • ker iščemo obhod(to pomeni, da točko zapustimo in se moramo po drugi povezavi vrniti v njo),zato najprej preverimo ali imajo vse točke sodo število povezav
    • če pogoj ni izpolnjen, končamo (saj ne dobimo obhoda)
  • sicer nadaljujemo z izbiro začetne točke
  • prečkamo poljubno povezavo iz izbrane začetne točke, paziti moramo le, da ne prečkamo mostu (MOST je po definiciji takšna povezava v grafu, da njena odstranitev poveča število povezanih komponent grafa)
    • v primeru, da nimamo na voljo nobene druge povezave, moramo izbrati most
  • povezavo, ki smo jo prečkali "odstranimo", to pomeni da za nas ni več prehodna, saj je prehod čez povezavo možen natanko enkrat
  • postopek ponavljamo dokler ne prečkamo vseh povezav, pri čemer moramo končati v začetni točki



Dejansko lahko celo zadevo poenostavljeno opišemo takole: Dokler ne pregledamo vseh možnih povezav, ne smemo iti preko mostu, ker se ne bomo mogli vrniti. Ko pa je nujno, gremo preko mostu v drugi del.

Primer

Primer 1

Primer prikazuje (eno) konkretno pot Eulerjevega obhoda s pomočjo Fleuryjevega algoritma z začetkom v točki 2.

Slika:Graf2.png

Vsaka točka ima sodo število povezav, zato lahko nadaljujemo z izbiro začetne točke. Izbrala sem si točko 2, na voljo imam povezave a, b, g, i. Izberem povezavo b, ter jo odstranim.

Slika:Graf3.png

Tako pridem v točko 3, kjer lahko izbiram med c, e, f povezavami. Izberem f, ter pridem v točko 6.

Slika:Graf4.png

Od tu lahko prečkam povezave i, k ali h. Izberem slednjo, ki me pripelje v točko 5.

Slika:Graf14.PNG

Tokrat smo naleteli na primer, kjer je ena izmed možnih povezav most -to je povezava.

Slika:Graf5.png

Ker imam poleg te na voljo še dve povezavi e in d mostu(g) ne smem izbrati, saj bi graf razpadel na dva nepovezana dela.

Slika:Graf6.png

Torej si izberem povezavo d, ki me pripelje v točko 4.

Slika:Graf7.png

Iz te točke lahko pridem v točko 3 samo po povezavi c.

Slika:Graf8.png

Nato po povezavi e v točko 5.

Slika:Graf9.png

Zopet smo naleteli na primer, kjer je povezava most. Razlika je v tem, da je to edina možnost za izbiro, zato moramo izbrati most(g), ter prispemo v točko 2.

Slika:Graf10.png

Na voljo ostaneta povezavi a in i. Izberem a, ki me vodi v točko 1. Slika:Graf11.png

Iz točke 1 imam edino možnost po povezavi k do točke 6.

Slika:Graf12.png

Na izbiro mi ostane še povezava i, ki me pripelje v mojo izbrano začetno točko. Slika:Graf13.png

Primer 2

Primer ko Eulerjev obhod ni možen, ker nimajo vse točke sodo šteilo povezav. Slika:Grafaa.png

Vir

Fleuryjev algoritem

Glej tudi

Osebna orodja