Grafy, wielomian chromatyczny.
-
- Użytkownik
- Posty: 9
- Rejestracja: 4 mar 2018, o 22:58
- Płeć: Kobieta
- Lokalizacja: Gdynia
- Podziękował: 1 raz
Grafy, wielomian chromatyczny.
Cześć, czy znalazłby się ktoś, kto mógłby mi napisać w jaki sposób zabrać się za wyznaczenie wielomianu chromatycznego?
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Grafy, wielomian chromatyczny.
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
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