Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.1.PODSTAWOWEPOJĘCIAIDEFINICJE
5
grafdwudzielny,wktórymjedenzezbiorówV1,V2zawieratylkojeden
wierzchołek(patrzrys.1.4).Lasemnazywamygrafniezawierający
cykli,zaśdrzewemgrafspójnyniezawierającycykli.
RYSUNEK1.4.Przykłady:(a)cykluC4,(b)kołaW5,(c)gwiazdyS5;gwiazdajest
zarazemprzykłademdrzewa
DEFINICJA1.14.Kaktusemnazywamygraf,którymożezostaćzdekompo-
nowanynapojedynczecyklepołączoneścieżkamiwtakisposób,że
każdedwacyklemająconajwyżejjedenwspólnywierzchołek.Na-
szyjnikiemnazywamygraf,któryskładasięzpewnejliczbyk>2
ścieżekP
...,P
i1,
ikodługościachodpowiednioi1,
...,ik.Wszystkie
ścieżkisąparamiwierzchołkoworozłącznezwyjątkiemwierzchoł-
kówuiυ,stanowiącychpoczątekikonieckażdejścieżki.Drzewem
wielokątowymnazywamygrafnależącydoklasygrafówzdefiniowa-
nejrekurencyjniewsposóbnastępujący:dowolnycyklstanowidrzewo
wielokątowe;nowedrzewowielokątoweG/powstajeprzezdodaniedo
istniejącegodrzewawielokątowegoGcykluwtakisposób,bymiał
ondokładniejednąkrawędźwspólnązgrafemG(patrzrys.1.5).
RYSUNEK1.5.Przykłady:(a)kaktusa,(b)naszyjnika,(c)drzewawielokątowego
1.1.2.
Analizametodprzybliżonych
Ponieważznajdowaniedokładnegopokolorowaniagrafudlawszystkich
nietrywialnychmodelikolorowaniajestproblememtrudnymobliczenio-
wo(wszczególnościniesąznanedokładnealgorytmydziałającewczasie
wielomianowym),musząbyćrozwijanealgorytmyprzybliżone.Przydużej
liczbieistniejącychalgorytmówniezbędnestająsięnarzędziaumożliwia-
jącebadanieiocenęefektywnościtakichheurystyk.
