Badania w teorii grafów a algorytmy grafowe

12

Mam bardzo ogólne pytanie. Jest to związane z badaniami. Interesuje mnie teoria grafów. Zrobiłem w tym kurs. Zrobiłem kilka tematów związanych z teorią grafów z punktu widzenia robienia tego jako student matematyki, a także studiowałem niektóre algorytmy grafów. Idę na staż badawczy z teorii grafów. Ale w mojej głowie jest pewna usterka, której nie jestem w stanie naprawić w kwestii mojego prawdziwego zainteresowania grafami z powodu braku właściwych, odrębnych pomysłów na temat prawdziwej różnicy w prowadzeniu badań w algorytmie graficznym lub teorii grafów jako student matematyki . Chciałbym wiedzieć następujące rzeczy:

  1. Jaka jest prawdziwa różnica w robieniu teorii grafów jako student matematyki lub w algorytmach graficznych? Czy oba mają jakąś prawdziwą różnicę?
  2. Czy ktoś może mi powiedzieć dobre źródło informacji na temat teorii grafów i algorytmów grafowych.
  3. Czy dobrze jest zacząć robić wykresy jako student matematyki?

Nie wiem, czy jest to właściwe miejsce do zgłaszania tego rodzaju problemów. Daj mi znać, jeśli tutaj nie pasuje.

graph-theory graphs legendarny zabójca
źródło
wiele nakładających się i zazębiających się przez cały czas np. z dużymi danymi i nie musi to być ani „albo”, ani „. algorytmy grafowe są zwykle bardziej stosowane / praktyczne, teoria grafów jest bardziej teoretyczna. teoria grafów dotyczy bardziej właściwości / dowodzenia twierdzeń ... to jak pytanie o różnicę między CS / matematyką ... do czego bardziej ci się podoba? Inną kwestią jest to, że niektóre teorie grafów są teoretycznie istotne, ale niepraktyczne lub „niekonstruktywne” i nie można ich używać w algorytmach lub jest to otwarte pytanie, czy istnieją jakieś algorytmy ... również zgrabnym obszarem silnego nakładania się jest „złożoność grafów” ...
vzn

Odpowiedzi:

9

Pytanie 1

Powiedziałbym, że oba obszary zdecydowanie nie są identyczne, jednak nakładają się na siebie. Częściowo zależy to od tego, gdzie narysujesz bardzo rozmyte linie. Zacznijmy:

  • Teoria grafów dotyczy właściwości grafów jako obiektów matematycznych
  • Algorytmy grafowe jako obszar badań dotyczą rozwiązywania problemów obliczeniowych reprezentowanych za pomocą grafów.

Oczywiście teoria grafów jest zaskakująco bardzo przydatna w opracowywaniu algorytmów graficznych, a algorytmy graficzne mogą odpowiadać na pytania w teorii grafowej. Rzeczywiście, jak wyraźnie zauważyłeś, wiele problemów w teorii grafów można rozpatrywać jako problemy obliczeniowe, na które można odpowiedzieć, podając algorytm (w pewnym sensie jest to aspekt korespondencji Curry-Howarda ), szczególnie na poziomie wprowadzającym to niewiele więcej niż styl prezentacji, który je dzieli.

Aby jeszcze bardziej skomplikować sytuację, większość badaczy w jednej dziedzinie ma przynajmniej pewne zainteresowanie i doświadczenie w drugiej, ale istnieje kilka punktów, w których możemy wytyczyć pewne linie rozróżnienia:

  • Teoria grafów (jako pole) chętnie poradzi sobie z grafami nieskończonymi, które nie są tak interesujące z punktu widzenia algorytmu.
  • Teoretycy grafów będą bardziej zainteresowani stwierdzeniami egzystencjalnymi („liczba chromatyczna klasy grafów to co najwyżej bla”), podczas gdy algorytmy grafowe będą poszukiwać najlepszego algorytmu do rozwiązania problemu („jak obliczyć rzeczywista wartość liczby chromatycznej tak szybko, jak to możliwe? ”).
  • Algorytmy grafów obejmują / pokrywają się z zastosowaniem i dostosowywaniem algorytmów graficznych do rozwiązywania problemów, które tak naprawdę nie dotyczą grafów (np. Opracowanie dobrego algorytmu do klastrowania sieci interakcji białek), w które teoretyk grafów byłby niezainteresowany (przynajmniej jako wykres teoretyk).

pytanie 2

Jeśli masz dostęp do subskrypcji uniwersytetów lub podobnych (nie jest to w żaden sposób wyczerpujące):

Co więcej, wiele z nich zawiera przykłady zarówno teorii czystego grafu, jak i algorytmów grafowych.

Kilka list do dalszej eksploracji:

Istnieje serwer preprint arXiv , który ma wersje przedruków artykułów naukowych, ale znowu będziesz musiał poświęcić trochę czasu na zbadanie i znalezienie czegoś, czego chcesz (jest bardziej skonfigurowany do znalezienia papieru, który już wiesz, że tam jest) ).

pytanie 3

Na to pytanie nie można tak naprawdę odpowiedzieć obiektywnie. Zależy to całkowicie od rzeczy, których nie masz możliwości poznać (tj. Przyszłości), a ja nie mam możliwości poznania (jak dobrzy są ludzie na twoim uniwersytecie, jakie szanse zyskasz lub stracisz dzięki odbyciu stażu).

Jeśli chcesz mojej subiektywnej ogólnej opinii, powiedziałbym tak. Teoria grafów jest ważną częścią matematyki i informatyki (osobiście uważam, że i tak nie są to różne rzeczy), a wszechstronność i ogrom wiedzy są ważnymi cechami dobrego badacza, nawet jeśli później zdecydujesz, że nie masz zamiaru być teoretyk grafów - nie powstrzyma cię to od możliwości przeprowadzenia złożonej analizy lub topologii.

Ponownie chodzi o to, czy dowolny uczeń skorzystałby na pracy na grafach (algorytmach lub teorii) - osobiście możesz być w szczególnej sytuacji, w której nie byłoby to korzystne, i nie możemy na to odpowiedzieć tutaj. Na przykład, jeśli odbycie stażu oznacza, że ​​nie dostaniesz stażu w teorii kategorii, który jest właściwie tym, co chcesz zrobić, może to cię cofnąć. Na początku kariery naukowej trudno jest uciec od określonej ścieżki, nie wracając do kroku pierwszego. Później łatwiej jest przejść, ale na lepsze lub gorsze jest okres, taki jak staż, w którym nie można łatwo przejść do pracy, którą jesteś zainteresowany, ale to jest pytanie do Academia.SE.

Luke Mathieson
źródło
„Algorytmy grafowe jako obszar badań dotyczą rozwiązywania problemów obliczeniowych reprezentowanych za pomocą grafów”. Lub po prostu problemy obliczeniowe na wykresach. Wykres nie musi reprezentować niczego, aby algorytmy mogły się na nim liczyć jako algorytmy grafowe.
David Richerby,