Sieć transformatorów Algorytm z powrotami

0

Witam mam pewien problem z zadaniem z algorytmów . Nie chodzi mi to napisanie kodu czy czegoś w tym rodzaju , po prostu nie rozumiem jak dla zadanych danych wejściowych mogą wyjść takie dane wyjściowe. Jeżeli był by ktoś taki dobry i napisał jak zrozumieć te zadanie to byłbym wdzięczny ;_)

W duzym nowym osiedlu planowane jest postawienie transformatorów obsługujacych
osiedlowa siec przesyłu energii elektrycznej. Ustalono ju? mo?liwe do zrealizowania
lokalizacje transformatorów i projekt linii przesyłu łaczacych te transformatory. Nalezy
jeszcze jednak, ze zbioru ustalonych lokalizacji, wybrac te, które zapewni? przesył energii
kazda linia sieci. Przy czym nalezy zadbac o to, aby wybranych lokalizacji
zapewniajacych przesył na ka?dym łaczu sieci było jak najmniej.
Zaproponuj algorytm, który na podstawie grafu sieci ustali najmniejszy podzbiór
lokalizacji transformatorów, zapewniaj?cy przesył energii w kazdym łaczu sieci.
Plik wejsciowy: Plik tekstowy o nazwie Siec_nazwisko_grupa_in.txt ma nastepujacy
format: W pierwszej linijce pliku znajduje sie liczba całkowita n (0<n?200) okreslajaca
liczba transformatorów. W kolejnych n linijkach pliku znajduje sie co najwyzej n-1 liczb
oddzielonych pojedyncza spacja i oznaczajacych linie przesyłu obsługiwane przez dany
transformator. W i -tej linijce znajduje sie numery transformatorów, z którymi jest
połaczony liniami przesyłu transformator o numerze i.
Plik wyjsciowy: Plik tekstowy o nazwie Siec_nazwisko_grupa_out.txt ma nastepujacy
format: W pierwszej linijce pliku znajduje sie jedna liczba całkowita min oznaczajaca
rozmiar podzbioru wybranych lokalizacji transformatorów. W drugiej linijce znajduje sie
min liczb całkowitych oddzielonych pojedyncza spacja i oznaczajacych numery
lokalizacji, które nalezy do tego minimalnego podzbioru.
Przykład
Siec_nazwisko_grupa_in.txt
7
3 4
4 5 7
1
1 2 7
2 7
7
2 4 5 6
Siec_nazwisko_grupa_out.txt
3
2 4 7

Jak bym nie patrzył na to zadanie to zawsze wychodzi mi że dane wyjsciowe to 1 4 7.

Z góry dziękuje za wszystkie odpowiedzi ;-)

2

Chcesz po prostu wybrać minimalny podzbiór wierzchołków grafu który będzie połączony ze wszystkimi krawędziami w grafie. Wyobraź sobie że kiedy wybierasz sobie jakis wierzchołek grafu to wszystkie krawędzie które są z nim połączone zostają pokolorowane na różowo (koniecznie na różowo!). Chcesz pokolorować wszystkie krawędzie na różowo ale jednocześnie wybrać jak najmniej wierzchołków. Pytanie brzmi: które wierzcholki należy wybrać.

Tak wygląda wejściowy graf:
graf.png

Gdybyśmy wybrali 1 4 7 jak sugerujesz to co by się stało?

graf2.png

Pokolorowałem wybrane wierzchołki i krawędzie z nich wychodzące i jedna krawędź nadal jest czarna więc tam nie ma prądu :(
A co się stanie jeśli pokolorujemy, jak sugeruje odpowiedź do tego przykładu, 2 4 7?

graf3.png

Jak widać nadal nie działa, więc odpowiedź jest błędna ;] W rzeczywistości odpowiedzia jest 1 7 2

0

Masz racje źle napisałem powinno być 1 2 7 , to chyba ta późna pora :-)
hmmmm dzięki za odpowiedz było mi potrzeba świeżego podejścia do tematu oraz potwierdzenia tego ze odpowiedz jest błędna. Szczerze mówiąc od razu też pomyślałem o pokryciu wierzchołkowym , jednak pytałem się prowadzącego zajęcia i on sugerował że jest wszystko w odpowiedziach dobrze ... ehhh napisze po prostu pokrycie wierzchołkowe.
Dzieki i Pozdrawiam.

Prowadzący rozrysował mi coś takiego, mówił też że moje rozumowanie jest lekko mówiąc błędne , jednak szczerze mówiąc nie wiem o co mu chodziło ... skoro i przy takim rozrysowaniu odpowiedz z zadania nie pasuję.
Dzięki jeszcze raz zabieram się do pisania ;_)

1 użytkowników online, w tym zalogowanych: 0, gości: 1