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.

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).