Grafy - dwa zadania

[fcluki07]

(a) Udowodnij, że graf niezorientowany jest drzewem wtedy i tylko wtedy, gdy dowolne dwa różne wierzchołki są połączone dokładnie jedną drogą, której wszystkie wierzchołki są różne.


(b) Załóżmy, że Twoim zadaniem jest zorganizowanie wystawy. Jednym z problemów, które musisz rozwiązać, jest takie rozmieszczenie eksponatów i takie umieszczenie w przejściach znaków wskazujących, jak powinni poruszać się zwiedzający, aby można było zobaczyć każdy eksponat. Sformułuj problem i zaproponuj rozwiązanie w terminach teorii grafów.

Takie oto dwa zadanka mi zadali ikurcze nie wiem jak je mozna ugrysc. Jak ja nie lubie takiej wirtualnej matematyki

[ Dodano: 28 Marca 2008, 17:21 ]
bardzo prosze o wsparcie przy tych zadaniach bo nauczyciele nacieraja a ja niestety nie umiem tego zrobic

[ Dodano: 28 Marca 2008, 19:39 ]
prosze pomózcie z tymi zadankami bo ja juz osiwialem przy tym

[ Dodano: 29 Marca 2008, 11:53 ]
Nikt nie pomoze?? chociaz nakierujcie na odpowiednia droge

[saker]

(a) załóżmy, że dowolne 2 wierzchołki w grafie \(\displaystyle{ G}\) są połączone dokładnie jedną ścieżką. Oczywiście \(\displaystyle{ G}\) jest spójny. wystarczy pokazać, że jest acykliczny. Jeśli w \(\displaystyle{ G}\) byłby jakiś cykl \(\displaystyle{ C}\), to niech \(\displaystyle{ v,w}\) będą wierzchołkami leżącymi na cyklu. Widać, że między \(\displaystyle{ v}\) i \(\displaystyle{ w}\) znajdziemy dwie różne ścieżki - sprzeczność.
Zatem \(\displaystyle{ G}\) musi być grafem acyklicznym, a w konsekwencji drzewem.
W drugą stronę - oczywiste.

(b) Niech eksponaty będą wierzchołkami grafu, przejścia krawędziami. Musisz tak poustawiać eksponaty, aby powstały graf był hamiltonowski. Odpowiedni cykl Hamiltona da ci rozwiązanie.