Zad.1
Przeliczyć wszystkie grafy na 5 wierzchołkach.
Wiem że trzeba tutaj skorzystać z tw. Polyi i znaleźć funkcję tworzącą.
Odp. \(\displaystyle{ g(x)=1+x+2x ^{2} +4x ^{3} +6x ^{4} +6x ^{5} +6x ^{6} +4x ^{7} +2x ^{8} +x ^{9} +x ^{10}}\)
Jak to policzyć?
Zad.2
Niech \(\displaystyle{ G}\) będzie grafem, w którym każdy wierzchołek z wyjątkiem jednego ma stopień \(\displaystyle{ d}\). Pokazać, że jeżeli można pokolorować krawędzie grafu G za pomocą \(\displaystyle{ d}\) kolorów, to
i) \(\displaystyle{ G}\) ma nieparzystą liczbę wierzchołków
ii) \(\displaystyle{ G}\) ma wierzchołek stopnia zero
Wskazówką do zadania jest to, że ten jeden wierzchołek v ma stopień mniejszy od \(\displaystyle{ d}\). Każdy z \(\displaystyle{ d}\) kolorów musi być użyty przy każdym wierzchołku stopnia \(\displaystyle{ d}\). W i) rozważyć jeden z kolorów nie występujący przy wierzchołku v, ii) rozważyć jeden z kolorów występujących przy v (być może nie ma żadnego)
Zad.3
Pokazać, że dla dowolnego grafu \(\displaystyle{ G}\) jego wielomian chromatyczny ma postać:
\(\displaystyle{ p _{G} (k)= k ^{ ft| V \right| } - ft| E \right| k ^{ ft| V \right| -1 } +}\) mniejsze potęgi \(\displaystyle{ k}\)
Wskazówką jest zastosowanie indukcji względem liczby \(\displaystyle{ m}\) brakujących krawędzi.
Niezbyt wiele mi pomagają te wskazówki więc proszę osoby zorientowane w temacie o pomoc.
Dziękuję
[ Dodano: 2 Marca 2008, 23:04 ]
Naprawdę nikt nie wie jak zrobić te zadania ?