Jakie są wykresy w kategoriach laików?

18

Co to są wykresy w informatyce i do czego służą? W kategoriach laików najlepiej.

Przeczytałem definicję na Wikipedii :

W informatyce wykres jest abstrakcyjnym typem danych, który ma zaimplementować pojęcia matematyczne oparte na grafie i hiperrafacie.

Struktura danych wykresu składa się ze skończonego (i prawdopodobnie zmiennego) zestawu uporządkowanych par, zwanych krawędziami lub łukami, pewnych bytów zwanych węzłami lub wierzchołkami. Podobnie jak w matematyce, krawędź (x, y) mówi się, że wskazuje lub przechodzi od x do y. Węzły mogą być częścią struktury grafu lub mogą być podmiotami zewnętrznymi reprezentowanymi przez indeksy lub odwołania całkowite.

ale szukam mniej formalnej, łatwiejszej do zrozumienia definicji.

ConditionRacer
źródło
Masz na myśli wykresy struktury danych?
System Down
1
Tak, przepraszam. Wykresy jak opisano tutaj en.wikipedia.org/wiki/Graph_(abstract_data_type) , tylko szukam mniej formalnej, łatwiejszej do zrozumienia definicji.
ConditionRacer
@ Justin984 Wikipedia linki z nawiasami (a jest ich tak wiele) nie działają, nawiasy nie działają dobrze w formacie Markdown dla linków. Teraz, w celu odniesienia w przyszłości, dodaj wyjaśnienia do pytania w samym pytaniu, a nie w komentarzach, nie są one tak widoczne i łatwo je przeoczyć. Zmienię twój powyższy komentarz w pytaniu ...
yannis,
@ Justin984 Należy również pamiętać, że Computer Science Stack Exchange może być nieco bardziej odpowiednie dla takich pytań jak programiści. Nie zrozumcie mnie źle, pytanie jest doskonale na ten temat i uzyskało świetne odpowiedzi, ale nie zaszkodziłoby, gdybyś sprawdził społeczność, która jest bardziej skupiona na podstawowych koncepcjach informatycznych niż my (nie rób tego opublikuj to samo pytanie w wielu witrynach, jeśli zdarzy się, że zamieścisz je na niewłaściwej stronie, możemy automatycznie przenieść je na właściwe).
yannis,

Odpowiedzi:

26

Doskonałym przykładem laika może być Facebook . Sieć twoich, twoich przyjaciół i ich przyjaciół itp. Jest wspólnie określana jako wykres społecznościowy .

Na tym „wykresie” ludzie są uważani za węzły wykresu, a krawędziełączami przyjaźni .

Na Facebooku przyjaciel jest dwukierunkowym związkiem (A jest przyjacielem B => B jest przyjacielem A), więc wykres jest wykresem niekierowanym . Sieć taka jak Google+ czy Twitter byłaby uważana za Graf Kierunkowy, ponieważ kierunek relacji ma tutaj znaczenie.

Wszystkie te wykresy są określane jako wykresy cykliczne , ponieważ relacje między węzłami mogą tworzyć cykle. Z kolei drzewo genealogiczne jest szczególnym rodzajem wykresu, który między innymi jest acykliczny, ponieważ w relacjach drzewa genealogicznego nie może być cykli. (Jest technicznie nazywany Directed Acyclic Graph (DAG), ponieważ jest zarówno ukierunkowany, jak i acykliczny)

Powinno to obejmować wszystkie podstawowe żargony obejmujące wykresy, więc teraz powinieneś być w stanie śledzić resztę materiału w terenie.

Karthik T.
źródło
1
Nie mogę uwierzyć, że nie przyszło mi do głowy, że nazywa się to graficznym interfejsem Facebooka. Dobry przykład!
ConditionRacer
4
Drzewo genealogiczne nie jest cykliczne? Nie powinno tak być, ale niestety jest ...
Marjan Venema
1
@MarjanVenema, drzewo genealogiczne jest cykliczne ? (Jest to ukierunkowany wykres, więc kierunek jest ważny przy określaniu cykli i przypuszczalnie związki krokowe tak naprawdę się nie liczą.)
huon
@dbaupp: Nie chcę tutaj wchodzić w szczegóły, więc wspomnę tylko jedno słowo: kazirodztwo.
Marjan Venema
5
@MarjanVenema, nie rozumiesz mnie. Cykl na ukierunkowanym wykresie to wzór podobny A -> B -> C -> A(tj. Koło strzałek), kazirodztwo po prostu daje A -> B -> Ci A -> D -> C(tj. Diament). Cykl w drzewie genealogicznym wymaga podróży w czasie.
huon
16

