algorytm na zbadanie stopnia spójności grafu

pytanie zadane 11 maja 2015 w C i C++ przez keresmi Użytkownik (770 p.)

Witajcie!

Czy ktoś kiedykolwiek zajmował się badaniem stopnia spójności grafu? Jeśli tak to prosiłbym o jakieś wskazówki. Potrzebuje napisać program, który będzie badał ile połączeń między węzłami może być przerwanych, aby graf dalej był spójny. Może da się ten problem rozwiazać w inny spsoób?

1 odpowiedź

odpowiedź 11 maja 2015 przez Fulaphex Początkujący (470 p.)

Jesli dobrze rozumiem potrzebujesz dowiedziec sie dla zadanej pary wierzcholkow ile krawedzi musi zostac usunietych, zeby graf rozspojnic, prawda? Jesli o to chodzi, to zagadnienie to mozna rozwiazac korzystajac z twierdzenia http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem . W skrocie mowi ono, ze minimalna liczba krawedzi potrzebna do rozspojenia grafu jest rowna maksymalnemu przeplywowi w grafie. W Twoim przypadku zapewne warto ustawic przeplyw na wszystkich krawedziach na 1 i zastosowac jakis algorytm do liczenia maksymalnego przeplywu. Na poczatek, jesli nie miales nigdy stycznosci z problemem polecam algorytm forda fulkersona, bo jest to chyba najprostszy algorytm dotyczacy problemu maksymalnego przeplywu: http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm . Jesli udalo mi sie rozwiac Twoje watpliwosci, to sie ciesze :) Jesli nie, to pytaj dalej

komentarz 12 maja 2015 przez keresmi Użytkownik (770 p.)

Dokładnie rzecz ujmując ile minimalnie krawędzi musi zostaać usuniętych żeby rozspójnić graf nieskierowany (zapomniałem tego dodać o to dość istotne). Znalazłem do tego takie twierdzenie (Mengera): Maksymalna liczba dróg krawędziowo rozłącznych, łącząca dwa różne wierzchołki v i w grafu spójnego, jest równa minimalnej liczbie krawędzi w zbiorze vw-rozpinającym. To co mi podesłałeś może być bardzo użyteczne. Sam myślałem żeby zrobić to w ten sposób: Wybieram sobie jakiś losowy wierzchołek i z niego szukam możliwie jak największej liczby dróg krawędziowo rozłącznych do każdego z pozostałych wierzchołków (do każdego z osobna). Następnie połączenie miedzy wierzchołkami, które na najmniejszą liczbę dróg krawędziowo rozłącznych określa mi stopień spójności. Czy uważasz, że to myślenie jest poprawne?

komentarz 14 maja 2015 przez Fulaphex Początkujący (470 p.)

No tak. Twierdzenie, ktore Ci wyslalem dotyczy odrobine bardziej zlozonego problemu, kiedy kazda z krawedzi ma swoja pojemnosc. Rozumowanie, ktore przedstawiles wydaje sie byc poprawne, z twierdzenia wynika, ze liczba rozlacznych drog pomiedzy tymi dwoma punktami bedzie wlasnie minimalna liczba krawdzi potrzebnych do rozspojenia grafu. Pozostaje tylko naturalne pytanie jak tych sciezek szukac. Moim pierwszym pomyslem w tym wypadku bylo wlasnie wykorzystanie algorytmu liczacego przeplyw pomiedzy tymi dwoma wierzcholkami, byc moze wymyslisz do tego cos lepszego :)