MASARYKOVA UNIVERZITA

MASARYKOVA UNIVERZITA PŘÍRODOVĚDECKÁ FAKULTA

MINIMÁLNÍ KOSTRA GRAFU SEMESTRÁLNÍ PRÁCE Z PŘEDMĚTU TEORIE GRAFŮ

DATUM ODEVZDÁNÍ 21.5.2007

JIŘÍ KALINA, 150824

JIŘÍ KALINA

MINIMÁLNÍ KOSTRA GRAFU

1. OBSAH: 1. Obsah

2

2. Úvod

3

3. Kruskalův algoritmus

4

3.1. Minimální kostra grafu

4

3.2. Kruskalův algoritmus

4

3.3. Obrácený Kruskalův algoritmus

4

4. Mapa české železniční dítě

5

4.1. Definice prostředí

5

4.2. Úpravy mapy pro konstrukci grafu

5

5. Hledání minimální kostry

6

5.1. Zanedbání slepých tratí

6

5.2. Ohodnocení hran grafu přirozenými čísly

6

5.3. Postupné odebírání nadbytečných hran

6

2

JIŘÍ KALINA


2. ÚVOD: Součástí absolvování předmětu M5145 Teorie grafů na Přírodovědecké fakultě Masarykovy univerzity je zpracování semestrální práce, ve které student aplikuje jeden z probíraných algoritmů na určitý graf. Vzhledem k rozsahu učiva předmětu, významu semestrální práce a v neposlední řadě předpokládaným znalostem studentů v kurzu jde o poměrně mechanickou záležitost bez vlastní invence nebo snahy o řešení dosud neřešených problémů. Z takového pojetí nehodlá vybočit ani tato práce, autor však zastává názor, že pokud má být »pouze« uplatněn jednoduchý postup, bude zajímavější použít namísto uměle vymyšleného grafu se slabým nebo žádným vztahem ke skutečnosti graf reálný, se kterým se lze navíc poměrně často setkat. Takovým se jeví mapa české železniční sítě, která na první pohled připomíná obvyklá schémata užívaná při výkladu teorie grafů. Uzly (kterých je zjevně konečné množství) jsou značeny malými kružnicemi, hrany pak reprezentují přímky nebo křivky. Ve vybraném grafu neexistují smyčky, každé dva uzly jsou spojeny nejvýše jednou hranou, graf je přehledný a obsahuje řadu kružnic. Pro množství uzlů (426) však je bez využití počítače (a s ním pravděpodobně nejinak) řešení všech algoritmů časově velice náročné, proto byl zvolen nejjednodušší algoritmus hledání minimální kostry – tzv. obrácený Kruskalův algoritmus. Zadání práce tedy může znít například následovně: České dráhy, a. s. a Správa železniční dopravní cesty, s. o. se rozhodly v rámci snižování nákladů, restrukturalizace, optimalizace a racionalizace snížit délku české železniční sítě na minimum při zachování dopravní obslužnosti všech významných tarifních bodů (uvedených v mapě). Nalezněte takové řešení, kdy délka zachovaných tratí po racionalizaci bude minimální a přesto bude možné se dostat vlkem z libovolné stanice vyznačené v mapě do libovolné jiné vyznačené stanice. Cílem práce je čistě předvést aplikaci daného matematického algoritmu, přenesení výsledků do reality je samozřejmě nesmyslné a předpokládám, že poslouží zejména pro pobavení čtenáře svojí absurditou.

3

JIŘÍ KALINA


3. KRUSKALŮV ALGORITMUS 3.1. MINIMÁLNÍ KOSTRA GRAFU Minimální kostrou hranově ohodnoceného grafu [U, H, f] nazveme takový faktor [U, H*] tohoto grafu, který je stromem a pro který platí ([1]):

∑ f ( h) ≤ ∑ f ( h )

h∈H *

h∈H '

(1)

kde [U, H‘] je libovolný faktor grafu [U, H, f] a současně je stromem. Neboli platí, že má-li každá hrana určitou hodnotu, je minimální kostra grafu takový jeho faktor, kdy součet hran faktoru je co nejnižší číslo a z každého uzlu do každého je možné se dostat právě jednou cestou.

3.2. KRUSKALŮV ALGORITMUS Nalezení minimální kostry grafu podle Kruskala probíhá následovně ([2]): 1. Hrany z původní množiny H uspořádáme podle velikosti a indexujeme je vzestupně. 2. Vytvoříme prázdnou množinu H0*. 3. Přidáváme hrany hi z množiny H od nejníže hodnocené a zvyšujeme index i. 4. Vznikne-li přidáním hrany hi kružnice, ponecháme v tomto kroku Hi+1* = Hi*. Algoritmus je užitečný, konstruujeme-li minimální kostru grafu »od nuly«. V případě, kdy je však zadán kompletní graf a kostru tvoříme odebíráním existujících hran je užitečné využít následující obměny.

