Razlika između inačica stranice »Bojenje grafa«
(Bot: Automatski unos stranica) |
m (bnz) |
||
| Redak 1: | Redak 1: | ||
'''Bojenje grafova'''. Bojenje grafa <math>G = (V,E)</math> je funkcija <math>f:V \rightarrow S</math>, pri čemu je <math> S </math> [[konačan skup]] boja sa svojstvom:<ref name=Bujanović/> | |||
<math>(u,v) \in E \implies f(u) \neq f(v).</math> | <math>(u,v) \in E \implies f(u) \neq f(v).</math> | ||
Trenutačna izmjena od 18:10, 29. travnja 2022.
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.