Minimálně barevná kostra grafu

Vstupní data:

Doporučení pro generování G:

Použijte generátor grafu Generator 2 s typem grafu AD.

Definice:

V grafu G je každá jeho hrana ohodnocena přirozeným číslem z množiny B={ 1, .., b} představující její barvu. Kostra grafu G je strom (t.j. souvislý acyklický podgraf) obsahující všechny uzly grafu G.

Úkol:

Nalezněte minimálně barevnou kostru K grafu G, t.j. kostru s minimálním počtem barev hran.

Výstup algoritmu:

Výpis hran minimalně barevné kostry K ve formě matice incidence.

Sekvenční algoritmus:

Řešení vždy existuje. Použijeme sekvenční algoritmus typu BB-DFS s hloubkou omezenou na n-1. Přípustný mezistav je podmnožina hran, která je lesem (t.j. množinou stromů) v G. Cena, kterou minimalizujeme, je počet různých barev hran v K. Kostru K lze budovat přidáváním hran počínaje libovolnou hranou tak, aby nevznikla kružnice. Neobsahuje-li K právě n-1 hran, přidá se do K nová hrana. Je-li |K|=n-1 , provádí se návrat. Algoritmus skončí, až prohledá celý stavový prostor do hloubky n-1.

Triviální řešení představuje kostra s hranami obarvenými pouze jedinou barvou. Tento případ může nastat v případě kdy každý uzel grafu inciduje s alespoň dvěmi hranami obarvenými stejnou barvou.

Paralelní algoritmus:

Paralelní algoritmus je typu G-PBB-DFS-D.