Teorie grafů Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka ATCZ62 - CLIL jako výuková strategie na vysoké škole C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Teorie grafů •Graf – uspořádaná dvojice (V, E), kde •V je množina vrcholů •E je množina hran, každá hrana je určena právě dvěma vrcholy, volitelně pak směrem nebo váhou •Typy hran •Orientovaná – uspořádaná dvojice vrcholů (u,v), kde u je počátek, v je cíl •Neorientovaná - uspořádaná dvojice vrcholů (u,v) •Smyčky – hrana začíná a končí ve stejném vrcholu •Multihrana (násobná, paralelní, rovnoběžná) – mezi vrcholy (u,v) vede více hran C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Teorie grafů •Typy grafů •Orientovaný – všechny hrany jsou orientované •Neorientovaný – všechny hrany jsou neorientované •Multigraf – obsahuje multihrany •Terminologie •Sousedství •Všechny vrcholy, se kterými daný vrchol sousedí •Pokud dva vrcholy jsou spojeny hranou, tak spolu sousedí •Stupeň – deg(v) •Velikost sousedství stupně •deg+(v) – počet vstupních hran, deg-(v) – počet výstupních hran • • C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Teorie grafů •Sled •Posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími vrcholy je hrana •Tah •Sled, ve kterém se neopakují hrany •Cesta •Sled, ve kterém se neopakují vrcholy •Cyklus (kružnice) •Uzavřená posloupnost vrcholů C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Teorie grafů •Aplikace •Elektronické obvody •Přepravní sítě •Počítačové sítě •Databáze • C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Graf – ADT C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Graf – DFS – depth-first search Prohledávání do hloubky •Algoritmus je úplný, ale není ideální •Expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil •Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byli všichni navštíveni), vrací se zpět backtrackingem. • void DFS (Graph G) { for (Node u in U(G)) { stav[u] = FRESH; p[u] = null; } i = 0; for (Node u in U(G)) if (stav[u] == FRESH) DFS-Projdi(u); } void DFS-Projdi(Node u) { stav[u] = OPEN; d[u] = ++i; for (Node v in Adj[u]) if (stav[v] == FRESH) { p[v] = u; DFS-Projdi(v); } stav[u] = CLOSED; f[u] = ++i;} C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Graf – BFS – Breadth-first search Prohledávání do šířky •projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti void BFS (Graph G, Node s) { for (Node u in U(G)-s) { stav[u] = FRESH; d[u] = nekonečno; p[u] = null; } stav[s] = OPEN; d[s] = 0; p[s] = null; Queue.Init(); Queue.Push(s); while (!Queue.Empty()) { u = Queue.Pop(); for (v in Adj[u]) { if (stav[v] == FRESH) { stav[v] = OPEN; d[v] = d[u]+1; p[v] = u; Queue.Push(v); }} stav[u]=CLOSED;}} C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Graf – hledání nejkratší cesty •Dijkstrův algoritmus •Konečný, funguje pouze na kladně ohodnoceném grafu •O(|V|2+|E|) – V je počet vrcholů, E počet hran •Bellmanův-Fordův algoritmus •Graf může obsahovat i záporné hrany •O(V·E) – pomalejší než Dijsktrův alg. •Floydův-Warshallův algoritmus •Orientovaný graf s kladnými hranami •Nalezne nejkratší cestu mezi všemi vrcholy •Časová náročnost – O(V3), paměťová náročnost O(V2) C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ VKBw/image001.png Fachhochschulen Oberösterreich Graf – hledání nejkratší cesty •Johnsonův algoritmus •Orientovaný graf, může mít i záporné hrany •V řídkých grafech je rychlejší, než Floydův-Warshallův algoritmus •Dokáže rozpoznat záporný cyklus v grafu a výpočet ukončit •využívá Bellmanův-Fordův algoritmus, s jehož pomocí přehodnotí hrany tak, aby žádná neobsahovala zápornou hodnotu •Po přehodnocení hran používá Dijkstrův algoritmus k nalezení nejkratších cest mezi všemi uzly. •O(V2 log2(V)+ VE)