Zastosowanie teorii grafów w informatyce

11

Jestem studentką CS. Zrobiliśmy teorię grafów w jednym kursie. Uważam to za interesujące.

Jakie są prawdziwe zastosowania teorii grafów w dziedzinie informatyki?

Na przykład odkryłem, że niektóre koncepcje teorii grafów można wykorzystać do projektowania sieci. Jakie są inne podobne aplikacje?

nbro
źródło
1
może to być bardzo długa lista. Myślę o CW?
Suresh Venkat
4
To wydaje się trochę zbyt ogólne, nawet jak na CW. Teoria grafów jest wszechobecna w TCS.
Huck Bennett
30
Pytanie o tematy w CS, które nie używają wykresów, mogło dać krótszą listę.
Raphael
1
@peedarpk: Jeśli śledzisz zajęcia z teorii grafów w kursie CS, dlaczego nie zapytasz profesora?
Anthony Labarre
3
Naprawdę, możemy to teraz zamknąć? Odpowiedź na to pytanie znajduje się na wikipedii ( en.wikipedia.org/wiki/Graph_theory#Applications ) lub w dowolnym wprowadzającym podręczniku dla studentów.
RJK

Odpowiedzi:

12

To nie jest w żaden sposób ostateczna odpowiedź i nie zamierzam jej jako takiej.

Wiele problemów interesujących informatyków można sformułować jako problemy związane z grafem, w wyniku czego teoria grafów bardzo często pojawia się w teorii złożoności. Na przykład wysiłek obliczeniowy niezbędny do ustalenia, gdzie dwa wykresy są izomorficzne, jest obecnie przedmiotem dużego zainteresowania teorią złożoności (nie wiadomo, że jest NP-kompletny ani nie zawiera P, BPP lub BQP, ale jest wyraźnie w NP) . Z drugiej strony wykres nieizomorfizm ma bardzo ładny dowód zerowej wiedzy (kolejny obszar badań w teorii złożoności). Wiele klas złożoności ma problemy z grafem, które są kompletne dla tej klasy (z pewną redukcją).

Jednak nie tylko teoria złożoności korzysta z teorii grafów. Jak widać z niektórych innych odpowiedzi, istnieje szereg problemów, dla których język teorii grafów jest najbardziej odpowiedni. Istnieje zbyt wiele aplikacji, aby przedstawić listę niejednoznaczną, dlatego zostawię wam przykład, jak teoria grafów odgrywa fundamentalną rolę w moim własnym obszarze badań.

Obliczenia kwantowe oparte na pomiarach to model obliczeń, który nie ma odpowiednika w klasycznym świecie. W tym modelu obliczenia oparte są na pomiarach specjalnej klasy stanów kwantowych. Stany te są znane jako stany wykresów, ponieważ każdy stan można jednoznacznie zidentyfikować za pomocą niekierowanego wykresu z liczbą wierzchołków równą liczbie kubitów w stanie wykresu. Ten związek z teorią grafów jest jednak więcej niż przypadkowy. Wiemy, że ważna klasa pomiarów (pomiary oparte na Pauli, jeśli jesteś zainteresowany) odwzorowuje podstawowy stan wykresu na nowy stan wykresu na jednym kubicie mniejszym, a zasady, według których ma to miejsce, są dobrze zrozumiane. Ponadto właściwości podstawowej rodziny grafów (jej przepływ i przepływ g) w pełni określiły, czy obsługuje on uniwersalne obliczenia. W końcu, dla każdego wykresu G ', który można uzyskać z innego wykresu G przez dowolną sekwencję uzupełniania krawędzi sąsiedztwa wierzchołka, można osiągnąć tylko przez operacje pojedynczej kubitów, a zatem są równie potężne jak zasób do obliczeń. Jest to interesujące, ponieważ liczba krawędzi, maksimum stopni wierzchołków itp. Może się drastycznie zmienić.

Joe Fitzsimons
źródło
Świetna odpowiedź na to, o co OP prawdopodobnie nie pytał! Ale ogólnie rzecz biorąc, dlaczego nie zapomnimy oryginalnej (złej) wersji pytania i udajemy, że gramy w Jeopardy: „Jaka intuicja kryje się za wszechobecnością grafów w prawie wszystkich poddyscyplinach teoretycznej informatyki?”.
RJK
@RJK: Być może powinienem był przeczytać to pytanie dokładniej, ale pomyślałem, że może to być interesujące dla osoby zadającej pytanie.
Joe Fitzsimons,
Nie nie, to była świetna odpowiedź.
Montagist
5

Zastosowania teorii grafów są liczne w informatyce i na co dzień:

  • Znajdowanie najkrótszych tras w samochodowych systemach nawigacyjnych
  • Wyszukiwarki używają algorytmów rankingowych opartych na teorii grafów
  • Optymalizacja harmonogramów dla szkół lub uniwersytetów
  • Analiza sieci społecznościowych
  • Optymalizacja wykorzystania systemów kolejowych
  • Kompilatory używają algorytmów kolorowania do przypisywania rejestrów do zmiennych
  • Planowanie ścieżek w robotyce
Volker Turau
źródło
3

Teoria grafów ma wiele zastosowań. Moje ulubione to aplikacje w:

  • Sieci o dużej skali
  • Komputery społecznościowe
  • Bioinformatyka
Nikhil
źródło
2

Modelowanie sieci odbywa się za pomocą grafów. Na przykład, jeśli chcesz studiować transmisję lub multiemisję w niektórych typach topologii sieci, możesz użyć wykresów do modelowania sieci. Na przykład:

  • hipergrrafy
  • pełne wykresy
  • wykresy gwiazdowe
  • oczka

Kiedy modelujesz sieci za pomocą grafów, możesz wykorzystać całą moc teorii grafów do analizy sieci.

To tylko jeden z wielu zastosowań teorii grafów w informatyce.

gprime
źródło
-2

Struktura katalogów jest strukturą drzewiastą (z węzłami głównymi i potomnymi. W sieci służy do znajdowania najkrótszej trasy przy użyciu minimalnego drzewa opinającego, algorytmu Dijkstry.

Geetanjali
źródło