Wykresy są jedną z najważniejszych pojęć matematycznych stosowanych w informatyce.

Widziałeś wykresy wiele razy. Wyobraź sobie, że lecisz samolotem z jednego miasta do drugiego. Nieuchronnie znajdziesz ładny błyszczący magazyn od linii lotniczej w kieszeni przed sobą. Na końcu tego czasopisma prawie zawsze można znaleźć mapę przedstawiającą miasta obsługiwane przez tę linię lotniczą w postaci okręgów, a loty łączące te miasta są przedstawiane jako zakrzywione linie. To jest wykres! Miasta, reprezentowane jako koła, są węzłami tego wykresu, a loty, reprezentowane jako linie zakrzywione, są krawędziami. Wykresy to tylko rzeczy z węzłami i krawędziami, które łączą węzły.

Możesz upiększyć te proste wykresy na różne sposoby. Nie chcesz widzieć tylko kilku kółek i linii, patrząc na tę mapę. Te miasta mają nazwy. Oznaczenie tych miast wynikiem jest oznaczony wykres. (Można również oznaczyć krawędzie, np. Lot 1234.) Informatyka często kojarzy dane z węzłami, czasami z krawędziami, ale to tylko rozszerzenie etykiety. To wciąż jest oznaczony wykres. Kolejne upiększenie występuje, jeśli możesz lecieć bezpośrednio z miasta A do miasta B, ale nie z miasta B do miasta A. Oczywistym sposobem na przedstawienie tego jest umieszczenie strzałki na linii łączącej miasta, aby przedstawić tę relację jednokierunkową. Teraz masz ukierunkowany wykres.

Połączone listy, drzewa, diagramy zmian stanów i wiele innych struktur danych informatycznych to przykłady grafów. To bardzo potężna koncepcja.

David Hammen
źródło
Chciałbym rozszerzyć ten przykład, aby zauważyć, że wszystkie byty opisane w twoim przykładzie mogą być przedstawione jako wierzchołki na wykresie (miasto, samolot, czasopismo, mapa itp.), A sama mapa jest tylko jednym wierzchołkiem.
Demian Brecht
14

Lepszym pytaniem byłoby „Do czego nie używa się wykresów?”. Informatyka jest pod wieloma względami studium grafów.

Wykres, w kategoriach laików, to zbiór dowolnych obiektów abstrakcyjnych zwanych „węzłami” lub „wierzchołkami”, które reprezentują punkty połączenia. Są one następnie łączone za pomocą „ścieżek” lub „krawędzi”. Abstrakcyjny typ danych „Graph” jest implementacją matematycznego „Graph”. Zasadniczo masz więc węzły i krawędzie jako swoje pola i różne operacje, które możesz na nich wykonywać. Możesz na przykład dodać nowy węzeł do kolekcji wykresu (może to być lista, tablica lub inna struktura w zależności od języka). Następnie możesz połączyć ten węzeł z istniejącymi węzłami. Operacje obejmowałyby również przemierzanie wykresu, sprawdzanie, czy dwa węzły dzielą krawędź (są połączone), pobieranie wartości z węzłów lub krawędzi oraz usuwanie węzłów lub krawędzi z wykresu.

Jeśli chodzi o wykorzystanie, wykresy są używane w dowolnym miejscu. Networking wykorzystuje je szczególnie intensywnie, ale można je znaleźć w sztucznej inteligencji, eksploracji danych, tworzeniu gier, geoinformatyce i wielu innych dyscyplinach. W formalnej informatyce widzą jeszcze większe zastosowanie, a mianowicie sposób reprezentowania państwa.

W efekcie wszystko, co możesz reprezentować jako zestaw połączeń, może być reprezentowane jako wykres i zaimplementowane za pośrednictwem tego narzędzia ADT w jakiejś formie.

Oto przykładowa grafika, którą wykonałem:

Przykład wykresu

Inżynier świata
źródło
3

Wykres to tylko zbiór obiektów połączonych ze sobą liniami zwanymi wierzchołkami.

Termin „wykres” jest abstrakcją i uogólnieniem wielu struktur danych wykorzystywanych w tworzeniu oprogramowania. Połączone listy, drzewa binarne i AST to wykresy.

Zasadniczo każda kolekcja obiektów, która ma wskaźniki, które kojarzą te obiekty ze sobą, jest wykresem. Gdy masz już wykres, możesz zastosować do niego zasady teorii grafów , aby rozwiązać niektóre problemy .

Robert Harvey
źródło