Problem A - Pułapka na myszy
Problem B - Drzewo rozpinające
Problem C - Manipulowanie tablicą
Problem D - Figury wpisane
Problem E - Słownik danych
Problem F - Domki z pni
Problem G - Binarne drzewa gry
Problem H - Mnożenie wielomianów

 


 

 

1983

Problem B - Drzewo rozpinające


Opis

Graf (ang. graph) G jest zbiorem wierzchołków (ang. vertices) V oraz zbiorem krawędzi (ang. edges) E. Krawędź jest połączeniem pomiędzy dwoma (niekoniecznie różnymi) wierzchołkami. Spójny graf (ang. connected graph)  jest grafem, w którym można po krawędziach przejść z każdego wierzchołka do każdego innego. Drzewo rozpinające (ang. spanning tree) T dla spójnego grafu G jest grafem, który posiada taki sam zbiór wierzchołków V i którego zbiór krawędzi E' jest podzbiorem (niekoniecznie właściwym) zbioru krawędzi E. Co więcej, T musi być grafem spójnym bez cykli, tj. pomiędzy dwoma dowolnymi wierzchołkami istnieje tylko jedna ścieżka przejścia po krawędziach. W ten sposób E' jest minimalnym podzbiorem E, takim iż T jest grafem spójnym. Drzewo rozpinające niekoniecznie jest unikalne.

Jako przykład, poniższy graf zawiera cztery węzły (1-4) i pięć krawędzi (A-E):

 

Dla tego grafu są możliwe trzy drzewa rozpinające:

 

   

 

Masz napisać program, który wygeneruje drzewa rozpinające z grafów. Grafy będą się składały z co najwyżej 15 wierzchołków. Twój program powinien przetworzyć dowolną liczbę grafów wejściowych i dla każdego z nich wyświetlić krawędzie jednego z drzew rozpinających.

 

Specyfikacja wejścia

Dane wejściowe dla twojego programu będą się pojawiały w zestawach. Pierwszy wiersz zestawu zawiera liczbę n - ilość wierzchołków grafu G. Następnie pojawi się n wierszy, z których każdy reprezentuje jeden wierzchołek grafu oraz jego połączenia. Pierwszy z tych wierszy odnosi się do wierzchołka 1, drugi do wierzchołka 2, itd. Wiersz reprezentujący wierzchołek będzie zawierał n liczb określających krawędzie (połączenia) pomiędzy tym wierzchołkiem a pozostałymi wierzchołkami grafu. Liczby w wierszu odnoszą się do kolejnych wierzchołków grafu. Wartość 0 oznacza brak krawędzi, a 1 istnienie krawędzi pomiędzy wierzchołkiem określonym przez wiersz a wierzchołkiem określonym przez liczbę w wierszu. Na przykład, dla wiersza reprezentującego wierzchołek k pierwsza liczba 0 lub 1 określa, czy istnieje krawędź od wierzchołka k do wierzchołka 1, druga liczba określa istnienie krawędzi od wierzchołka k do wierzchołka 2, i-ta liczba w tym wierszu określa istnienie krawędzi od wierzchołka k do wierzchołka i. Dane wejściowe kończą się, jeśli pierwszy wiersz zawiera wartość 0.

 

Specyfikacja wyjścia

Dla każdego zestawu danych reprezentującego graf należy wyświetlić listę par wierzchołków (po jednej parze na wiersz wydruku) określających krawędzie drzewa rozpinającego dla tego grafu. Na tej liście każda krawędź powinna być umieszczona dokładnie jeden raz.

 

Przykładowe dane wejściowe

4
0 1 0 1
1 0 1 1
0 1 1 1
0 1 1 0
0

 

Przykładowe dane wyjściowe

THE CONNECTIONS ARE

1 - 2
2 - 3
2 - 4

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.