Wielomian chromatyczny

[dusiek]

Obliczyć wielomian chromatyczny dla grafu:

Mam wskazówkę żeby obliczyć najpierw wielomian chromatyczny dla jakiegoś podgrafu, lecz niestety nie mam pojęcia jakiego. Prosiłbym o dalsze wskazówki

[adambak]

oblicz najpierw wielomian chromatyczny tego małego kwadratu ze środkiem i przekątnymi.. da radę na palcach rozpatrując kilka przypadków i dalej będzie z górki..

[dusiek]

Zupełnie intuicyjnie \(\displaystyle{ f_{G}\left(t\right) = t\left( t - 1\right)\left( t - 2\right)^{2}\left( t - 3\right) = n^{5} - 8n^4 + 23n^3 - 28n^2 + 12n}\). Nie wiem w ogóle czy to co napisałem ma sens. Tok rozumowania jest taki: środkowy wierzchołek możemy pokolorować na n kolorów, jeden z wierzchołków kwadratu na n - 1 bo jest połączony ze środkiem, następnie dwa na przekątnej na n - 2 bo są połączone ze środkiem i z tym już pokolorowanym i ostatni na n - 3 bo jest połączony z trzema, które już mają różne kolory.

[TMac]

No nie do końca. Zacząłeś dobrze wybierając środkowy wierzchołek, ale jeśli pomalujesz dwa po obu stronach środkowego na ten sam kolor, to ostatni możesz pomalować na n-2, a jeśli na 2 różne, to na n-3 jak napisałeś. To, że wierzchołek w środku jest połączony ze wszystkimi innymi powinno Ci dać do myślenia - co możesz zrobić z \(\displaystyle{ G}\), a właściwie ze środkowym wierzchołkiem by uprościć liczenie? Możesz go jakoś oddzielić? (Chciałem tu jakoś nakierować na pewien sposób, ale chyba średnio mi to wyszło )
Odpowiedź:

Ukryta treść:    

