Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
1.KLASYCZNEKOLOROWANIEGRAFÓW
Jk[15].Dlakażdegotakiegografumożnawskazaćsekwencjęwymagającą
użyciadokładniekkolorów.StądfunkcjadobrociRS(n)=O(n).Grafem
SHCdlatejmetodyjestścieżkaP4,pokazananarys.1.6(kolejnośćwierz-
chołkówpodananarysunkuprowadzidonieoptymalnegopokolorowania
grafu).Należyzauważyć,żedlatejmetodynieistniejegrafHC,czego
dowódmożestanowićprostećwiczeniedlaCzytelnika.
RYSUNEK1.6.ŚcieżkaP4—najmniejszygrafdośćtrudnydlametodyRS
MetodaLF
Metoda,którejnazwapochodziodangielskichsłówLargest-First(LF),
zostałazaproponowanaprzezWelshaiPowella[33].Jestonajednąznaj-
starszychinajprostszychmetodsekwencyjnych.MetodaLFjestrezultatem
spostrzeżenia,żewierzchołkioniskimstopniuzwyklepozostawiająpewną
swobodęwdoborzekoloru;wzwiązkuztymnależynajpierwkolorować
pozostałe,tj.wierzchołkiowysokimstopniu.Mimoprostotycechujeją
niezłaskuteczność.
algorytmKolorujLF(G);
begin
K:=wierzchołkiGuporządkowanewgnierosnącychstopniwgrafieG;
KolorujZachłannie(G,K);
end;
MetodatamożezostaćzaimplementowanawczasieO(m+n).Do
analizydobrocimetodyLFmożnawykorzystaćrodzinęgrafówdwudziel-
nych,zaproponowanąprzezJohnsona.GrafyJkwnajgorszymprzypadku
wymagająk=n/2kolorów.StądfunkcjadobrociLF(n)=O(n).Grafem
SHCdlametodyLFjestścieżkaP6,pokazananarys.1.7(a),natomiast
grafemHC(LF)jestgrafnazywanykopertą,pokazanynarys.1.7(b).
RYSUNEK1.7.(a)ŚcieżkaP6—najmniejszygrafdośćtrudnydlametodyLF,
(b)kopertaKp—najmniejszygraftrudnydlametodyLF
