drzewo

warning: Creating default object from empty value in /usr/share/drupal6/modules/taxonomy/taxonomy.pages.inc on line 33.

Ćwiczenia 11: drzewa, cykle Eulera i Hamiltona

Zadanie 1

Centrum grafu G to zbiór wierzchołków v, dla których maxw d(v,w) jest najmniejsze. Udowodnij, że centrum drzewa to pojedynczy wierzchołek albo para wierzchołków połaczonych krawędzią.

Zadanie 2

Udowodnij twierdzenie Cayleya o zliczaniu drzew etykietowanych: Kn ma nn-2 drzew rozpinających
(a) wskazując bijekcję między takimi drzewami a (n-2)-ciągami o elementach ze zbioru {1,...,n} (kody Prufera);
(b) sumując liczby drzew o ustalonym układzie stopni wierzchołków.

Zadanie 3

Ćwiczenia 10: grafy - podstawowe pojęcia

Zadanie 1

Udowodnij, że na każdym przyjęciu są dwie osoby o takiej samej liczbie
znajomych.

Zadanie 2

Udowodnij, że przynajmniej jeden z grafów G, G' (dopełnienie) jest spójny. Niech diam(G) oznacza średnicę grafu G (nieskończoność jeśli G jest niespójny) i niech f(G) = min(diam(G), diam(G')). Znajdź sup f(G) po wszystkich grafach G.

Zadanie 3

Udowodnij, że w K6 dowolnie pokolorowanym krawędziowo na 2 kolory jest
monochromat. trojkat (są nawet dwa!), ale w K5 niekoniecznie.

Zadanie 4

Rozstrzygnij, czy istnieje:

Subskrybuje zawartość