znajdz wielomian chromatyczny:
a)cyklu o n wierzcholkach
b) "kola o n szprychach"
c) K_{3,3}
znalezc wielomian chromatyczny
-
- 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
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ąć
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ąć