Bojenje grafa: razlika između inačica

Posljednja izmjena od 29. travanj 2022. u 18:10

Bojenje grafova. Bojenje grafa $G=(V,E)$ je funkcija $f:V\rightarrow S$ , pri čemu je $S$ konačan skup boja sa svojstvom:^[1] $(u,v)\in E\implies f(u)\neq f(v).$

Bojenje je $k$ -bojenje ako je $|Im(f)|=k$ . ^[1]

Graf $G=(V,E)$ je $k$ -obojiv ako postoji $1$ -bojenje grafa za neki $l\leq k$ . Ako je $G$ $k$ -obojiv, a nije $k-1$ -obojiv, kažemo da je $G$ $k$ -kromatski. Za $k$ kažemo da je kromatski broj te ga označavamo se $\chi (G)$ .^[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.

[Bujanović-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.)

[1]

Inačica od 9. prosinac 2021. u 17:38 vidi izvor WikiSysop (razgovor \| doprinosi) AA_Korisnik, Botovi, Birokrati, Administratori sučelja, Otajnici, Administratori 528.032 edits Bot: Automatski unos stranica		Posljednja izmjena od 29. travanj 2022. u 18:10 vidi izvor WikiSysop (razgovor \| doprinosi) AA_Korisnik, Botovi, Birokrati, Administratori sučelja, Otajnici, Administratori 528.032 edits m bnz
Redak 1:		Redak 1:
	~~<!--'''Bojenje grafa'''-->~~'''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ć/>		'''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>