Bojenje grafa

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

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. 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