3545336451

Zadanie 10.6. Korzystając z algorytmu Kruskala znaleźć optymalne drzewo w grafie o macierzy wag:

oo    19    oo    10    co"

19    oo    6    9    5

oo    6    oo    7    13

10    9    7    oo    2

oo    5    13    2    oo

11 Planarność/kolorowania

Zadanie 11.1. Określ liczbę chromatyczną grafów na rysunku.

Zadanie 11.2. Dla każdego grafu na rysunku określ, czy zawiera on K33 lub K5, lub ich podział. Rozstrzygnij, czy graf jest planarny. Jeśli tak, to narysuj jego graf plaski. Jeśli nie, to uzasadnij, dlaczego tak sądzisz.

Zadanie 11.3. Udowodnij wzór Eulera indukcją ze względu na liczbę ścian.

Zadanie 11.4. Spójny prosty graf 3-regularny o 8 wierzchołkach jest planarny. Ile ścian ma płaska reprezentacja tego grafu?

Zadanie 11.5. Spójny prosty graf płaski o 30 krawędziach ma 20 ścian. Wyznacz liczbę wierzchołków tego grafu. Zadanie 11.6. Czy spójny graf prosty bez trójkątów na 15 wierzchołkach i o 27 krawędziach może być planarny?

6