Kritičan graf: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Stvorena nova stranica sa sadržajem: »mini|desno|250px|Primjeri kritičkih grafova '''Kritičan graf''' je onaj graf (teorija grafova) za koji vri...«. |
(Nema razlike inačica)
|
Inačica od 3. listopada 2020. u 19:42
Kritičan graf je onaj graf za koji vrijedi [1]:1
Kritični grafovi su povezani, inače bi svaka komponenta povezanosti imala isti kromatski broj kao čitav graf. Vrijedi li da je kritičan graf -kromatski, onda ga nazivamo -kritičnim. Svaki graf kromatskog broja ima kritičan podgraf kromatskog broja -kromatski.[1]:1 Za minimalni stupanj -kritičnog grafa vrijedi da je [1]:2
Izvori
- ↑ a b c Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)