Zauważ, że możesz policzyć tak: \(\displaystyle{ f_{G}\left(t\right) = t \cdot f_{G'}\left(t-1\right)}\), gdzie \(\displaystyle{ G'}\) to najzwyklejszy kwadrat (dlaczego można tak zrobić?).

Polecam też twierdzenie:
W skrócie mówi, że jeżeli masz graf i wybierzesz sobie jakąś krawędź to liczba pokolorowań będzie równa liczbie pokolorowań grafu bez tej krawędzi minus liczbie pokolorowań grafu z tą krawędzią ściągniętą (wynika to z tego, że jak masz graf bez krawędzi między danymi wierzchołkami to wierzchołki mogą mieć ten sam kolor - a wtedy jest tak jakbyś je ściągnął - lub inne kolory - a wtedy możesz dorzucić krawędź między nimi, bo nic nie popsuje).
Oczywiście można to twierdzenie stosować "rekurencyjnie".

[dusiek]

Znam te twierdzenie z teorii, nigdy jeszcze go nie stosowałem w praktyce Faktycznie ten kwadrat z przekątna spełnia \(\displaystyle{ f_{G}\left(t\right) = t * f_{G^{'}}\left( t - 1\right)}\), bo jak środkowemu wierzchołkowi nadamy jakiś kolor to do pozostałych czterech musimy użyć jednego koloru mniej, bo jest połączony ze wszystkimi. A dla samego kwadratu mamy \(\displaystyle{ f_{G^{'}}\left( t\right) = f_{G-e}\left( t\right) - f_{G/e}\left( t\right)}\). \(\displaystyle{ G-e}\) jest drzewem, więc wielomian jest równy \(\displaystyle{ t\left( t - 1\right)^3}\), natomiast \(\displaystyle{ G/e}\) jest trójkątem, więc wielomian to \(\displaystyle{ t\left( t-1\right)\left( t - 2\right)}\). Ostatecznie \(\displaystyle{ f_{G^{'}} = t\left( t - 1\right)^3 - t\left( t-1\right)\left( t - 2\right)}\). Mamy policzone \(\displaystyle{ f_{G}(t)}\), ale teraz za bardzo nie mam pomysłu jak to odnieść do całego grafu. Bo chyba nie będzie to suma ani iloczyn wielomianów \(\displaystyle{ f_{G}\left( t\right)}\)? Bo mają niektóre krawędzie wspólne.

[adambak]

Zupełnie intuicyjnie \(\displaystyle{ f_{G}\left(t\right) = t\left( t - 1\right)\left( t - 2\right)^{2}\left( t - 3\right) = n^{5} - 8n^4 + 23n^3 - 28n^2 + 12n}\). Nie wiem w ogóle czy to co napisałem ma sens.

średnio, bo w końcu wychodzi że jest niezależny od \(\displaystyle{ t}\)


ja tam zacząłem kolorowanie od lewego dolnego wierzchołka i nie było problemów, ostatecznie wyszło mi:
\(\displaystyle{ f_G(t)=t(t-1)((t-2)^2+(t-2)(t-3)^2)}\), ponieważ wybieram dla lewego dolnego, potem dla tego nad nim, następnie dwa przypadki: kiedy prawy górny jest tego samego koloru co lewy dolny oraz kiedy jest innego, a więc rozumowanie takie samo

co oczywiście jest tym samym po uproszczeniu jak się złoży Twój wynik, bo sprawdziłem

no to teraz sklejasz te kwadraty.. zauważ, że sklejenie dwóch takich kwadratów, powiedzmy jednym wierzchołkiem jak to jest w prawej części grafu, powoduje utożsamienie prawego górnego wierzchołka pierwszego kwadratu z lewym dolnym wierzchołkiem drugiego kwadratu.. czyli ten wierzchołek musi mieć ten sam kolor, no to jak wybierzemy go w pierwszym kwadracie to w drugim już nie trzeba, wielomian chromatyczny takiego sklejenia to \(\displaystyle{ \frac{f_G^2(t)}{t}}\)

spróbuj dokończyć sam, ja bym zaczął od pokolorowania środkowego kwadratu-- 7 wrz 2012, o 14:47 --środkowego - tego z którym krawędziowo sąsiadują cztery kwadraty

[dusiek]

dusiek napisał(a):
Zupełnie intuicyjnie \(\displaystyle{ f_{G}\left(t\right) = t\left( t - 1\right)\left( t - 2\right)^{2}\left( t - 3\right) = n^{5} - 8n^4 + 23n^3 - 28n^2 + 12n.}\) Nie wiem w ogóle czy to co napisałem ma sens.

średnio, bo w końcu wychodzi że jest niezależny od t

Oczywiście wkradła się tu zmienna \(\displaystyle{ n}\) zamiast \(\displaystyle{ t}\). Ale i tak rozumowanie było błędne.

Wracając do wielomianu:
Zaczynając od tego kwadratu najbardziej w środku możemy go pokolorować na \(\displaystyle{ f_{G}\left(t\right)}\) sposobów, a każdy z kwadratów z nim sąsiadujących na \(\displaystyle{ \frac{f_{G}\left( t\right)}{t\left( t-1\right)}}\) (tutaj mam wątpliwości czy nie przez \(\displaystyle{ t^{2}}\)) a kwadrat najbardziej na prawo na \(\displaystyle{ \frac{f_{G}\left(t\right)}{t}}\) . Czyli ostatecznie wielomian wygląda tak: \(\displaystyle{ f_{H}\left( t\right) = f_{G}\left(t\right)*\left( \frac{f_{G}\left( t\right)}{t\left( t-1\right)} \right)^{4}*\frac{f_{G}\left(t\right)}{t}}\)

[adambak]

no pewnie, wszystko się zgadza

wątpliwości niepotrzebne, przez \(\displaystyle{ t^2}\) by się dzieliło, gdyby te dwa wierzchołki mogły mieć ten sam kolor, to dzielenie widać, jeśli się zaczyna kolorowanie kwadratu od lewego dolnego wierzchołka tak jak ja to zrobiłem.. było najpierw \(\displaystyle{ t(t-1)}\), więc skoro te dwa są wybrane to mamy \(\displaystyle{ \frac{f_{G}\left( t\right)}{t\left( t-1\right)}}\)-- 7 wrz 2012, o 15:50 --ale można też tłumaczyć to sobie na parę innych sposobów