Grafy, wielomian chromatyczny.

[MPIS_pad]

Cześć, czy znalazłby się ktoś, kto mógłby mi napisać w jaki sposób zabrać się za wyznaczenie wielomianu chromatycznego?

[leg14]

Rozważmy sobie graf \(\displaystyle{ G}\) i jego dwa wierzchołki - \(\displaystyle{ v_1,v_2}\) nie połączone krawędzią.
Kolorowania G dzielą się na dwie klasy:
1) kolorowania, w których \(\displaystyle{ kolor(v_1) = kolor(v_2)}\)
2) kolorowania, w których \(\displaystyle{ kolor(v_1) != kolor(v_2)}\)

Niech \(\displaystyle{ G/v}\) oznacza graf powstały z grafu \(\displaystyle{ G}\) przez utożsamienie wierzchołków \(\displaystyle{ v_1,v_2}\)
Niech \(\displaystyle{ Gv}\) oznacza graf powstały z grafu \(\displaystyle{ G}\) przez dodanie krawędzi \(\displaystyle{ [v_1,v_2 ]}\)

Obserwacja: Kolorowania klasy 1) są w bijekcji z kolorowaniami \(\displaystyle{ G/v}\). kolorowania klasy 2) są w bijekcji z kolorowaniami \(\displaystyle{ Gv}\)

Wniosek:
\(\displaystyle{ w_{G}(t) = w_{Gv}(t) + w_{G/v}(t)}\) gdzie "w" oznacza wielomian chromatyczny.


obserwacja 2: Iterując operację dodawania krawędzi do grafu G otrzymamy (po skończonej ilości kroków) klikę.

obserwacja 3: Iterując operację "zlepiania" krawędzi grafu spójnego otrzymamy (po skończonej liczbie kroków) graf z jednym wierzchołkiem

Twoje zadanie:
1) zauważenie, że Wniosek daje Ci algorytm obliczania wielomianu chormatycznego dowolnego grafu, o ile znasz wielomian chromatyczny kliki i punktu
2) wyznaczenie wielomianu chromatycznego kliki