3.3. OBRÁCENÝ KRUSKALŮV ALGORITMUS Principielně jde o tentýž postup jako v odstavci 3.2., hrany se zde ale odebírají za dodržení souvislosti grafu: 1. Hrany z původní množiny H uspořádáme podle velikosti a indexujeme je sestupně. 2. Vytvoříme množinu H0* = H. 3. Odebíráme hrany hi z množiny H od nejvýše hodnocené a zvyšujeme index i. 4. Poruší-li se odebráním hrany hi souvislost, ponecháme v tomto kroku Hi+1* = Hi*. Obrácený Kruskalův algoritmus je výhodné použít v tomto případě zejména z technických důvodů, protože skutečně provádíme »odmazávání« hran grafu na obrázku v grafickém editoru.

4

JIŘÍ KALINA


4. MAPA ČESKÉ ŽELEZNIČNÍ SÍTĚ 4.1. DEFINICE PROSTŘEDÍ Mapa uvedená ve vydání jízdního řádu Českých drah pro období 2006 / 2007 (zdroj [3]) obsahuje celkem 426 uzlů, reprezentovaných významnějšími městy nebo uzlovými stanicemi. Uzly jsou spojeny několika druhy hran reprezentujících železniční tratě jedno-, dvou- a vícekolejné, úzkorozchodné, elektrifikované a provozované soukromými dopravci. Pro účely práce byly však všechny železnice zjednodušeně považovány za vzájemně rovnocenné. Výše zmíněná funkce f, ohodnocující hrany přirozenými čísly byla definována jako délka traťového úseku (hrany) podle Kilometrovníku pro přepravu cestujících a zavazadel ([4]).

4.2. ÚPRAVY MAPY PRO KONSTRUKCI GRAFU Přestože mapa uvedená v jízdním řádu je téměř dokonalým grafem v matematickém pojetí, bylo nutné pro potřeby práce provést několik detailních úprav: 1. Přeshraniční úseky od poslední stanice vyznačené v mapě byly zanedbány. 2. Peážní tratě byly považovány za tratě vnitrostátní, včetně vyznačených stanic. 3. Uzly Praha a Brno byly užity bez rozlišení jednotlivých stanic v rámci města. 4. Lanová dráha Liberec Horní Hanychov – Ještěd byla zanedbána.

5

JIŘÍ KALINA


5. HLEDÁNÍ MINIMÁLNÍ KOSTRY 5.1. ZANEDBÁNÍ SLEPÝCH TRATÍ Samotnou práci s využitím obráceného Kruskalova algoritmu je vhodné začít samozřejmě s pokud možno minimálním počtem hodnocených hran. Zcela zřejmé je, že v průběhu obráceného Kruskalova algoritmu nemůže dojít k vymazání slepých tratí (neboli hran, ne jejichž konci se nachází uzel stupně 1, protože po jejich vymazání by se z tohoto uzlu stal izolovaný uzel, což odporuje podmínce souvislosti), nebo hran podgrafů, které jsou stromy (tentýž problém), pročež lze před »spuštěním« algoritmu odebrat z grafu ty části, které nejsou součástí žádné kružnice (tedy slepé tratě a stromové systémy slepých tratí).

5.2. OHODNOCENÍ HRAN GRAFU PŘIROZENÝMI ČÍSLY Tratě, které zbývají po provedení kroku z odstavce 5.1., jsou nyní vždy zahrnuty alespoň v jedné kružnici grafu. Tyto železnice lze ohodnotit podle jejich délky, jak je uvedeno na obrázku v příloze 1. Červená čísla u příslušných traťových úseků odpovídají délce podle [4]:

