Kromatično število: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
N |
m m+/dp |
||
| Vrstica 1: | Vrstica 1: | ||
[[slika:Petersen graph 3-coloring.svg|thumb|right|200px|Zgled [[barvanje grafa|barvanja]] [[Petersenov graf|Petersenovega grafa]] po [[točka (teorija grafov)|točkah]]. Za njegovo barvanje so potrebne tri različne barve, njegovo kromatično število pa je enako 3.]] |
[[slika:Petersen graph 3-coloring.svg|thumb|right|200px|Zgled [[barvanje grafa|barvanja]] [[Petersenov graf|Petersenovega grafa]] po [[točka (teorija grafov)|točkah]]. Za njegovo barvanje so potrebne tri različne barve, njegovo kromatično število pa je enako 3.]] |
||
'''Kromatično število''' (ali '''barvnost'''<ref name="wilson_1997" />) [[graf (matematika)|grafa]] ''G'' je v [[teorija grafov|teoriji grafov]] najmanjše število ''k'', za katerega je ''G'' [[k-pobarvljivi graf|''k''-pobarvljiv]], oziroma je najmanjše število barv, s katerimi je mogoče [[barvanje grafa|pobarvati]] graf ''G'' po [[točka (teorija grafov)|točkah]] tako, da imajo pari točk poljubne [[povezava (teorija grafov)|povezave]] različne barve. Običajno se označuje kot <math> \chi (G) \!\, </math>. |
'''Kromatično število''' (ali '''barvnost'''<ref name="wilson_1997" />) [[graf (matematika)|grafa]] ''G'' je v [[teorija grafov|teoriji grafov]] najmanjše število ''k'', za katerega je ''G'' [[k-pobarvljivi graf|''k''-pobarvljiv]], oziroma je najmanjše število barv, s katerimi je mogoče [[barvanje grafa|pobarvati]] graf ''G'' po [[točka (teorija grafov)|točkah]] tako, da imajo pari točk poljubne [[povezava (teorija grafov)|povezave]] različne barve. Običajno se označuje kot <math> \chi (G) \!\, </math>. |
||
<gallery> |
|||
11-simplex graph.svg|Kromatično število vsakega [[polni graf|polnega grafa]] <math> K_{n} \!\, </math> pri <math> n\ge 2 \!\, </math> je <math>n \!\, </math>. Na sliki polni graf <math> K_{12} \!\, </math> |
|||
Hypercubestar.svg|Kromatično število [[hiperkockin graf|hiperkockinega grafa]] je 2 |
|||
DesarguesGraph.svg|Kromatično število [[Desarguesov graf|Desarguesovega grafa]] je 2 |
|||
Ljubljana graph hamiltonian.svg|Kromatično število [[Ljubljanski graf|Ljubljanskega grafa]] je 2 |
|||
Frucht graph.neato.svg|Kromatično število [[Fruchtov graf|Fruchtovega grafa]] je 3 |
|||
Biggs-Smith graph.svg|Kromatično število [[Biggs-Smithov graf|Biggs-Smithovega grafa]] je 3 |
|||
Higman Sims Graph.svg|Kromatično število [[Higman-Simsov graf|Higman-Simsovega grafa]] je 6 |
|||
</gallery> |
|||
== Sklici == |
== Sklici == |
||
Redakcija: 23:00, 1. julij 2019
Kromatično število (ali barvnost[1]) grafa G je v teoriji grafov najmanjše število k, za katerega je G k-pobarvljiv, oziroma je najmanjše število barv, s katerimi je mogoče pobarvati graf G po točkah tako, da imajo pari točk poljubne povezave različne barve. Običajno se označuje kot .
-
-
Kromatično število hiperkockinega grafa je 2 -
Kromatično število Desarguesovega grafa je 2 -
Kromatično število Ljubljanskega grafa je 2 -
Kromatično število Fruchtovega grafa je 3 -
Kromatično število Biggs-Smithovega grafa je 3 -
Kromatično število Higman-Simsovega grafa je 6
Sklici
- ↑ Wilson; Watkins (1997), str. 278.
Viri
- Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1
{{citation}}: Neveljaven|ref=harv(pomoč)
