[ATG] Algoritmická teória grafov

BCKIS

[ATG] Algoritmická teória grafov

Výsledky vzdelávania:

Štúdiom predmetu študent získa základné poznatky z algoritmickej teórie grafov, ktoré mu umožňujú ich použitie pri riešení technických úloh v inžinierskej praxi.
Po absolvovaní predmetu študent:
– pozná základné štruktúry teórie grafov,
– pozná základné grafové algoritmy ,
– vie implementovať základné grafové algoritmy,
– má schopnosť aplikovať získané poznatky pri riešení praktických úloh.

Vysoká škola: Žilinská univerzita
Fakulta: Riadenia a informatiky
Kód predmetu: 5BA126Názov predmetu: algoritmická teória grafov (ATG)
Druh, rozsah a metóda vzdelávacích činností: 2 - 0 - 2 (prednášky-cvičenia-lab.cv.) hodín za týždeň, prezenčná metóda výučby.
Počet kreditov: 5.0
Odporúčaný semester/trimester štúdia: 4 semester
Stupeň štúdia: 1
Podmieňujúce predmety:
Podmienky na absolvovanie predmetu:
Priebežné hodnotenie:
40% = 40 bodov
Podmienkou pre úspešné absolvovanie cvičení k predmetu je systematická práca na cvičeniach posudzovaná splnením nasledujúcich kritérií:
- Aktívna účasť na cvičeniach
- Úspešné zvládnutie krátkych testov zameraných na základené definície zadávaných na každom cvičení
- Úspešné zvládnutie záverečného písomného testu v 12. týždni semestra
- Za náročnejšie počítačové implementácie môže dostať študent body naviac

Záverečné hodnotenie:
60% = 60 bodov
Podmienkou pre úspešné absolvovanie predmetu je získanie minimálne 61 zo 100 bodov za prácu v semestri a vykonanie skúšky z predmetu. Skúška je ústna a je zameraná hlavne na pochopenie pojmov a algoritmov.

Výsledné hodnotenie predmetu:
100 - 92 A
91 - 84 B
83 - 76 C
75 - 68 D
67 - 61 E

Pre prihlásenie sa na skúšku musí študent dosiahnuť najmenej 20.0 bodov
Výsledky vzdelávania:
Štúdiom predmetu študent získa základné poznatky z algoritmickej teórie grafov, ktoré mu umožňujú ich použitie pri riešení technických úloh v inžinierskej praxi.
Po absolvovaní predmetu študent:
- pozná základné štruktúry teórie grafov,
- pozná základné grafové algoritmy ,
- vie implementovať základné grafové algoritmy,
- má schopnosť aplikovať získané poznatky pri riešení praktických úloh.
Stručná osnova predmetu:
Stručná osnova predmetu:
Prednášky:
1. Základné pojmy teórie grafov: Základy kombinatoriky. Reprezentácia grafov.
2. Cesty v grafoch, súvislosť a prieskum grafov: Súvislosť a Tarryho algoritmus.
3. Algoritmy, výpočtová zložitosť a NP-ťažké úlohy: Výpočtová zložitosť a polynomiálne redukcia úloh.
4. Najkratšia cesta v grafe a digrafe. Hľadanie cyklov zápornej ceny: Algoritmy pre hľadanie najkratšej cesty v grafe a digrafe.
5. Stromy, kostra grafu a cesta maximálnej priepustnosti: Prehľadávanie grafu do šírky a do hĺbky, Kruskalov algoritmus a hľadanie cesty maximálnej priepustnosti.
6. Acyklické digrafy a úloha časového plánovania: Acyklické digrafy. Monotónne očíslovanie. Sieťová analýza-metóda CPM.
7. Toky v sieťach: Ford-Fulkersonov algoritmus pre maximálny tok v sieti.
8. Najlacnejší maximálny tok a ďalšie tokové úlohy: Najlacnejší maximálny tok v sieti.
9. Eulerovské ťahy. Párenia. Úloha čínskeho poštára: Algoritmy pre eulerovský ťah v grafe a digrafe, Edmonsov algoritmus pre úlohu čínskeho poštára.
10. Úloha obchodného cestujúceho: Heuristiky pre úlohu obchodného cestujúceho.
11. Mediány a centrá. Kliky, nezávislé množiny a pokrývacie množiny: Alokačné úlohy, nezávislá množina a klika.
12. Farbenie grafov: Farbenie grafov. Rovinné grafy

