Teorija grafov

Avtor:

Gal Gantar, 3. e

Mentor:

Klemen Bajec

Ključne besede:

teorija grafov, implementacija grafa, algoritmi na grafih, NP težavnost, vizualizacija

Povzetek:

Teorija grafov je veja matematike, ki se ukvarja z grafi. Grafi so diskretne matematične strukture, ki jih posredno uporabljamo na vsakodnevni ravni, ne da bi se tega sploh zavedali. Teorija grafov je osnova tehnologij, ki so v zadnjih 30 letih spremenile tako tehnološki svet, kot tudi vsakdanje življenje. Cilj te raziskovalne naloge je predstavitev nekaj osnovnih pojmov teorije grafov, njihovih lastnosti in zakonitosti. Kot praktičen izdelek je vključena tudi implementacija grafa v programskem jeziku Python in izdelava grafičnega vmesnika za vizualizacijo algoritmov, ki jih uporabljamo za delo z grafi.