5.3. POSTUPNÉ ODEBÍRÁNÍ NADBYTEČNÝCH HRAN Přesně v souladu s obráceným Kruskalovým algoritmem nyní odebírám traťové úseky od nejdelších po nejkratší tak, aby byla zachována souvislost grafu. Jako první byly odebrány shodně dlouhé nadbytečné trati (61 km) Ústí nad Labem Střekov – Mělník a Bečov nad Teplou – Blatno u Jesenice. Postup odebírání dalších tratí je vyznačen níže. Jelikož není minimální kostra obecně jednoznačně určena, stanovil jsem postup pro řešení sporných případů. Bylo-li možno odebrat dva stejně dlouhé úseky, odebíral jsem nejprve západnější z nich, v případě, že toto nebylo jednoznačné, byl odebrán severnější z obou úseků (což bylo zvoleno čistě proto, že jsem z jižní Moravy a mám rád železnice. Pozn. autora). Tratě s délkou větší než 20 km byly odebírány postupně podle následujícího pořadí, kratší tratě byly poté v několika málo zbývajících lokálních kružnicích odebrány podle délky bez zapisování. Před názvem traťového úseku je jeho kilometrická délka. Nebylo-li možné již úsek odebrat pro dodržení podmínky souvislosti grafu, je označen slovem NELZE. 61 Ústí nad Labem Střekov - Mělník 61 Bečov nad Teplou - Blano u Jesenice 56 Olomouc hlavní nádraží - Valšov 50 České Budějovice - České Velenice 49 Mělník - Mladá Boleslav hl. n. 48 Plzeň hl. n. - Klatovy 48 Nové město na Moravě - Tišnov 46 Obrataň - Jindřichův Hradec 44 Rakovník - Louny předměstí 44 Český Krumlov - Nová Pec 42 Litoměřice horní nádraží - Česká Lípa hl. n. 42 Březnice - Písek 40 Plzeň - Mladotice 40 Oldřichov u Duchcova - Děčín hlavní nádraží 40 Praha - Poříčany 40 Slavkov u Brna - Kyjov 39 Klatovy - Sušice 39 Vimperk - Volary 39 Olbramovice - Tábor 39 České Budějovice - Veselí nad Lužnicí 38 Liberec - Turnov 38 Čáslav - Světlá nad Sázavou 38 Moravské Budějovice - Znojmo

37 Čížkovice - Obrnice 37 Bor - Poběžovice 37 Vrané nad Vltavou - Čerčany 37 Jindřichův Hradec - Horní Cerekev 37 Lipník nad Bečvou - Olomouc hlavní nádraží 37 Újezdec u Luhačovic - Bylnice 36 Žatec - Krupá 36 Střelice - Studenec 35 Ostroměř - Hradec Králové hlavní nádraží 34 Praha - Neratovice 34 Písek - Milevsko 34 Kutná Hora město - Zruč nad Sázavou 34 Žďárec u Skutče - Polička 34 Chornice - Kostelec na Hané 34 NELZE Třeboň - České Velenice 33 Louny - Zlonice 33 Kladno - Lužná u Rakovníka 33 Bečov nad Teplou - Mariánské Lázně 32 Všetaty - Mladá Boleslav hlavní nádraží 32 NELZE Strakonice - Vimperk 32 NELZE Okříšky - Moravské Budějovice 32 Trutnov střed - Teplice nad Metují 32 Hanušovice - Lipová Lázně

6

JIŘÍ KALINA

MINIMÁLNÍ KOSTRA GRAFU 26 Brno - Holubice 26 Hranice na Moravě - Valašské Meziříčí 26 Bystřice pod Hostýnem - Valašské Meziříčí 25 Klášterec nad Ohří - Ostrov nad Ohří 25 Most - Chomutov 25 Ústní nad Labem Střekov - Děčín východ 25 NELZE Nepomuk - Horažďovice předměstí 25 NELZE Nepomuk - Blatná 25 Nelze Zábřeh na Moravě - Červenka 25 Brno - Vranovice 24 NELZE Tršnice - Sokolov 24 Neratovice - Čelákovice 24 NELZE Ledečko - Bečváry 24 NELZE Velké Meziříčí - Studenec 24 NELZE Obrataň - Tábor 24 NELZE Velký Osek - Chlumec nad Cidlinou 23 NELZE Pňovany - Plzeň hlavní nádraží 23 Chomutov - Žatec 23 Ústí nad Labem hl. n. - Děčín hlavní nádraží 23 Libochovice - Straškov 23 NELZE Všetaty - Lysá nad Labem 23 Praha - Hostivice 23 NELZE Praha - Vrané nad Vltavou 23 Dolní Bousov - Kopidlno 23 NELZE český šternberk - Zruč nad Sázavou 23 Týniště nad Orlicí - Opočno pod Orlickými horami 23 Veřovice - Frýdlant nad Ostravicí 22 Obrnice - Louny 22 Poběžovice - Staňkov 22 Planá u Mariánských Lázní - Svojšín 22 Ústí nad Labem hlavní nádraží - Lovosice 22 Olomouc hlaní nádraží - Přerov 22 NELZE Hanušovice - Bludov 22 Studénka - Ostrava Kunčice 21 Březno u Postoloprt - Obrnice 21 NELZE Lochovice - Příbram 21 Mikulášovice dolní nádraží - Rumburk 21 NELZE Hrádek nad Nisou - Liberec 21 Mladá Boleslav - Dolní Bousov 21 Libuň - Stará Paka 21 Moravany - Choceň 21 Červenka - Olomouc hlavní nádraží 20 Praha - Rudná u Prahy 20 Benešov nad Ploučnicí - Česká Lípa 20 Prostějov hlavní nádraží - Olomouc hlavní nádraží

