Bojenje grafa: razlika između inačica
Prijeđi na navigaciju
Prijeđi na pretraživanje
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> | ||
Posljednja izmjena od 29. travanj 2022. u 18:10
Bojenje grafova. Bojenje grafa je funkcija , pri čemu je konačan skup boja sa svojstvom:[1]
Bojenje je -bojenje ako je . [1]
Graf je -obojiv ako postoji -bojenje grafa za neki . Ako je -obojiv, a nije -obojiv, kažemo da je -kromatski. Za kažemo da je kromatski broj te ga označavamo se .[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.