Bardzo proszę o pomoc w rozwiązaniu tego zadania.
Dane jest drzewo T o następującej strukturze:
- korzeń (poziom 0) posiada k > 9 potomków.
- wysokość drzewa wynosi H > 9,
- każdy węzeł na poziomie h < H posiada k + h potomków
Wszystkie węzły drzewa na poziomie h oznaczamy jako V(h) (0<h<=H)
Z drzewa T budujemy graf G, w taki sposób, że:
a) Tworzymy graf T', poprzez dodanie minimalnej liczby krawędzi do grafu T, niezbędnej do tego, aby węzły w każdym ze zbiorów V(h) (1<=h<=H), utworzyły klikę.
b) G jest dopełnieniem grafu T'
Pytanie 1: Czy graf jest eulerowski?
Pytanie 2: Jaka jest liczba chromatyczna grafu T'?
Przedstaw tok rozumowania.
Grafy - drzewa
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij