2014

11.12.2015

Teorie grafů Radim Farana Podklady pro výuku pro akademický rok 2013/2014

Obsah Kostra grafu. Tahy, Eulerovské tahy. Úloha čínského pošťáka. Zdroj: Vítečková, M., Přidal, P. & Koudela, T. Výukový modul k předmětu Systémová analýza [on-line]. Dostupný z webu:

Kostra grafu Kostra grafu – podgraf původního grafu, který obsahuje všechny jeho uzly, a současně je stromem. Minimální kostra grafu – je taková kostra grafu, která má minimální součet ohodnocení hran.

1

11.12.2015

Minimální kostra grafu

Zařazovací algoritmus  Označovaný také jako Jarníkův Vojtěch Jarník algoritmus (v zahraničí známý jako * 22. 12. 1897, Praha + 22. 9. 1970, Praha Primův algoritmus případně Dijkstrův algoritmus)  Hrany seřadíme podle ohodnocení od do neklesající posloupnosti.  Vezmeme diskrétní podgraf původního grafu obsahující pouze vrcholy.  Procházíme seřazený seznam hran, pokud hrana připojuje další nepřipojený uzel, zařadíme ji do kostry.

http://inserv.math.muni.cz/biografie/ vojtech_jarnik.html

Zařazovací algoritmus  Borůvkův algoritmus. Otakar Borůvka 1. V celém grafu se vyberou dvě * 10. 5. 1899, Ostrožské Předměstí + 22. 7. 1995, Brno hrany s nejnižším ohodnocením. 2. V dalších krocích se vždy vybere další hrana s minimálním ohodnocením tak, aby netvořila cyklus s již dříve vybranými hranami. 3. Krok 2 se opakuje až do vybrání celkového počtu (n – 1) hran, které budou tvořit hledanou minimální kostru grafu.

http://inserv.math.muni.cz/biografie/otakar_boruvka.html

2

11.12.2015

Eulerovské tahy  Eulerovský tah je takový tah, který obsahuje všechny hrany právě jednou. Orientované Leonhard Paul Euler Basilej, Švýcarsko grafy obsahují orientované tahy a neorien- *+15.18.4.9.1707 1783 Petrohrad, Rusko tované grafy obsahují neorientované tahy.  Uzavřené Eulerovské tahy jsou takové tahy, u kterých je počáteční a koncový uzel totožný.  Neuzavřené Eulerovské tahy jsou takové tahy, které nemají totožný počáteční a koncový uzel.  „Jednotažky“ jsou všechny hrany nakresleny jedním tahem. http://www.converter.cz/fyzici/euler.htm

Neuzavřená jednotažka

Uzavřená jednotažka

Eulerovské tahy  Typy úloh  Rozhodnout, zda v daném grafu existuje otevřený nebo uzavřený Eulerovský tah.  V daném grafu sestrojit otevřený nebo uzavřený Eulerovský tah.  V daném grafu najít nejmenší počet tahů, nikoli Eulerovských, které pokrývají všechny hrany grafu.  V daném souvislém grafu (mezi každými dvěma uzly existuje hrana), jehož hrany jsou ohodnoceny kladnými čísly, máme za úkol najít nejkratší uzavřený sled, který obsahuje každou hranu alespoň jednou. (Úloha čínského pošťáka).

Eulerovské tahy  Věta 1:  Nechť graf G je neorientovaný, pak v grafu existuje neorientovaný uzavřený Eulerovský tah právě tehdy, když každý uzel grafu je sudého stupně.  Věta 2:  Nechť graf G je orientovaný, pak v grafu G existuje orientovaný uzavřený Eulerovský tah právě tehdy, když pro každý uzel grafu platí, že počet hran vstupujících do uzlu je roven počtu hran z uzlu vystupujících.

3

11.12.2015

Algoritmus pro hledání uzavřeného Eulerovského tahu

 Musí být zajištěna platnost věty 1 nebo 2. V algoritmu se pak střídavě prodlužují dvě fáze:  Existující tah prodlužujeme, dokud se nestane uzavřeným.  Uzavřený tah kontrolujeme, zda je Eulerovský. Při kontrole procházíme podél tahu a v každém uzlu x testujeme, zda v okolí uzlu x existuje hrana, která dosud neleží v tahu. Jestliže ano, pak přerušíme kontrolu, tah v uzlu x rozpojíme a začneme jej prodlužovat. Prodlužování skončí v uzlu x. Po rozpojení nového a starého tahu pokračujeme v kontrole počínaje uzlem x a postupujeme podél nové části tahu. Takto je zajištěno, že jak při prodlužování, tak i při kontrole postupujeme podél každé hrany pouze jednou. Celý postup je tedy velmi rychlý.

Eulerovské tahy Věta 3: Nechť G je neorientovaný souvislý graf, který obsahuje k uzlů lichého stupně, pak nejmenší počet neorientovaných tahů pokrývajících všechny hrany grafu je k/2. Počet uzlů lichého stupně v grafu: k = 4  2 tahy.

Eulerovské tahy  Věta 4:  V souvislém orientovaném grafu je právě jeden Eulerovský tah neuzavřený právě tehdy, když graf je souvislý a existují-li v něm dva uzly u1, u2, pro které platí: d  u1   d  u1   1, d  u 2   d  u 2   1,

kde je: d+( u1) - počet hran vstupujících do uzlu u1, d-( u2) - počet hran vystupujících z uzlu u2. Pak uzel u1 je počáteční uzel a uzel u2 je koncový uzel neuzavřeného Eulerovského tahu. Pro ostatní uzly platí d+(u) = d-(u). u1 = 4 – 3 – 2 – 1 – 4 – 2 = u2

4

11.12.2015

Algoritmus čínského pošťáka Pošťák musí při roznášce pošty alespoň jedenkrát projít každou ulicí svého rajónu. Jak má postupovat, aby ušel co nejméně kilometrů, to znamená, aby kratší cesty procházel vícekrát? 1. Zjistit, zda jsou všechny uzly sudého stupně. 2. Není-li tomu tak, musíme přidat hrany, abychom tuto podmínku splnili a to provedeme tak, že spojíme uzly s lichým stupněm nejkratší cestou. 3. Provedeme kontrolu, zda cesta pošťáka je opravdu nejkratší. 

5