Teorija grafova
sa primjenama
| |
Smjer: |
Teorijska kompjuterska nauka |
| |
Semestar: |
VII |
| |
Tip kursa: |
Obavezni |
| |
Fond sati: |
3+2+0 |
| |
Broj
ECTS kredita: |
8 |
Nastavni program:
- Pregled osnovnih
pojmova i definicija teorije grafova;
- Prolasci kroz grafove;
BFS i DFS pretraga; Primjene DFS i BFS pretrage;
- Problem najkraćeg
drveta; Primov algoritam; Kruskalov algoritam;
- Problem najkraćeg puta;
Dijkstra algoritam; Belmann-Fordov algoritam;
- Problemi protoka:
Algoritam Forda Fulkersona za maksimalni protok;
- Veza problema
minimalnog puta, protoka i linearnog programiranja;
- Matrične metode u
teoriji grafova; Unimodularnost incidentne matrice;
- Hamiltonijani (kola);
“prebrojivi“ algoritam;
- Optimizacije nad
grafovima;
- Upravljanje projektima:
tehnike PERT-CPM;
Literatura:
- D. Cvetković, M. Milić:
Teorija grafova i primene, Naučna knjiga, Beograd, 1977
-
Hillier S. F.: Lieberman G.J.:
Introduction to operations research, 7th Edition, McGrow Hill
Book Co. 2001
-
Martello S.: Fondamenti di Ricerca
operativa L-A, Esculapio (progetto Leonardo), Bologna, 2004
-
Krčevinac S., Čangalović M., Kovačević-Vučić
V., Martić M., Vujošević M.: Operaciona istraživanja, Fakultet
organizacionih nauka, Beograd, 2004.
-
Encyclopedia of Operations Research and
Management Sciance, 2nd
Edition, Kluwer, 2000