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