Kolorowanie grafu

[norbert22]

Mam zadanie: na ile sposobów można poprawnie pokolorować niżej narysowany graf za pomocą 666 kolorów?



Można pokolorować go za pomocą 4 i 5 kolorów. Z 5 kolorami nie ma problemu. To będzie kombinacja 5 z 666. Natomiast z 4 kolorami mam problem. Pokolorowałem graf w ten sposób: a=1, b=2, c=3, d=1, e=4. Doszedłem do wniosku, że jest łącznie 12 możliwości pokolorowania tego grafu za pomocą 4 kolorów, gdzie a=1, ponieważ a i e oraz a i d muszą tak samo pokolorowane, zaś b,c,d oraz b,c,e można pokolorować na 6 różnych sposobów. 6x2=12. Nie wiem jak dalej ruszyć. Proszę o jakąś wskazówkę.

[Jacek_Karwatka]

Pytanie co to znaczy policzyć sposoby kolorowania.
Zwykle liczymy tylko istmie rożne sposoby kolorowania. Permutacja kolorów jest utożsamiana jako to samo kolorowanie. Zgodnie z tą definicja jeśli użyjemy 5 kolorów jest tylko jeden sposób pokolorowania grafu (każdy wierzchołek ma inny kolor)

Jeśli użyjemy 4 kolorów to są dwa istotnie różne przypadki:
1. ten sam kolor maja wierzchołki a i e
2. ten sam kolor maja wierzchołki a i d
mniej kolorów użyć się nie da.

w sumie mamy 3 istotnie rożne sposoby pokolorowania grafu dysponując pięcioma lub większą liczbą kolorów (np 666) Zakładam ze nie wszystkie kolory muszą być wykorzystane

Jeśli uwzględniamy także permutacje kolorów to kolorowań jest w sumie:
1. przypadek kiedy używany 5 różnych kolorów 666*665*664*663*662 (najpierw wywieramy kolor dla a, potem z pozostałych dla b itd)
2. przypadek kiedy używamy 4 kolorów i wierzchołki a i e są pokolorowane tym samym kolorem 666*665*664*663 (najpierw wywieramy kolor dla a i e, potem z pozostałych dla b itd)
3. przypadek kiedy używamy 4 kolorów i wierzchołki a i d są pokolorowane tym samym kolorem 666*665*664*663 (najpierw wywieramy kolor dla a i d, potem z pozostałych dla b itd)

tak licząc mamy w sumie 666*665*664*663*662+2 * 666*665*664*663 sposobów kolorowania