[DM 2005/06]

Uwaga słowo graf oznacza graf prosty (chyba, że wyraźnie zaznaczono w treści zadania, że chodzi o multigraf).

[1/06] Z dokładnością do izomorfizmu, wyznacz wszystkie drzewa siedmio-wierzchołkowe.

[2/06] Udowodnij, że każdy las jest grafem dwudzielnym.

[3/06] Udowodnij, że krawędź należąca do każdego drzewa spinającego grafu G jest mostem w G. Czy twierdzenie odwrotne jest prawdziwe?

[4/06] Jaka jest minimalna liczba liści (wierzchołków stp. 1) w drzewie?

[5/06]* Wykaż, że graf o n wierzchołkach posiada nie więcej niż n - 2 przeguby.

[6/06]* Wykaż, że grafo n wierzchołkach, który nie jest ścieżką, posiada nie więcej niż n - 3 przeguby.

[7/06] Wykaż, że każdy graf r-regularny zawiera cykl o długości co najmniej r + 1.

[8/06] Które z figur szachowych (król, hetman, skoczek, goniec, wieża) mogą obejść szachownicę o wymiarach n × n (n ≥ 2) tak, aby

1. stanąć w każdym polu dokładnie raz i wrócić do punktu wyjścia?

2. wykonać każdy ruch (identyfikowany przez nieuporządkowaną parę pól) dokładnie raz i wrócić do punktu wyjścia?

[9/06] Dany jest graf G

1. Rozwiąż problem chińskiego listonosza dla grafu G

2. Wyznacz minimalne drzewo spinające grafu G

3. Przyjmując, że każdy wierzchołek oznacza miasto, a każda krawędź bezpośrednią drogę łączącą dwa miasta, zaplanuj optymalną trasę wędrowca, którego celem jest odwiedzenie wszystkich miast i powrót do punktu wyjścia, przy czym nie ma dla wędrowca znaczenia fakt, że być może odwiedzi niektóre miasta wielokrotnie. Jedynym celem jest odwiedzić wszystkie miasta i przebyć drogę o minimalnej długości. (celowo użyto słowa "wędrowiec" zamiast "komiwojażer", żeby nie zwieść studentów na manowce :) )

[10/06] Indiana Jones znalazł się nad labiryntem, w którym jest 6 podziemnych jaskiń. Każda z jaskiń połączona jest z każdą inną osobnym korytarzem, który nie przecina innego korytarza i ma zapadnię pozwalającą przejść tym korytarzem tylko jeden raz (szczegóły konstrukcji do wyjaśnienia na ćwiczeniach ;). W każdym korytarzu znajduje się skarb. Tylko dwie z jaskiń są połączone bezpiecznym przejściem z powierzchnia. Indiana może tylko raz zejść pod powierzchnię. Ile skarbów ma szanse zebrać (zakładając, że dostał 5+ z teorii grafów na studiach)?

[11/06] Czy istnieje kubiczny spójny graf niehamiltonowski?

[12/06] Dla jakich parametrów n, k, r, t ∈ N grafy K_n, K_r,s, K_r,s,t, C_n, W_n, Q_k są (a) eulerowskie, (b) półeulerowskie, (c) hamiltonowskie, (d) półhamiltonowskie?

[13/06] Które z następujących grafów są (a) hamiltonowskie, (b) półhamiltonowskie

[14/06] Wyznacz spójność wierzchołkową i krawędziową grafów przedstawionych na rysunkach powyżej.

[15/06] Iloma ciągłymi pociągnięciami ołówka można narysować figurę pokazaną na rysunku poniżej tak, aby nie rysować żadnej linii dwukrotnie?

[16/06] Udowodnij, że jeżeli w grafie G o n wierzchołkach suma stopni każdych dwóch niesąsiednich wierzchołków jest niemniejsza niż n - 1, to w grafie G istnieje droga Hamiltona (zawierająca wszystkie wierzchołki).

[17/06] Niech G będzie (2r + 1)-wierzchołkowym grafem regularnym. Wykaż, że jeżeli G zawiera cykl długości r, to jest grafem hamiltonowskim.

[18/06] Wykaż, że jeżeli wszystkie 3-wierzchołkowe podgrafy indukowane n-wierzchołkowego grafu G są spójne, gdzie n ≥ 4, to G jest grafem hamiltonowskim.

[19/06] Wykaż, że każdy dwudzielny graf eulerowski posiada parzystą liczbę krawędzi.

[20/06] Wykaż, że jeżeli G jest grafem spójnym, a H grafem powstałym z G przez dodanie krawędzi łączących pary wierzchołków o odległości 2, to każdy wierzchołek grafu H jest wierzchołkiem początkowym pewnej drogi Hamiltona (drogi zawierającej wszystkie wierzchołki grafu H).

---