|
Šifra modula |
AMAT 380 |
Fakultet |
PMF Sarajevo |
Teorija grafova
NASTAVNI PROGRAM
A. OPŠTI PODACI
|
Fakultet |
Prirodno-matematički fakultet Univerziteta u
Sarajevu |
|
Odsjek |
Odsjek za matematiku |
|
Smjer |
Primijenjena matematika; Teorijska kompjuterska
nauka |
|
Semestar |
Šesti |
|
Naziv modula |
Teorija grafova |
|
Tip modula |
Obavezni |
|
Broj kreditnih bodova |
6 |
|
Kontakt sati |
Ukupno |
Predavanja |
Vježbe |
Seminari |
Konsultacije |
|
90 |
45 |
30 |
15 |
po potrebi |
|
Samostalni rad (sati) |
60 |
|
Obavezni prethodno položeni moduli |
Uvod u matematičku logiku; Uvod u linearnu
algebru |
|
Modul relevantan za module |
Moduli II ciklusa studija |
|
Nastavno osoblje |
|
|
– Nastavnik nosilac modula |
Doc. dr. Haris Gavranović |
|
– Ostali nastavnici |
– |
|
– Asistenti |
Damir Hasić; Mr. Almasa Odžak; Mr. Vedad Letić |
B. CILJEVI MODULA
|
Ciljevi modula su
upoznavanje sa osnovnim elementima teorije grafova i njenim
primjenama. Jedan od najvažnijih ciljeva je pokazati na koji način
modelirati problema pomoću grafova i kako ih onda rješavati ili
barem definisati odgovarajuće problema. |
C. SPECIFIČNI ZADACI MODULA
D. OČEKIVANI REZULTATI NASTAVNOG
PROCESA
E. SADRŽAJ NASTAVNOG PROCESA
P – Predavanja; AV – Auditorne
vježbe; LV – Laboratorijske vježbe
|
Br. |
Nastavna jedinica |
Nastavni metod |
Sati rada |
|
Kontakt |
Samostalno |
|
1. |
Osnovni pojmovi i definicije, graf kao model |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
2. |
isomorfismi, specijalni grafovi i dekompozicije
grafova |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
3. |
Povezanost, bipartitni grafovi, eulerovi
grafovi, grafovi intervala, Stepeni cvorova i prebrojavanje grafova |
Usmeno izlaganje 3
Vježbe i zadaci 3
|
6 |
2 |
|
4. |
Orjentisani grafovi i odgovarajući modeli |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
5. |
Osnovne osobine drveta, udaljenost u drvetima,
prebrojavanje drveta |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
6. |
Matching i pokrivaci, matching na bipartitnim
grafovima |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
7. |
Matching na grafovima (Tutte teorem) |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
8. |
Povezanost (2 i 3 povezanost) |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
9. |
Mengerovi teoremi i povezanost |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
10. |
Bojenje grafova, List bojenje grafova,
Kromatski polinomi |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
11. |
Perfektni grafovi, Trouglasti grafovi |
Usmeno izlaganje 2
Vježbe i zadaci 3 |
6 |
2 |
|
12. |
Planarnost, Planarnost i teorem Kuratowskog, |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
13. |
Hamiltonove konture |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
14. |
Ekstremalni problemi na grafovima |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
|
15. |
Osnovni algoritmi pretraživanja na grafovima |
Usmeno izlaganje 3
Vježbe i zadaci 3 |
6 |
2 |
F. PROVJERA ZNANJA I OCJENJIVANJE
|
Provjera znanja - kriteriji |
Ocjenjivanje |
|
Kriterij |
Maksimalan broj bodova |
Bodovi za prolaz |
Osvojen broj bodova |
Ocjena (BiH) |
ECTS ocjena |
|
Domaće zadaće (2 zadaće) |
20 |
10 |
< 55,00 |
5 |
F |
|
Testovi tokom kursa (2 testa) |
40 |
23 |
55,00 – 64,99 |
6 |
E |
|
Seminarski rad |
10 |
5 |
65,00 – 74,99 |
7 |
D |
|
Pismeni završni ispit |
30 |
17 |
75,00 – 84,99 |
8 |
C |
|
|
|
|
85,00 – 94,99 |
9 |
B |
|
|
|
|
95,00 – 100,00 |
10 |
A |
|
U k u p n o |
100 |
55 |
|
G. LITERATURA
Osnovna literatura:
1.
Ballobas, Graph Theory
2.
Thomas Corman, Charles Leiserson, Ronald Rivest; Introduction to
Algorithms
3.
Jonathan Gross, Jay Yellen Graph theory and its applications
4.
Gary Chartrand, Introductory graph theory