Wielomian chromatyczny
-
- Użytkownik
- Posty: 24
- Rejestracja: 19 paź 2011, o 19:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wielomian chromatyczny
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
Mam wskazówkę żeby obliczyć najpierw wielomian chromatyczny dla jakiegoś podgrafu, lecz niestety nie mam pojęcia jakiego. Prosiłbym o dalsze wskazówki
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
Wielomian chromatyczny
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..
-
- Użytkownik
- Posty: 24
- Rejestracja: 19 paź 2011, o 19:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wielomian chromatyczny
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.
Wielomian chromatyczny
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ź:
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".
Odpowiedź:
Ukryta treść:
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".
-
- Użytkownik
- Posty: 24
- Rejestracja: 19 paź 2011, o 19:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wielomian chromatyczny
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.
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
Wielomian chromatyczny
średnio, bo w końcu wychodzi że jest niezależny od \(\displaystyle{ t}\)dusiek pisze: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.
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
-
- Użytkownik
- Posty: 24
- Rejestracja: 19 paź 2011, o 19:39
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 2 razy
Wielomian chromatyczny
Oczywiście wkradła się tu zmienna \(\displaystyle{ n}\) zamiast \(\displaystyle{ t}\). Ale i tak rozumowanie było błędne.średnio, bo w końcu wychodzi że jest niezależny od tdusiek 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.
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}}\)
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
Wielomian chromatyczny
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
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