Dlaczego wykresy skierowane są ważne?

18

Czytaliśmy o algorytmach dla MST, silnej łączności, routingu itp. W grafach ukierunkowanych.

Ostatnio ludzie przeprowadzają badania nad algorytmami dynamicznymi i odpornymi na uszkodzenia dla grafów ukierunkowanych.

Zastanawiałem się jednak, czy istnieją jakieś praktyczne zastosowania, w których sieć grafów podkreślających jest „Kierowana”. Poza sieciami społecznościowymi wszystkie problemy, o których mogłem pomyśleć, takie jak sieć kolejowa / drogowa, sieć internetowa itp., Dotyczą wyłącznie niekierowanych wykresów.

Edycja 1: Rozumiem, że można ich użyć do modelowania niektórych scenariuszy, do których kierowane są linki, ale zastanawiałem się, jak często te scenariusze występują w świecie rzeczywistym i jak ważne jest badanie tolerancji błędów dla grafów ukierunkowanych.

graphs graph-theory fault-tolerance chyle
źródło
6
Dwie najbardziej znane klasy grafów ukierunkowanych we wszystkich dziedzinach informatyki to drzewo i DAG (Directed Acyclic Graph). Drzewo jest używane w wielu rzeczach (np. Drzewa genealogiczne, hierarchie); DAG może tworzyć bardziej wyrafinowane wersje tych. DAG są używane zasadniczo, gdy masz zestaw encji, które są od siebie zależne. Kiedy twój problem ma komponent „czas” lub „krok po kroku”, ukierunkowanie reprezentuje ten nieubłagany marsz postępu. DAG widzisz w takich elementach, jak schematy blokowe, oprogramowanie do zarządzania pakietami i formularze SSA reprezentujące pośrednie kompilatory.
Nie będę istniał Idonotexist
2
OK, jakie jest twoje aktualne pytanie? Czy chcesz wiedzieć, dlaczego wykresy kierunkowe są ważne lub dlaczego ważna jest odporność na błędy w wykresach ukierunkowanych? To są dwa całkowicie oddzielne pytania.
David Richerby,
2
Wasze przykłady, choć fizycznie „nieukierowane” we wdrażaniu, nadal często kierują nad nimi wykresy logicznie działające. Na przykład pociągi nie jeżdżą dwukierunkowo - jeżdżą w jedną lub drugą stronę zgodnie z rozkładem jazdy. Powiedzmy, że nie planuje się pociągów, a jedynie pasażerów. Następnie ta osoba jest zainteresowana nakierowanym wykresem, pomimo arbitralnego faktu, że pociągi teoretycznie mogą podróżować w obie strony koleją.
Darren Ringer
5
chyle: Sieci z pewnością mogą skorzystać z tego, że są reprezentowane przez ukierunkowany wykres. Większość domowych połączeń internetowych jest asymetryczna. Łącza upstream i downstream mogą mieć zupełnie inne właściwości (przepustowość, opóźnienie, utrata pakietów itp.)
Alexander - Przywróć Monikę
1
Nie wiem o wszystkich innych, ale moje drzewo genealogiczne to digraf. Nie jestem rodzicem mojej matki.

Odpowiedzi:

36

Przypominając, że skierowany wykres jest wykresem, na którym krawędzie mają powiązany z nimi kierunek.

Za pomocą grafu kierunkowego można przedstawić asymetryczne relacje między węzłami, natomiast na grafie niekierowanym możemy przedstawić tylko relacje symetryczne .

Praktycznie, korzystając z ukierunkowanego wykresu, możesz przedstawić:

  • Sieci drogowe (za pomocą ukierunkowanego wykresu możesz przedstawić kierunek ulic);
  • hiperłącza łączące strony internetowe ;
  • zależności w modułach oprogramowania ;
  • relacje drapieżnik-drapieżnik ;
  • deterministyczny automat skończony .

Oprócz tych klasycznych przykładów, możesz przedstawić wiele innych rzeczywistych scenariuszy (handel finansowy, planowanie, choroby zakaźne, cytowanie, przepływ kontroli itp.), Które wymagają uporządkowanego związku [1] .

