1. Udowodnij, że graf niezorientowany jest drzewem wtedy i tylko wtedy, gdy dowolne dwa jego wierzchołki można połaczyć dokładnie jedną drogą.
   

2. Niech G będzie grafem niezorientowany, którego wierzchołkami sa liczby naturalne 1,..., n. Niech Tab będzie tablicą, przechowującą informacje o danym podziale zbioru wierzchołków grafu G: Tab[i] jest nazwą tego zbioru w danym podziale, do którego należy wierzchołek i.
   Zaimplementuj operacje Find i Union w tym modelu. Oszacuj koszt algorytmu Kruskala z Twoją implementacją operacji Find-Union.  

3. Niech G = <V, E>  będzie grafem niezorientowanym, spójnym.  Niech T₁ = <V, E₁> oraz T₂ = <V, E₂> będą dwoma drzewami rozpinającmi grafu G. Udowodnij, że dla dowolnej krawędzi a Î E₁\ E₂, istnieje krawędź b Î E₂\ E₁, taka że  graf <V, (E₁\{a}) È{b}> jest też drzewem rozpinającym grafu G.
   

4. (a) Narysuj drzewo powstałe w wyniku wykonania następującego ciągu instrukcji, jeżeli struktura  Find-Union  została zaimplementowana  na drzewach z balansowaniem i kompresją ścieżek:  
   
   {P := Union(P,A,B); P :=Union (P,C,D); P:= Union(P,E,F); P:= Union(P,G,H);
    P := Union(P,H,E); P := Union(P,C,E); P := Union (P,E,B); X :=Find(P,H);}
   
   Zakładamy, że pocztkowo P = {A, B, C, D, E, F, G, H}.
   (b)  Narysuj drzewo powstałe w wyniku wykonania tych samych instrukcji, jeśli struktura Find-Union została zaimplementowana bez balansowania i bez kompresji ścieżek.

5. Podaj przykład grafu niezorientowanego, w którym drzewo najkrótszych ścieżek z pewnego wierzchołka jest identyczne z drzewem rozpinającym o minimalnym koszcie. Czy te dwa drzewa są zawsze takie same?
   
   
6. Zapropnuj iteracyjną wersję algorytmu badania sþójności grafu, opartą o metodę DFS.
   
   
7. Niech będzie dana sieć dróg. Zakładamy, że wszystkie drogi w tej sieci są dwukierunkowe oraz, że z każde dwie miejscowości są połączone  drogą,  chociaż niekoniecznie bezpośrednio. Drogę nazwiemy krytyczną, jeśli blokada tej drogi (wyłączenie jest z ruchu) spowoduje, że pewne miejscowości zostaną odcięte od innych ( nie będzie do nich można dojechać używając dróg tej sieci) .  Napisz program, który dla zadanej sieci bada, czy istnieją w niej drogi krytyczne i wypisuje je.
   

 

« poprzedni punkt

następny punkt »