Wielomian chromatyczny grafu K_3,3

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Heniek1991
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 14 paź 2010, o 16:58
Płeć: Mężczyzna
Lokalizacja: Lublin / Warszawa
Podziękował: 1 raz
Pomógł: 1 raz

Wielomian chromatyczny grafu K_3,3

Post autor: Heniek1991 » 25 sie 2011, o 11:30

Chcę znaleźć wielomian chromatyczny grafu \(\displaystyle{ K_{3,3}}\). Na wikipedii napisali, że za różne uznajemy takie kolorowania, która różnią się nawet tylko permutacją kolorów.

Wydaje mi się, że będzie tak:
\(\displaystyle{ P_{K_{3,3}}(x) = x^{\underline{2}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{3}} + 2 \cdot 3! \cdot x^{\underline{4}} + {3 \choose 2} \cdot {3 \choose 2} \cdot x^{\underline{4}} + 2 \cdot 3! \cdot {3 \choose 2} \cdot x^{\underline{5}} + 6! \cdot x^{\underline{6}}}\)

Po kolei:
- pierwszy składnik: kolorujemy dwoma kolorami, nie łamiemy symetrii
- drugi: wybieramy stronę grafu na dwa sposoby, wybieramy na 3 sposoby dwa wierzchołki z trzech, kolorujemy je jednym kolorem, trzeci kolorujemy drugim, a drugą stronę nowym kolorem
- trzeci: wybieramy stronę, każdy wierzchołek z tej strony kolorujemy innym kolorem. Więc wybieramy kolory i mnożymy przez liczbę ich permutacji. Drugą stronę kolorujemy nowym kolorem
- czwarty (z obu stron kolorujemy dwoma kolorami) - wybieramy dwa wierzchołki z lewej, i dwa z prawej, kolorujemy je dwoma kolorami kolorami. Dwa pozostałe wierzchołki kolorujemy dwoma nowymi kolorami. Nie łamiemy symetrii
- piąty (z jednej trzy, a z drugiej strony dwa kolory) - wybieramy stronę, kolorujemy trzema kolorami, mnożymy przez liczbę permutacji, z drugiej strony wybieramy dwa wierzchołki, kolorujemy jednym kolorem, a ostatni wierzchołek nowym
- szósty (każdy innym kolorem) - wybieramy sześć kolorów i mnożymy przez liczbę permutacji

Pytanie czy dobrze?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wielomian chromatyczny grafu K_3,3

Post autor: norwimaj » 25 sie 2011, o 12:19

Heniek1991 pisze: - trzeci: wybieramy stronę, każdy wierzchołek z tej strony kolorujemy innym kolorem. Więc wybieramy kolory i mnożymy przez liczbę ich permutacji. Drugą stronę kolorujemy nowym kolorem
Nie mnożymy przez liczbę permutacji. Wybieramy stronę, która będzie pokolorowana trzema kolorami: \(\displaystyle{ 2}\), wybieramy kolory dla kolejnych trzech wierzchołków po tej stronie: \(\displaystyle{ x(x-1)(x-2)}\), wybieramy kolor dla drugiej strony: \(\displaystyle{ x-3}\). Razem \(\displaystyle{ 2\cdot x^{\underline{4}}}\).

Heniek1991 pisze: - piąty (z jednej trzy, a z drugiej strony dwa kolory) - wybieramy stronę, kolorujemy trzema kolorami, mnożymy przez liczbę permutacji, z drugiej strony wybieramy dwa wierzchołki, kolorujemy jednym kolorem, a ostatni wierzchołek nowym
- szósty (każdy innym kolorem) - wybieramy sześć kolorów i mnożymy przez liczbę permutacji
To samo.

Heniek1991
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 14 paź 2010, o 16:58
Płeć: Mężczyzna
Lokalizacja: Lublin / Warszawa
Podziękował: 1 raz
Pomógł: 1 raz

Wielomian chromatyczny grafu K_3,3

Post autor: Heniek1991 » 25 sie 2011, o 12:25

Czyli: \(\displaystyle{ P_{K_{3,3}}(x) = x^{\underline{2}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{3}} + 2 \cdot x^{\underline{4}} + {3 \choose 2} \cdot {3 \choose 2} \cdot x^{\underline{4}} + 2 \cdot {3 \choose 2} \cdot x^{\underline{5}} + x^{\underline{6}}}\)

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wielomian chromatyczny grafu K_3,3

Post autor: norwimaj » 25 sie 2011, o 12:29

Tak.

Heniek1991
Użytkownik
Użytkownik
Posty: 111
Rejestracja: 14 paź 2010, o 16:58
Płeć: Mężczyzna
Lokalizacja: Lublin / Warszawa
Podziękował: 1 raz
Pomógł: 1 raz

Wielomian chromatyczny grafu K_3,3

Post autor: Heniek1991 » 25 sie 2011, o 12:50

Powiedz jeszcze dlaczego nie mnożymy przez te permutacje?

norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

Wielomian chromatyczny grafu K_3,3

Post autor: norwimaj » 25 sie 2011, o 13:04

A dlaczego mielibyśmy mnożyć?

ODPOWIEDZ