Prijeđi na sadržaj

Bojenje grafa

Izvor: Wikipedija
(Preusmjereno s Bojenje grafova)

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]

Izvori

[uredi | uredi kôd]
  1. a b c d Prirodoslovno-matematički fakultet u ZagrebuArhivirana inačica izvorne stranice od 25. svibnja 2020. (Wayback Machine) Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)

Vanjske poveznice

[uredi | uredi kôd]