Izpit pri predmetu OSNOVE TEORIJE GRAFOV
15.12.2016
as re²evanja je 120 minut. Vse odgovore je potrebno utemeljiti!
1. [35] Na sliki 1 je prikazan graf G.
(a) Dolo£ite kromati£no ²tevilo grafaG. (b) Dolo£ite kromati£ni indeks grafaG.
(c) Ali je grafG Hamiltonov?
Slika 1: Graf G iz naloge 1
2. [15] Na sliki 2 sta prikazana grafa Gin H. Ali sta izomorfna?
Slika 2: Grafa G inH iz naloge 2
3. [30] Podan je graf Gn z mnoºico vozli²£ V(Gn) in mnoºico povezav E(Gn), kjer je V(Gn) = {1,2, ..., n} inE(Gn) ={uv;u, v ∈V(Gn)∧ |u−v| ≤2}.
(a) Dolo£ite vsa naravna ²tevila n, za katera so gra Gn gra intervalov.
(b) Dolo£ite vsa naravna ²tevila n, za katera so gra Gn vpeti podgra nekega ravninskega grafa, ki ima dve vozli²£i stopnje 3, vsa ostala vozli²£a pa vi²jih stopenj.
4. [20] Naj bo G poljuben tetivni graf z vsaj eno povezavo. Dokaºite, da G premore tak²no povezavoe, da je graf, ki ga dobimo tako, da iz grafaGodstranimoe, tetivni.
