Bojenje grafova. Bojenje grafa [math]\displaystyle{ G = (V,E) }[/math] je funkcija [math]\displaystyle{ f:V \rightarrow S }[/math], pri čemu je [math]\displaystyle{ S }[/math] konačan skup boja sa svojstvom:[1] [math]\displaystyle{ (u,v) \in E \implies f(u) \neq f(v). }[/math]
Bojenje je [math]\displaystyle{ k }[/math]-bojenje ako je [math]\displaystyle{ |Im(f)| = k }[/math]. [1]
Graf [math]\displaystyle{ G = (V,E) }[/math] je [math]\displaystyle{ k }[/math]-obojiv ako postoji [math]\displaystyle{ 1 }[/math]-bojenje grafa za neki [math]\displaystyle{ l \leq k }[/math]. Ako je [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-obojiv, a nije [math]\displaystyle{ k - 1 }[/math]-obojiv, kažemo da je [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-kromatski. Za [math]\displaystyle{ k }[/math] kažemo da je kromatski broj te ga označavamo se [math]\displaystyle{ \chi (G) }[/math].[1]
Ciklički graf može se obojiti samo na dva načina, dok bojenje Petersenovog grafa nije jedinstveno. [1]
Vidi
Izvori
- ↑ 1,0 1,1 1,2 1,3 Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)
Vanjske poveznice
- Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011.