Práce se zabývá navržením algoritmu pro výpočet všech souvislých podgrafů daného bázového síťového grafu s omezující podmínkou výskytu vrcholu-zdroje a vrcholu-ústí v každém z podgrafů a následnou softwarovou realizací s vizuálním znázorněním podgrafů na zadaném grafu.
Anotace v angličtině
This work is dedicated to designing an algorithm for calculating all subgraphs of the network graph with restrictive condition. Each of subgraphs must contain edge-source and edge-sink. This part is followed by the creation of software for implementation this algorithm with graphic demonstration subgraphs on working graph.
Klíčová slova
graf, podgraf, Petriho síť, cesty v grafu, datové struktury
Klíčová slova v angličtině
graph, subgraph, Petri net, paths in graph, data structures
Rozsah průvodní práce
59 s. (60 000 znaků)
Jazyk
CZ
Anotace
Práce se zabývá navržením algoritmu pro výpočet všech souvislých podgrafů daného bázového síťového grafu s omezující podmínkou výskytu vrcholu-zdroje a vrcholu-ústí v každém z podgrafů a následnou softwarovou realizací s vizuálním znázorněním podgrafů na zadaném grafu.
Anotace v angličtině
This work is dedicated to designing an algorithm for calculating all subgraphs of the network graph with restrictive condition. Each of subgraphs must contain edge-source and edge-sink. This part is followed by the creation of software for implementation this algorithm with graphic demonstration subgraphs on working graph.
Klíčová slova
graf, podgraf, Petriho síť, cesty v grafu, datové struktury
Klíčová slova v angličtině
graph, subgraph, Petri net, paths in graph, data structures
Zásady pro vypracování
- Primárním cílem bakalářské práce je realizace softwarové podpory pro výpočet všech podgrafů daného bázového síťového grafu s omezující podmínkou výskytu vrcholu-zdroje a vrcholu-ústí v každém z podgrafů.
- Zmíněné podgrafy jsou graficky reprezentovány na podkladu bázového síťového grafu.
- Reprezentace grafu je postavena nad vhodnou abstraktní datovou strukturou umožňující efektivní implementaci výše zmíněného typu výpočtu.
- Pro testování cílové aplikace se použijí vybrané síťové grafy reprezentující specifické Petriho sítě (v rámci softwarového nástroje CPN Tools) datově popsané pomocí XML-souboru.
Zásady pro vypracování
- Primárním cílem bakalářské práce je realizace softwarové podpory pro výpočet všech podgrafů daného bázového síťového grafu s omezující podmínkou výskytu vrcholu-zdroje a vrcholu-ústí v každém z podgrafů.
- Zmíněné podgrafy jsou graficky reprezentovány na podkladu bázového síťového grafu.
- Reprezentace grafu je postavena nad vhodnou abstraktní datovou strukturou umožňující efektivní implementaci výše zmíněného typu výpočtu.
- Pro testování cílové aplikace se použijí vybrané síťové grafy reprezentující specifické Petriho sítě (v rámci softwarového nástroje CPN Tools) datově popsané pomocí XML-souboru.
Seznam doporučené literatury
1. CENEK, P. , KLIMA, V., JANÁČEK, J. Optimalizace dopravních a spojových procesů, Žilina, Univerzita Žilina, 1994.
2. VOLEK, J. Operační výzkum I., skripta DFJP UPa, Pardubice 2002
3. CORMEN a kol.: Introduction to algorithms, MIT Press, Cambridge, 2001
4. KAVIČKA, A., ŽARNAY, M.: Application of coloured Petri net for agent control and communication in the ABAsim architecture. In Proceeding of 9th workshop and tutorial on practical use of coloured Petri nets and the CPN Tools. K. Jensen (Ed.). Aarhus: University of Aarhus (Denmark), 2008. pp. 47-62. ISSN 0105-8571.
Seznam doporučené literatury
1. CENEK, P. , KLIMA, V., JANÁČEK, J. Optimalizace dopravních a spojových procesů, Žilina, Univerzita Žilina, 1994.
2. VOLEK, J. Operační výzkum I., skripta DFJP UPa, Pardubice 2002
3. CORMEN a kol.: Introduction to algorithms, MIT Press, Cambridge, 2001
4. KAVIČKA, A., ŽARNAY, M.: Application of coloured Petri net for agent control and communication in the ABAsim architecture. In Proceeding of 9th workshop and tutorial on practical use of coloured Petri nets and the CPN Tools. K. Jensen (Ed.). Aarhus: University of Aarhus (Denmark), 2008. pp. 47-62. ISSN 0105-8571.
Přílohy volně vložené
1 CD
Přílohy vázané v práci
grafy, schémata
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Cílem závěrečné práce byla realizace softwarové podpory pro výpočet všech podgrafů daného bázového síťového grafu s omezující podmínkou výskytu vrcholu-zdroje a vrcholu-ústí v každém z podgrafů. Stanovený cíl práce byl splněn, student prověřil tři variantní řešení specifikovaného problému, přičemž jedno z předložených řešení doporučil k aplikování jako výpočetně nejefektivnější. Logická a stylistická stránka bakalářské práce jsou na dobré úrovni. Implementační část práce
Výsledky práce lze potenciálně využít při budování stavových prostorů (reps. grafů dosažitelných značení) reflektujících specifické podtřídy barvených Petriho sítí.
Zkoušeny zodpověděl otázky vedoucího práce. Bakalářská práce byla vedoucím i zkušební komisí ohodnocena klasifikačním stupněm výborně, výsledek státní závěrečné zkoušky - výborně.