Cvičenia a laboratórne cvičenia:
1.Binárne relácie a opakovanie základov kombinatoriky.
2.Výpočtová zložitosť a polynomiálne redukcia úloh.
3.Súvislosť a Tarryho algoritmus.
4.Algoritmy pre hľadanie najkratšej cesty v grafe a digrafe. Hľadanie cyklu zápornej ceny.
5.Kruskalov algoritmus a hľadanie cesty maximálnej priepustnosti.
6.Acyklické digrafy. Monotónne očíslovanie. Sieťová analýza-metóda CPM.
7.Ford-Fulkersonov algoritmus pre maximálny tok v sieti.
8.Najlacnejší maximálny tok v sieti.
9.Algoritmy pre eulerovský ťah v grafe a digrafe, Edmonsov algoritmus pre úlohu čínskeho poštára.
10.Heuristiky pre úlohu obchodného cestujúceho.
11. Alokačné úlohy, nezávislá množina a klika.
12. Farbenie grafov. Rovinné grafy.
Odporúčaná literatúra:
Odporúčaná literatúra:
Palúch, S.: Teória grafov, EDIS, Žilina, ISBN 80-7100-874-5 (dostupné aj na http://frcatel.fri.uniza.sk/users/paluch/ resp. http://frcatel.fri.uniza.sk/users/paluch/grafy-ps.zip )
Plesník, J.: Grafové algoritmy, VEDA, SAV Bratislava 1983
Evans, J.,R., Minieka, E.: Optimizarion Algorithms for Networks and Graphs, Marcel Decker, New Yourk, second edition 1992, ISBN 0-8247-8602-5
Gross,J., Yellen, J.: Graph Theory and its Applications, CRC Press, 1998, ISBN 0-8493-3982-0
Jazyk, ktorého znalosť je potrebná na absolvovanie predmetu: slovenský/anglický
Poznámky:
Hodnotenie predmetov:
Celkový počet hodnotených študentov: 1121
ABCDEFX
25.16% 8.74%17.93% 8.30%14.99%24.89%
Vyučujúci:
Dátum poslednej zmeny: 11.8.2020 09:52:11
Schválil: Ing. Tomáš Majer, PhD.
Otázky:
1. Základné pojmy teórie grafov. Graf, digraf, ďalšie štruktúry TG, podgraf, úplný graf, stupeň vrchola, počet vrcholov nepárneho stupňa, izomorfizmus, komplementárnosť, reprezentácia grafov.

2. Cesty v grafoch. Sled, ťah, cesta, cyklus, polosled, poloťah, polocesta, polocyklus a ich analógie v digrafoch. Súvislosť grafov. Komponent grafu. Mosty a artikulácie. Tarryuho prieskum grafov.

3. Najkratšia cesta. Základný algoritmus, Dijkstrov a Floydov algoritmus. Label set a label correct implementácie algoritmov najkratšej cesty.

4. Stromy a ich vlastnosti. Veta o ekvivalentných výrokoch s výrokom \\\"graf G je stromom\\\". Prehľadávanie grafu do šírky a do hĺbky.

5. Kostra grafu, najlacnejšie a najdrahšia kostra grafu, Kruskalov algoritmus I. a II. Využitie pre hľadanie cesty maximálnej priepustnosti v grafe. Využitie Kruskalovho algoritmu na určenie komponentov grafu.

6. Acyklické digrafy a ich vlastnosti. Typy súvislosti v digrafoch - orientovaná, neorientovaná a silná súvislosť. Monotónne očíslovanie vrcholov grafu. Algoritmy na hľadanie najkratšej a najdlhšej cesty v acyklických digrafoch.

7. Časová analýza projektorv - metóda CPM. Dve možné reprezentácie (vrcholovo ohodnoteným resp.- hranovo ohodnoteným digrafom). Najskôr možný začiatok vykonávania činnosti a najneskôr nutný koniec vykonávania činnosti. Trvanie projektu. Kritické činnosti a kritická cesta.

8. Eulerovský ťah v grafe. Eulerovský graf. Kritérium pre to, aby bol graf eulerovský. Algoritmy na zostrojenie uzavretého eulerovského ťahu v grafe (Fleuryho, labyrintový, postupným rozširovaním uzavretého ťahu).

9. Úloha čínskeho poštára. Párenie v grafe. Edmondsov algoritmus na riešenie úlohy čínskeho poštára.

10. Úloha obchodného cestujúceho. Hamiltonovský cyklus a hamiltonovský graf. Postačujúce podmienky pre to, aby graf bol hmiltonovský. Metóda zdvojenia kostry a metóda kostry a párenia. Vytváracie a zlepšujúce heuristiky.

11. Algoritmy a ich zložitosť. Definícia symbolu $O(f(n))$, polynomiálne algoritmy. Polynomiálna redukcia a polynomiálna transformácia. Polynomiálne riešiteľné úlohy a NP-ťažké úlohy.


12. Alokačné úlohy - depá a havarijné strediská. Vážený p-medián a vážené p-centrum. Heuristický výmenný algoritmus. Atrakčné obvody.

13. Toky v sieťach. Dopravná sieť, zdroj, ústie. Tok -- definícia, veľkosť toku, maximálny tok. Rezová množina, Ford-Fulkersonova veta a algoritmus na hľadanie maximálneho toku v sieti. Algoritmus na hľadanie maximálneho toku s minimálnou cenou. Siete s viacerými zdrojmi a viacerými ústiami.

14. Rovinné grafy. Stena rovinného diagramu, Eulerov vzorec. Maximum počtu hrán rovinného grafu. Homeomorfizmus grafov. Prototypy najjednoduchších nerovinných grafov. Kuratowského veta.


15. Farbenie grafu, n-zafarbiteľnosť grafu, chromatické číslo grafu. Heuristiky na farbenie grafov. Praktické úlohy vedúce na riešenia úlohy farbenia grafu.
ZDROJ: https://vzdelavanie.uniza.sk/vzdelavanie/planinfo.php?kod=274633&lng=sk