Czy można usunąć krawędź bez odłączania wykresu?

Zanim zacznę, tak, to jest praca domowa. Nie napisałbym tutaj, jeśli nie starałem się tak mocno, jak tylko mogłem, rozwiązać ten problem przez ostatnie 14 godzin i nie udało mi się.Czy można usunąć krawędź bez odłączania wykresu?

Problem jest następujący: Chcę sprawdzić, czy mogę usunąć krawędź z połączonego grafu nieodłączonego bez odłączania go w czasie O (V), a nie tylko liniowo.

Co doszedłem tak daleko:

Krawędź cykl może być usunięte bez odłączania wykres, więc ja po prostu sprawdzić, czy wykres ma cykl. Mam dwie metody, które mogą być używane, jeden jest DFS, a następnie sprawdzanie, czy mam tylne krawędzie; drugi to liczenie Vs i Es i sprawdzenie, czy | E | = | V | - 1, jeśli to prawda, to wykres jest drzewem i nie ma węzła, który możemy usunąć bez jego odłączenia.

Oba wcześniejsze podejścia rozwiązują problem, ale oba wymagają O (| E | + | V |), a książka mówi, że istnieje szybszy sposób (to prawdopodobnie zachłanne podejście).

Czy mogę uzyskać wskazówki, proszę?

EDYCJA: Dokładniej, to jest moje pytanie; mając podłączony wykres G = (V, E), czy mogę usunąć krawędź e w E i czy otrzymany wykres nadal będzie podłączony?

Źródło

2012-01-03 Fingolfin

Bądź nieco dokładniejszy w komunikacie. Pytasz "biorąc pod uwagę podłączony wykres G = (V, E), czy mogę usunąć konkretną krawędź e w E i czy otrzymany wykres nadal będzie podłączony?" lub "Biorąc pod uwagę wykres taki jak poprzednio, czy istnieje pewna krawędź e w E, dla której wynikowy wykres nie jest już połączony?" –

Pytanie edytowane, przepraszam. Muszę sprawdzić, czy mogę usunąć krawędź z E i nadal mieć podłączony wykres. – Fingolfin

Termin techniczny jest [most] (http://en.wikipedia.org/wiki/Bridge_ (graph_theory)) – sdcvvc

Jakiekolwiek rekursywne przejście przez wykres, zaznaczanie węzłów podczas ich odwiedzania i zwarcie w celu zwrócenia wartości true, jeśli kiedykolwiek napotkasz zaznaczony węzeł, rozwiąże problem. To zabiera O (| V |) do przechodzenia przez cały wykres, jeśli nie ma krawędzi, która może zostać usunięta, i mniej czasu, jeśli zatrzyma się wcześniej, aby zwrócić wartość true.

edit

Tak, recusive przejścia całego wykresu wymaga O (| V | + | E |) czas, ale tylko przemierzać cały wykres, jeśli nie ma cykli - w tym przypadku | E | = | V | -1 i zajmuje tylko O (| V |) czas. Jeśli istnieje cykl, znajdziemy go po przekroczeniu najwyżej | V | krawędzie (i odwiedzając najwyżej węzły | V | +1), które również zabierają czas O (| V |).

Oczywiście, podczas przechodzenia z węzła (innego niż pierwszy), nie bierzesz pod uwagę krawędzi, która została użyta do przejścia do węzła, ponieważ spowoduje to natychmiastowe wyświetlenie już odwiedzonego węzła.

Źródło

2012-01-03 02:47:07

Po prostu wyjaśnij mi swoje rozumowanie, sir? Uruchamianie procedury rekursywnego przeglądania na podłączonym wykresie zwykle zajmuje O (| E | + | V |), ponieważ potrzebuję O (V) do zaznaczenia węzłów, a O (2 | E |) jedynie do sprawdzenia krawędzi łączących węzły . Rekursywne czy nie, nie zbliża się do O (| V |), więc w jaki sposób zwracanie wartości true, gdy przeciwdziałanie odwiedzanego węzła sprowadza się do O (V)? Ponadto, jeśli zwrócę prawdę podczas kontrowania odwiedzanego, mogę rzeczywiście zwrócić wartość true podczas śledzenia wstecznego ze zlewu, mogę powiedzieć, że mam cykl, ale nadal nie sprawdzam, czy to robię, czy nie. – Fingolfin

Wow !! To ma teraz sens! Wielkie dzięki, sir! – Fingolfin

Aha. Myślałem, że będzie jakiś trik z udziałem | E | = | V | -1, ale po wakacjach umieram na mózg i go nie widzę. –

Z tego co czytam, DFS bez powtórzeń jest uważany za O (| V |), więc jeśli weźmiesz krawędź e, i niech te dwa wierzchołki, które łączy to u i v, jeśli uruchomisz DFS z u, ignorując e, możesz domyślać się, że e nie jest mostem, jeśli v zostanie odkryte, i biorąc pod uwagę, że DFS bez powtórzeń to O (| V |), wtedy to, jak sądzę, zostanie uznane za O (| V |).

Źródło

2012-01-03 02:30:07 PlexQ

Nie, pełne DFS, nawet bez powtarzania wciąż jest O (| V | + | E |) od ciebie trzeba spojrzeć na wszystkie krawędzie, aby upewnić się, że nie trafiają do węzłów, które nie zostały jeszcze odwiedzone. Jeśli zatrzymasz przemierzanie, gdy tylko znajdziesz pętlę, to tylko wymaga patrzenia najwyżej | V | krawędzie. –

Sądzę, że powinienem był wyjaśnić, wydawało się to trochę oczywiste, że gdy znajdziesz v, udowodniłeś, że e nie jest mostem iw ten sposób odpowiedziałeś na problem, czasami zapominałeś, że nie możesz brać niczego za pewnik w dowodach: D – PlexQ

Wyświetlane są wszystkie krawędzie E i krawędź i zaznacz jeden po drugim dwa odwiedzone wierzchołki końcowe. Jeśli podczas ruchu odkryjemy, że dwa wierzchołki zostały wcześniej odwiedzone przez niektóre krawędzie i możemy usunąć tę krawędź.

Musimy wziąć krawędzie co najwyżej | V | czas, aby sprawdzić, czy warunek ten spełnia.

W najgorszym przypadku może to wyglądać, za każdym razem, gdy przyjmujemy przewagę, odwiedzamy co najmniej nowy wierzchołek. Następnie są | V | wierzchołki i musimy wziąć | V | krawędzie dla tej konkretnej krawędzi.

Najlepszym przykładem może być ten z | V |/2 + 1 e

Źródło

2017-04-04 22:17:35 YashM

Czy można usunąć krawędź bez odłączania wykresu?

Odpowiedz

Powiązane problemy