darioSka
źródło
4
Świetna odpowiedź. Myślę, że OP zapomina, że ​​kiedy masz ulicę, tak naprawdę masz dwie ulice (po jednej dla każdego kierunku, zwykle idealnie równoległe). Oni mogą być przedstawione w postaci wykresu prosty, ale graf skierowany dodać istotne informacje do modelu.
ecc
Podoba mi się to i zauważam, że w tej odpowiedzi można powiedzieć, że hiperłącza są połączone stronami internetowymi - co wyklucza użycie funkcji Wstecz. ;-)
SDsolar
Aby umieścić komentarz @ ecc w języku narodowym, masz dwa węzły połączone dwoma krawędziami. Każda krawędź jest skierowana przeciwnie do drugiej. Widać to często w deterministycznych diagramach stanów. W przypadku ulic zmniejszyłoby się do jednej krawędzi, zarówno skierowanej (jednokierunkowej), jak i nieukierunkowanej.
SDsolar
4
@ecc również, skąd pochodzę (Kalifornia), mamy ulice jednokierunkowe
k_g
5

Grafy kierunkowe istnieją. Jak wspomniano w komentarzach, w szczególności Directed Acyclic Graphs (DAG) są niezwykle przydatne w wielu zadaniach obliczeniowych, takich jak kompilacja kodu.

Warto również zauważyć, że większość algorytmów grafu ukierunkowanego można zastosować w przypadku niekierowanego, po prostu zastępując każdą nieukierowaną krawędź dwoma skierowanymi krawędziami. Podwójności tego, próbując stworzyć wykres kierowany z wykresu niekierowanego, nie można zrobić w przypadku większości algorytmów.

Cort Ammon - Przywróć Monikę
źródło
3

Początki sortowania topologicznego (podstawowa operacja na ukierunkowanych grafach acyklicznych) leżą w sieciach zależności w zarządzaniu projektami, w szczególności w metodzie PERT . Kahn i Lasser cytują PERT w swoich pracach i opierają na nim swoje przykłady, np

Sieć PERT obejmującą 30 000 czynności można zamówić w mniej niż godzinę czasu pracy maszyny.

W przypadku tego typu sieci planowanie zadań online jest nadal wykonywane; na przykład system ETL planuje uruchamianie zadań dopiero po uruchomieniu zadań dostarczających ich dane wejściowe.

KWillets
źródło
2

Odpowiedź: Z PO dedukuję, że pytanie jest faktycznie związane z SDG (Signed Directed Graphs). Oto moja odpowiedź, która dotyczy podstawowych ukierunkowanych wykresów, a następnie prowadzi do SDG.

Grafy kierunkowe są szeroko stosowane w analizie drzew błędów w systemach przemysłowych. Po wyeliminowaniu przyczyn błędu postępujesz zgodnie z kierowanym wykresem, aby zbadać inne możliwości.

Kierowane wykresy są wykorzystywane do zapobiegania ponownemu produktywnemu przeglądaniu węzłów, które zostały skutecznie wyeliminowane. W diagnostyce usterek często krytyczny jest czas na przywrócenie usługi. W złożonych systemach przemysłowych zawsze istnieje równoległe drzewo oparte na czasie, co może doprowadzić do całkowitego zamknięcia systemu, jeśli usterka nie zostanie naprawiona w różnych terminach. Cofanie się w przód i w przód prawdopodobnie prowadziłoby do całkowitej awarii, co może powodować znacznie bardziej czasochłonne operacje renowacji (takie jak opróżnianie zbiorników i rurociągów w celu ponownego uruchomienia rafinerii).

To jest jak przycinanie gałęzi drzewa - nie musisz wracać do pnia, gdy próbujesz znaleźć jedną gałązkę.

Cele SDG mają dodatkową właściwość polegającą na udzielaniu wskazówek opartych na prawdopodobieństwach lub progach, aby pomóc w podejmowaniu decyzji podczas przechodzenia drzewa.

Oto link do dobrej książki na ten temat, zatytułowanej Wykrywanie błędów i diagnoza w systemach przemysłowych (strona 224), w której opisano zalety diagnostyki opartej na SDG:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

SDsolar
źródło