36 (573)

znalezienie optymalnego rozwiązania w czasie wy ki adrii czym nie zawsze jest proste i szybkie. Problem rozwiazywaJności pojawia się juz na początku, czyli podczas wyboru pierwszego węzła grafu, Inćn będzie służył jako początek do dalszego rozwijania drogi jakiegoś algorytmu. Z analizy algorytmów wiadomo (sic!), ze jeśli umiejętnie dobierzemy początkowy wierzchołek analizy danego grafu lo uzyskane rozwiązanie będzie optymalne, czyli będzie zawierało najmniej kulorów. Postępowanie zacbaunc jest typem postępu wam ł, w którym luc zawsze znajdujemy optimum. Wybieramy z reguły „pierwszy lepszy,, wierzchołek i decydujemy się na rozwiązanie taki jakie po prostu „wyjdzie" I tu wiairue dochodzimy do sedna problemu kolorowania grafów. Problem kolorowania grafu polega na takim pokolorowaniu jego wszystkich wierzchołków, aby użyć w tym celu najmniejszej liczby kolorów Czasami celowe więc jest rozpoczęcie kolorowania od wierzchołka innego niż⁵ „pierwszy”, ale to nie jes: wtedy postępowanie zachłanne. W celu lepszego poznania problemu kolorowania grafów celowe jer wprowadzenie odpowiednich pojęć:

Graf nazywamy K-KOLORO WALNYM, jeśli istniej pewne przyporządkowanie wierzchołków graf. liczbom naturalnym ( kolorom ), tak żc żadne dwa sąsiednie wierzchołki me są pokolorowane ryr. samym kolorem.

Wierzchołki są SĄSIEDNIE, jeśli istnieje między nimi chociaż jedna krawędź je łącząca.

LICZBĄ CHROMATYCZNĄ grafu nazywamy najmniejszą liczbę całkowitą grafu, taką że graf jest k • koioro walny,

KLIKA ROZMIARU „N” • to zbiór wierzchołków grafu, w którym każdy z każdym jest połączony krawędzią i w .zbiorze tym występuję N kolorów.

Jeśli wprowadzone zostały pojęcia to należy zaznaczyć, ze graf jest pokolorowany liczbą ctiromalyczną jeśli udaje się znaleźć w tym grane kilkę o rozmiarze liczby chromatycznej. Czyli, z profesorskiego na nasze, jeśli w grafie uda się znaleźć klikę o rozmiarze takim jaka jest najmniejsza liczba kolorów.

Warto przeanalizować przykład rysunkowy*: