Přednášky:
1. Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci. Prohledávání grafů - základní algoritmus, prohledávání do šířky a do hloubky; zjišťování dostupnosti vrcholů.
2. Nejkratší cesty - základní algoritmus, modifikovaný alg., Bellman-Fordův algoritmus; úpravy algoritmů při hledání nejdelších cest. Topologické uspořádání vrcholů a hran - užití topolog. uspořádání k hledání nejkratších cest; test acykličnosti grafu.
3. Souvislé a silně souvislé grafy. Komponenty souvislosti - pomocí mocnin matice sousednosti (jejich součtová matice); Floydův algoritmus - testování existence cyklů se zápornou cenou.
4. Kostra grafu - Jarníkův a Borůvkův algoritmus. Souvislost s nejkratšími cestami v neorientovaném grafu. Kruskalův a Primův algoritmus.
5. Párování v bipartitních grafech - maximální párování, nejlevnější párování v bipartitních grafech. Maximální párování v obecných grafech - redukce grafu.
6. Eulerovské tahy - podmínky existence; algoritmus pro nalezení eulerova tahu v grafu (pokud existuje); úloha čínského pošťáka.
7. Vrcholové a hranové barvení grafu. Rovinné grafy.
8. Toky v sítích - maximální tok - ekvivalence úlohy maximálního párování v bipartitním grafu a maximálního toku v specifické síti; Ford-Fulkersonův algoritmus; přípustný tok v síti. Nejlevnější cirkulace v síti.
9. Heuristické algoritmy - izomorfismus, kliky a nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
10. Komplexní sítě, jejich typy a vlastnosti (small world effect, clustering, scale-free nets).
11. Modely sítí (náhodné sítě, Watts-Strogatz model, bezeškálové sítě).
12. Chyby, útoky, robustnost, stabilita, hledání v sítích, ...
Cvičení:
Demonstrace jednotlivých algoritmů na konkrétních příkladech.
Reprezentace grafů, prohledávání grafů.
Nejkratší cesty, topologické uspořádání vrcholů a hran, souvislé a silně souvislé grafy, komponenty souvislosti
Kostra grafu. Eulerovské tahy
Párování v bipartitních grafech, maximální párování v obecných grafech.
Vrcholové a hranové barvení grafu. Rovinné grafy.
Toky v sítích, nejlevnější cirkulace v síti.
Heuristické algoritmy - nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
Projekty:
Cílem projektu je vytvořit aplikaci demonstrující schopnost studenta porozumět grafovým algoritmům a implementovat je.
1. Reprezentace grafů - graficky, maticově, seznamem hran nebo seznamem vrcholů a jejich sousedů; volba reprezentace grafu v závislosti na aplikaci. Prohledávání grafů - základní algoritmus, prohledávání do šířky a do hloubky; zjišťování dostupnosti vrcholů.
2. Nejkratší cesty - základní algoritmus, modifikovaný alg., Bellman-Fordův algoritmus; úpravy algoritmů při hledání nejdelších cest. Topologické uspořádání vrcholů a hran - užití topolog. uspořádání k hledání nejkratších cest; test acykličnosti grafu.
3. Souvislé a silně souvislé grafy. Komponenty souvislosti - pomocí mocnin matice sousednosti (jejich součtová matice); Floydův algoritmus - testování existence cyklů se zápornou cenou.
4. Kostra grafu - Jarníkův a Borůvkův algoritmus. Souvislost s nejkratšími cestami v neorientovaném grafu. Kruskalův a Primův algoritmus.
5. Párování v bipartitních grafech - maximální párování, nejlevnější párování v bipartitních grafech. Maximální párování v obecných grafech - redukce grafu.
6. Eulerovské tahy - podmínky existence; algoritmus pro nalezení eulerova tahu v grafu (pokud existuje); úloha čínského pošťáka.
7. Vrcholové a hranové barvení grafu. Rovinné grafy.
8. Toky v sítích - maximální tok - ekvivalence úlohy maximálního párování v bipartitním grafu a maximálního toku v specifické síti; Ford-Fulkersonův algoritmus; přípustný tok v síti. Nejlevnější cirkulace v síti.
9. Heuristické algoritmy - izomorfismus, kliky a nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
10. Komplexní sítě, jejich typy a vlastnosti (small world effect, clustering, scale-free nets).
11. Modely sítí (náhodné sítě, Watts-Strogatz model, bezeškálové sítě).
12. Chyby, útoky, robustnost, stabilita, hledání v sítích, ...
Cvičení:
Demonstrace jednotlivých algoritmů na konkrétních příkladech.
Reprezentace grafů, prohledávání grafů.
Nejkratší cesty, topologické uspořádání vrcholů a hran, souvislé a silně souvislé grafy, komponenty souvislosti
Kostra grafu. Eulerovské tahy
Párování v bipartitních grafech, maximální párování v obecných grafech.
Vrcholové a hranové barvení grafu. Rovinné grafy.
Toky v sítích, nejlevnější cirkulace v síti.
Heuristické algoritmy - nezávislé množiny, Hamiltonovský cyklus, úloha obchodního cestujícího.
Projekty:
Cílem projektu je vytvořit aplikaci demonstrující schopnost studenta porozumět grafovým algoritmům a implementovat je.