Mam pytanko, załóżmy, że w grafie są jakieś mosty i trzeba dodać jak najmniej krawędzi, żeby tych mostów się pozbyć, np taki graf:
Składa się z 5 mostów, a do uszczelnienia wystarczy jedna dodatkowa krawędź ;d Mosty można łatwo wyznaczyć za pomocą tzw. funkcji Low, ale jak taki graf uszczelnić ? :d
Rozumiem że chodzi ci o to aby usunięcie jednej krawędzi nie zniszczyło spójności grafu? myślę że dobrym wyjściem będzie połączyć wierzchołki stopnia pierwszego =P problem będzie przy nieparzystej liczbie wierzchołków stopnia pierwszego, ten jeden nieparzysty połączysz z dowolnym innym wierzchołkiem i powinno być ok.
Tak, dokładnie: usunięcie jednej krawędzi nie może zniszczyć spójności grafu.
Niestety, wymyśliłem coś podobnego jak ty i nie przeszło :(
po dłuższym myśleniu już wiem dlaczego: mianowicie zobacz taki graf. Wszystkie wierzchołki mają stopień co najmniej 2, a most istnieje :(
Czy ktoś wie, jak rozwiązać ten problem w ogólności ? :(
Myślałem że cały graf składa się z mostów ;-)
Pomysł 1.
Stworzyć cykl eulera łącząc nieparzyste wierzchołki krawędziami.
Pomysł 2.
spróbować wygenerować drzewo spinające grafu, i połączyć liście tego drzewa tak jak w poprzednim przypadku ale nie dodając krawędzi które istnieją już w grafie! następnie do wyniku dodać wszystkie krawędzie grafu ( te które nie były w drzewie spinającym ). Nie jestem pewny czy to zadziała dla każdego grafu, trzeba nad tym pomyśleć =P
Teraz takie moje spostrzeżenie, aby to było jak najbardziej optymalne trzeba dbać aby każdy wierzchołek drzewa spinającego miał stopień 2, dzięki temu graf powinien mieć bardzo mało wierzchołków stopnia 1 więc i mało dodatkowych krawędzi.
I całkiem możliwe że w pierwszej kolejności trzeba postarać się aby w tym drzewie powstał cykl eulera, czyli połączyć tak te krawędzie aby każdy wierzchołek był stopnia parzystego.
Jeee, wreszcie rozwiązałem :)
Metoda jest taka:
Dowodu nie będę pisac ;) można przyjąć na słowo, że to działa ;]
pkt. 1 to właśnie robi drzewo spinające =P tylko wydaje mi się ze aby uzyskać minimalną ilość krawędzi które usuną mosty to trzeba te drzewo spinające czy też Graf' tworzyć tak aby było tam jak najwięcej gałęzi o stopniu 2, popatrz na swój przykład wyżej.
Jeden z wariantów G' będzie miał 4 punkty o stopniu 1, a inny wariant ma ich tylko 2 :]
graf potrzebny dla punktu 1' mozna w miare latwo wykonac "symulujac" "zapadanie sie" cykli. na danym grafie, poki istnieja cykle, znajduj dowolny (nie wazne jaki) cykl i sklej wszystkie wierzcholki cyklu w pojedynczy wierzcholek (usuwajac krawedzie pomiedzy zapadajacymi sie wierzcholkami, ale zachowujac wszystkie pozostale) i kontynuuj szukanie
graf ktory pozostanie na placu boju jest drzewem, ale nie spinajacym. zostana same mosty z grafu oryginalnego, sklejone tymi wierzcholkami, ktore mialy miedzy soba jakiekolwiek sciezki. aby "uzupelnic" oryginalny graf do postaci "bezmostowej" trzeba zrobic to samo co wymysliliscie - na otrzymanym grafie znalezc wierzcholki stopnia 1 i je polaczyc (czyli ceil(N/2) krawedzi).
jedyna uwaga - wierzcholki grafu otrzymanego moga sie "mapowac" na wiele wierzcholkow grafu oryginalnego z racji zapadania sie cykli. jesli chce sie okreslic nie tylko ILE ale i JAKIE krawedzie nalezy dolozyc - trzeba te wierzcholki "rozdmuchac" z powrotem i wybrac dowolne polaczenie - patrz przyklad 2
przyklad1)
wierzch: ABCDEF
kraw: AB, AC, BC, CD, AE, DF, EF
->znaleziono cykl ABC, sklej wierzcholki ABC w jeden np 'X', graf przeksztalca sie w:
wierzch: [X][X][X]DEF
kraw: [], [], [], [X]D, [X]E, DF, EF
->znaleziono cykl XDEF, sklej wierzcholki XDEF w jeden np 'Y', graf przeksztalca sie w:
wierzch: [Y][Y][Y][Y][Y][Y]
kraw: [], [], [], [], [], [], []
->nie ma wiecej cykli
wniosek: nie ma krawedzi, nie ma mostow.
przyklad2 (z rysunku drugiego)
wierzch: ABCDEF
kraw: AB, BC, CA, CD, DE, DF, EF
->cykl: ABC -> X
wierzch: [X][X][X]DEF
kraw: [], [], [], [X]D, DE, DF, EF
->cykl: DEF->Y
wierzch: [X][X][X][Y][Y][Y]
kraw: [], [], [], [X][Y], [], [], []
->brak cykli
wniosek: sa krawedzie, sila rzeczy wszystkie sa mostami. pozostala jedyna krawedz to XY. patrzac na oryginalny zestaw krawedzi mozna znalezc wszystkie mosty - z {AB, BC, CA, CD, DE, DF, EF} znajdz krawedzie rozpiete pomiedzy {XY}, czyli pomiedzy {A,B,C} a {D,E,F} czyli wszytkie mosty to CD..
*) zlozonosc pewnie okropna. ale kontrprzykladu dla "zapadania sie cykli" nie znalazlem :) jedyna 'trudnosc' to w kazdej iteracji wyszukac dowolny cykl
Przesadzacie :)
punkt pierwszy zrealizowałem za pomocą funkcji low i zwykłego przeszukiwania grafu w głąb, macie linka, rozdział Mosty:
http://www.astagor.net/putinf/data/algorytmy/Graf-2spojne.html
well.. dawno nie mialem stycznosci z teoria grafow, wiec napisalem co wymyslilem.. ot co:)
edit:
http://www.astagor.net/putinf/data/algorytmy/Graf-2spojne.html
yeay, bede mial co czytac wieczorem :)
quetzalcoatl napisał(a)
well.. dawno nie mialem stycznosci z teoria grafow, wiec napisalem co wymyslilem.. ot co:)
edit:
http://www.astagor.net/putinf/data/algorytmy/Graf-2spojne.html
yeay, bede mial co czytac wieczorem :)
Ktoś ma za dużo wolnego czasu ;-P No nic wracam do elektroniki, która już mi bokiem wychodzi [diabel]