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ą.
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.
Podaj przykłady grafów na wszystkie cztery kombinacje:
(istnieje/nie istnieje) x (cykl Eulera/cykl Hamiltona)
Udowodnij, ze jeśli G jest spójny o k>0 wierzchołkach nieparzystych stopni,
to k jest parzyste i k/2 jest najmniejszą liczbą krawędziowo rozłącznych
łańcuchów pokrywających wszystkie krawędzie G.
Z kompletu 28 kamieni domina (od 0-0 do 6-6) usuwamy kamienie 0-1, 0-2,
0-3. Ile jeszcze trzeba usunać, żeby resztę dało się ułożyć w łańcuch
zamknięty?
Które pełne grafy dwudzielne i trójdzielne są eulerowskie?
hamiltonowskie?
Pokaż, że graf Petersena jest maksymalny niehamiltonowski.
Pokaż, że turniej jest hamiltonowski <=> jest silnie spójny.
Udowodnij, że jesli z kodu Graya zdefiniowanego rekurencyjnie
G(0) = pusty ciąg; G(n+1) = (0G(n); 1G(n)R)
wypisać wektory zawierające k jedynek, to dwa sąsiednie (cyklicznie)
wektory mają odległość Hamminga równą 2. Napisać wzór rekurencyjny na taki
'okrojony' kod Graya G(n,k).