Teorija 5 - Algoritmi nad grafi
Naloga 1
Za enostavni neusmerjeni graf (z vsaj 6 vozlišči) določite število vozlišč, število povezav in stopnje vseh vozlišč.
Graf opišite s seznamom sosedov, matriko sosednosti in incidenčno matriko.
Naloga 2
Za enostavni usmerjeni graf (z vsaj 6 vozlišči) določite število vozlišč, število povezav in vhodne in izhodne stopnje vseh vozlišč.
Graf opišite s seznamom sosedov, matriko sosednosti in incidenčno matriko.
Naloga 3
Za neusmerjen graf iz naloge 1 določite število poti dolžine 2 (3, 18). Pojasnite razlike za primer usmerjenega grafa.
Naloga 4
Za graf iz naloge 1 določite število trikotnikov.
Naloga 5
Za usmerjen graf iz naloge 2 prikažite sledenje v globino (DFS), pri čemer izpišite tako vhodni kot izhodni vrstni red obiska. Začnite z vozliščem 0.
Naloga 6
Za graf iz naloge 2 prikažite sledenje v širino (BFS), pri čemer izpišite vrstni red obiska. Začnite z vozliščem 0.
Naloga 7
Usmerjen graf iz naloge 2 popravite tako, da bo acikličen ter na njem prikažite postopek topološkega urejanja vozlišč (na oba načina).