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
-
- Rozkręcam się
- Posty: 63
- Rejestracja: 25 mar 2016, 23:23
- Lokalizacja: Usa
- Podziękowania: 36 razy
- Płeć:
- Kontakt:
Freedom in relationships - that's our solution
Experience carefree connections with the top-rated site for casual dating adventures.
No strings attached dating, no promises
Real Women
Supreme casual Dating
No strings attached dating, no promises
Real Women
Supreme casual Dating