• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

algorytm na zbadanie stopnia spójności grafu

+1 głos
1,017 wizyt
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ź

+1 głos
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 :)

Podobne pytania

0 głosów
1 odpowiedź 190 wizyt
pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)
0 głosów
0 odpowiedzi 14 wizyt
pytanie zadane 14 listopada w HTML i CSS przez MacGyver Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 152 wizyt

89,693 zapytań

138,297 odpowiedzi

309,243 komentarzy

59,622 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...