32 Brno - Tišnov 31 Jablonné v Podještědí - Liberec 31 Stará Paka - Dvůr Králové nad Labem 33 Zruč nad Sázavou - Světlá nad Sázavou 31 NELZE České Budějovice - Český Krumlov 30 Praha - Zadní Třebáň 30 Doksy - Bakov nad Jizerou 30 Moravský Krumlov - Hrušovany nad Jevišovkou 30 Zábřeh na Moravě - Hanušovice 29 Hořovice - Rokycany 29 Křinec - Chlumec nad Cidlinou 29 Kolín - Přelouč 29 Hradec Králové hlavní nádraží - Častolovice 29 NELZE Volary - Prachatice 29 Jihlava - Okříšky 29 NELZE Krnov - Opava východ 28 Křivoklát - Beroun Závodí 28 NELZE Svitavy - Polička 28 Šumperk - Uničov 28 NELZE Opava východ - Ostrava Svinov 27 Blatno u Jesenice - Rakovník 27 NELZE Kralovice u Rakovníka - Rakovník 27 Rokycny - Nezvěstice 27 Blatná - Strakonice 27 Lochovic -Zadní Třebáň 27 Kralupy nad Vlatavou - Praha 27 Praha - Čelákovice 27 NELZE Prachaice - Číčenice 27 Mladá Boleslav - Veleliby 27 Čerčany - Ledečko 27 Chlumec nad Cidlinou - Ostroměř 27 Chlumec nad Cidlinou - Hradec Kr. hlavní nádraží 27 Svitavy - Letovice 27 Boskovice - Chornice 27 NELZE Obratň - Pelhřimov 27 NELZE Havlíčkův Brod - Jihlava 27 Mutěnice - Zaječí 27 Frýdek - Místek - Český Těšín 26 Úpořiny - Lovosice 26 Roudnice nad Labem - Vraňany 26 NELZE Tábor - Milevsko 26 NELZE Nýřany - Staňkov 26 NELZE Chrudim - Žďárec u Skutče 26 Doudleby nad Orlicí - Letohrad 26 Rudoltice v Čechách - Zábřeh na Moravě

Postupný stav české železniční sítě při odebírací racionalizaci lze vysledovat z příloh 2 – 4. Po odebrání posledního nadbytečného úseku byly do grafu opět přidány slepé tratě a stromové podgrafy odebrané v odstavci 5.1. Výsledek tak lze spatřit na příloze 5. Například cesta v oblíbené relaci Brno – Praha by probíhala po trase Brno – Nezamyslice – Senice na Hané – Zábřeh na Moravě – Hanušovice – Ústí nad Orlicí – Borohrádek – Pardubice hlavní nádraží – Hradec Králové hlavní nádraží – Trutnov Poříčí – Stará Paka – Nymburk hlavní nádraží – Všetaty – Kladno – Praha.

7

JIŘÍ KALINA


6. PRAMENY [1] FUCHS, Eduard. Kombinatorika a teorie grafů. Praha : Státní pedagogické nakladatelství, 1986. 138 s. [2] Kruskalův algoritmus [online]. 2007 , 16.2.2007 [cit. 2007-05-21]. Dostupný z WWW: . [3] Mapa sítě českých železnic [online]. 2007 [cit. 2007-05-21]. Dostupný z WWW: . [4] České dráhy, a. s.. Jízdní řád 2006/2007 : Úřední vydání Českých drah, a. s.. [s.l.] : [s.n.], 2006. 712 s.

8

JIŘÍ KALINA


PŘÍLOHA 1: OHODNOCENÉ HRANY V GRAFU BEZ SLEPÝCH TRATÍ A STROMOVÝCH PODGRAFŮ

9

JIŘÍ KALINA


PŘÍLOHA 2: GRAF PO ODMAZÁNÍ POVOLENÝCH HRAN S HODNOTOU VYŠŠÍ NEŽ 40

10

JIŘÍ KALINA



11

JIŘÍ KALINA



12

JIŘÍ KALINA


PŘÍLOHA 5: VÝSLEDNÁ MINIMÁLNÍ KOSTRA GRAFU

13

JIŘÍ KALINA


PŘÍLOHA 6: PŮVODNÍ SÍŤ BEZ PŘESHRANIČNÍCH ÚSEKŮ

14

MASARYKOVA UNIVERZITA

Recommend Documents