• 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

VPS Starter Arubacloud
+1 głos
1,361 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ź 226 wizyt
pytanie zadane 26 kwietnia 2015 w C i C++ przez keresmi Użytkownik (770 p.)
0 głosów
0 odpowiedzi 94 wizyt
pytanie zadane 14 listopada 2022 w HTML i CSS przez MacGyver Nowicjusz (120 p.)
0 głosów
0 odpowiedzi 309 wizyt

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...