Barvení grafu

Kategorie: Nezařazeno (celkem: 23181 referátů a seminárek)

Informace o referátu:

Příbuzná témata

Vytisknout referátPřidat referát do záložek

Barvení grafu

Obarvený graf - 3 barvy
Obarvený graf - 3 barvy
Vrcholy Petersenova grafu jsou obarvitelné třemi barvami
Vrcholy Petersenova grafu jsou obarvitelné třemi barvami

Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu - vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. barvení sousedících ploch) lze na tento jednoduše převést.

Definice

Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení b: V arr{1, 2, ldots, k } nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu {x, y}in E platí b(x) eq b(y). Barevnost grafu (také chromatické číslo G je minimální počet barev potřebný pro obarvení G. Značí se ?(G).

Některé vlastnosti ?(G)

  1. ?(G) = 1 právě tehdy, skládá-li se G z izolovaných vrcholů
  2. chi (G)ge 3 právě tehdy, obsahuje-li G kružnici liché délky (ekvivaletně, není-li G bipartitní)
  3. chi (G)le 4 pro libovolný rovinný graf (viz slavný problém čtyř barev)

Vytisknout referátPřidat referát do záložek

Nový příspěvek


Ochrana proti spamu. Kolik je 2x4?


Na-mobil.cz

Spřátelené weby

Přidat stránku k oblíbeným

Nejnovější v diskusi

Diskusní fórum »

TIP: Chcete zkrátit dlouho chvíli sobě nebo blízkému?
Klikněte na Puzzle-prodej.cz a vyberte si z 5000 motivů skladem!
TIP: Hračky a hry za dobré ceny?
Klikněte na Hračky obchod.cz a vyberte si z tisícovky hraček skladem!