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?
Wielomian chromatyczny grafu K_3,3
-
- 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
-
- 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
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: - 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
To samo.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
-
- 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
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}}}\)
-
- 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