Student si může podle svých preferencí vybrat tyto typy semestrální práce:

A: prezentace některé kapitoly teorie grafů, která nebyla probrána na standardních přednáškách, nebo
B: implementace některého z algoritmů, které byly probrány, nebo
C: vlastní téma.

Témata pro práci typu A - prezentace:

• cirkulace (patří pod téma 'Toky v síti'), nalezení přípustné cirkulace
  
• algoritmus pro nalezení nejlevnější cirkulace
• metoda větví a mezí (prohledávání prostoru řešení) 
• existenční hamiltonovské úlohy (nutné a postačující podmínky existence hamiltonovské kružnice, postup nalezení hamiltonovské kružnice/cesty) 
  
• optimalizační hamiltonovské úlohy (nejkratší neorientovaná hamiltonovská cesta nebo nejkratší hamiltonovský cyklus nebo problém obchodního cestujícího) 
• jezdcova procházka (úloha TG) 
• hranová barevnost grafu 
• nalezení nejpočetnější nezávislé množiny
• platónovská a archimédovská tělesa (popis, vlastnosti, dualita, ...) 
• tranzitivní redukce grafu 
• minimax (algoritmus pro hraní strategických her)
• volby, turnaje a Concordetův paradox (nevím, jestli pro toto téma existuje literatura v češtině)

Témata pro práci typu B - algoritmus:

• algoritmus z předmětu 17TGA (Teorie grafů v dopravě)
  
  • minimální kostra (Kruskal, Jarník, Borůvka, ...)
  • nejkratší cesta (Dijkstra, Berge, Floyd, maticová metoda)
  • úloha čínského pošťáka
  • maximální tok v síti (Ford-Fulkerson, Dinic)
• prohledávání grafu do šířky
• prohledávání grafu do hloubky
• barevnost grafu