Section outline

  • Mitja Trampuš

    Vsebina:

    1. Kaj je graf
      • Cestna omrežja, prijateljstva
      • Drevo, cikel, usmerjen graf, utežen graf
    2. Predstavitve grafov
      • Matrika sosednosti
      • Seznam sosedov
      • Implicitna predstavitev (npr. premikanje po gridu)
    3. DFS (iskanje v globino) z rekurzijo
      • Pazi na cikle
    4. DFS z ročno vodenim stackom
    5. BFS (iskanje v širino)
    6. Povezanost v neusmerjenih grafih. Komponente za povezanost
    7. Dvodelnost in 2-obarvljivost
    8. Intermezzo: Lahki nalogi za začetnike
      • Facebook friend suggest
      • Height map grid, iz zgornjega levega vogala izvira voda. Bo pritekla v spodnji desni vogal?
    9. Premer drevesa
    10. DAG (usmerjen acikličen graf) in topološko urejanje
    11. Najmanjše vpeto drevo (Minimum spanning tree)
    12. Najkrajše poti
      • Bellman-Fordov algoritem
      • Dijkstrov algoritem
      • Warshall-Floydov algoritem (bo razložil Janez v četrtek)
    13. Eulerjev obhod
    14. Problem trgovskega potnika (Travelling salesperson problem). Hamiltonov obhod (opis problema, NP-težkost)