Zadanie z teorii grafów ninja2020: 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.

wredulus_pospolitus: no dobrze ... a na jakim etapie się zatrzymałeś

ninja2020: No jeśli na poziomie h=1 mamy k węzłów to na każdym poziomie liczba ta rośnie o 1. Czyli na końcu mamy k + (h − 1) węzłów. No ale nie wiem czy wszystkie wierzchołki są parzyste czy też nie. Ciężko mi to sobie wyobrazić, gdzie są one połączone.

wredulus_pospolitus: zauważ, że o ile w drzewie T nie wiemy jakie ma połączenia (ale wiemy ile jest węzłów na danym poziomie), o tyle T' jest KLIKĄ Co daje już nam informację jak wyglądają tam połączenia. Jaka jest definicja kliki