znalezc wielomian chromatyczny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kriegor
Użytkownik
Użytkownik
Posty: 330
Rejestracja: 21 sty 2012, o 20:51
Płeć: Mężczyzna
Lokalizacja: ut
Podziękował: 182 razy
Pomógł: 1 raz

znalezc wielomian chromatyczny

Post autor: kriegor »

znajdz wielomian chromatyczny:
a)cyklu o n wierzcholkach
b) "kola o n szprychach"
c) K_{3,3}
Rodis
Użytkownik
Użytkownik
Posty: 23
Rejestracja: 25 lut 2009, o 21:22
Płeć: Mężczyzna
Podziękował: 1 raz
Pomógł: 1 raz

znalezc wielomian chromatyczny

Post autor: Rodis »

a) Jak utnie się jedną krawędź z cyklu, to wyjdzie ścieżka \(\displaystyle{ S_n}\) i wtedy \(\displaystyle{ P_{S_n}(t) = t(t-1)^{n-1}}\). Jeśli graf bez krawędzi \(\displaystyle{ e}\) to \(\displaystyle{ G-\{e\}}\), a graf z sklejonymi wierzchołkami będącymi końcami \(\displaystyle{ e}\), to \(\displaystyle{ G\cdot \{e\}}\) (oznaczenie robocze), to \(\displaystyle{ P_G = P_{G-\{e\}}(t) - P_{G\cdot \{e\}}}\) (liczymy z usuniętą, ale mogły powtórzyć się kolory - wtedy traktujemy końce jako jeden wierzchołek i odejmujemy te możliwości). Z tego mamy, że \(\displaystyle{ P_{C_n}(t) = t(t-1)^{n-1} - P_{C_{n-1}}(t)}\), co po rozwinięciu da mniej więcej coś takiego \(\displaystyle{ P_{C_n}(t) = t(t-1)( \sum_{k=2}^{n-2} (t-1)^k (-1)^{n-k} + (t-2)(-1)^{n+1})}\) (wyraz poza sumą wziął się z tego, że \(\displaystyle{ P_{C_3}(t) = t(t-1)(t-2)}\)
b) wybieramy kolor środka i dalej jak wyżej bez jednego koloru: \(\displaystyle{ P(t) = tP_{C_n}(t-1)}\)
c) chyba najprościej "na palcach" albo licząc z tego wzoru co powyżej (ew. używając analogicznego wariantu z dodawaniem, a nie usuwaniem krawędzi)

Za przygotowanie przed poniedziałkowym kolokwium czas się wziąć
kriegor
Użytkownik
Użytkownik
Posty: 330
Rejestracja: 21 sty 2012, o 20:51
Płeć: Mężczyzna
Lokalizacja: ut
Podziękował: 182 razy
Pomógł: 1 raz

znalezc wielomian chromatyczny

Post autor: kriegor »

Rodis pisze: Za przygotowanie przed poniedziałkowym kolokwium czas się wziąć
co to mialo znaczyc ?
ODPOWIEDZ