Izziv 6 - Algoritmi nad grafi

Naloga 1

Narišite usmerjeni graf na 6 vozliščih z (najmanj) 10 povezavami ter zanj določite vhodne/izhodne stopnje vseh vozlišč. Graf opišite s seznamom sosedov, matriko sosednosti in incidenčno matriko.

Naloga 2

Za usmerjen graf iz naloge 1 določite število poti dolžine 4 med vsemi vozlišči. 

Naloga 3

Za polni neusmerjeni graf na 6 vozliščih določite število trikotnikov.

Naloga 4

Za usmerjen graf iz naloge 1 prikažite sledenje v globino (DFS), pri čemer izpišite tako vhodni kot izhodni vrstni red obiska. Začnite z vozliščem 0.

Naloga 5

Za graf iz naloge 1 prikažite sledenje v širino  (BFS), pri čemer izpišite vrstni red obiska. Začnite z vozliščem 0.

Naloga 6

Usmerjen graf iz naloge 1 popravite tako, da bo acikličen ter na njem prikažite postopek topološkega urejanja vozlišč (na katerikoli način).

Naloga 7

Za usmerjen graf iz naloge 1 določite in urejeno izpišite vse krepko povezane komponente (na katerikoli način).