Matematické Fórum

nasivin · 03. 11. 2008 20:15

Na šachovnici NxN jsou položeny kameny. Obarvěte kameny minimálním počtem barev tak, aby žádný řádek a žádný sloupec neobsahoval 2 kameny stejných barev. Šachovnice může obsahovat i místa, kde nejsou položené kameny.

příklad: ( K = kámen ; 0 = pole bez kamene )
K 0 K 0
K 0 K 0
K K K 0
0 0 K K

jedno z možných řešení: ( každé číslo znamená jinou barvu )
1 0 2 0
3 0 1 0
2 1 3 0
0 0 4 1

Přišel jen na to, že minimální počet barev = maximální počet kamenů na každém řádku a zároveň na každém sloupci.

Přemýšlel jsem, že bych nějak použil teorii grafů, ale vůbec nevím jak.

Kondr · 04. 11. 2008 10:55

No pokud by šlo o to, převést to na grafovou úlohu, pak kameny budou vrcholy a hrana bude mezi každými dvěma vrcholy, které odpovídají kamenům ve stejném řádku/sloupci. Algoritmy na obarvení grafů jsou ale dost netriviální.

Nám stačí hladový postup. Pro každý řádek i sloupec si pamatujeme množinu barev, které jsme v něm použili. Pak procházíme šachovnici a vždy, když narazíme na kámen tak ho obarvíme barvou, která v těchto množinách pro příslušný řádek a sloupec není a tuto barvu do množin přidáme. Pokud si množiny pamatjeme jako binární stromy, máme složitost O(N^2logN). Možná to jde i v O(N^2), ale momentálně nevím jak.

nasivin · 15. 11. 2008 16:31

Myslím si že by to obecně nešlo. Třeba situace:

K 0 K K
K 0 K K
0 0 0 0
0 0 0 0

řešení:

1 0 2 3
2 0 1 ?
0 0 0 0
0 0 0 0

Matematické Fórum

#1 03. 11. 2008 20:15

Minimální barevnost grafu

#2 04. 11. 2008 10:55

Re: Minimální barevnost grafu

#3 15. 11. 2008 16:31

Re: Minimální barevnost grafu

Zápatí