Izpit pri predmetu OSNOVE TEORIJE GRAFOV
21.2.2018
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 in kromati£ni indeks grafaG. (b) Ali je grafG tetiven?
(c) Ali je grafG ravninski?
Slika 1: Graf G iz naloge 1
2. [15] Ali je graf H, prikazan na sliki2, izomorfen grafu Giz naloge 1?
3. [15] Naj bo G tak²en graf z lihim ²tevilom vozli²£, da sta grafa G in G povezana.
Dokaºite naslednje: £e je graf G Eulerjev, je tudi graf G Eulerjev.
4. [35] Za vsako naravno ²tevilo n denirajmo graf Gn z V(Gn) = {1,2, ..., n} in E(Gn) = {ab; ab je sodo ²tevilo}.
(a) Za katera naravna ²tevila n so gra Gn regularni? Utemeljite.
(b) Dolo£ite vsa naravna ²tevila n, za katera so gra Gn gra intervalov. Za vse, ki so gra intervalov, podajte intervalne predstavitve.
(c) Za vsako naravno ²tevilon ≥4nari²ite vpeti podgraf grafaGn, ki je dvodelen, a ni drevo.
Slika 2: Graf H iz naloge 2
