Forschung in der Graphentheorie versus Graphalgorithmen

12

Ich habe eine sehr allgemeine Frage zu stellen. Es hängt mit der Forschung zusammen. Ich interessiere mich für Graphentheorie. Ich habe einen Kurs darin gemacht. Ich habe einige Themen im Zusammenhang mit der Graphentheorie aus der Sicht eines Mathematikstudenten behandelt und auch einige Graphalgorithmen studiert. Ich mache ein Forschungspraktikum in Graphentheorie. Aber ich habe ein Problem in meinem Kopf, das ich nicht lösen kann, weil ich keine genauen Vorstellungen über den Unterschied habe, den ich als Mathematikstudent bei der Erforschung von Graph-Algorithmen oder bei der Graphentheorie habe . Ich möchte folgende Dinge wissen:

  1. Was ist der wirkliche Unterschied, wenn man als Mathematikstudent Graphentheorie oder Graphalgorithmen macht? Haben beide einen echten Unterschied?
  2. Kann mir jemand eine gute Quelle für Forschungsarbeiten zur Graphentheorie und zu Graphalgorithmen nennen?
  3. Ist es gut, als Mathematikstudent mit dem Zeichnen zu beginnen?

Ich weiß nicht, ob es der richtige Ort ist, solche Probleme vorzubringen. Bitte lassen Sie mich wissen, wenn es hier nicht passt.

Legendenkiller
quelle
Viele Überlappungen und eine immer stärkere Verzahnung mit z. B. Big Data. Es muss kein "Entweder-Oder" sein. Graph-Algorithmen werden in der Regel eher angewendet / praktikabel, die Graphentheorie eher theoretisch. In der Graphentheorie geht es mehr um Eigenschaften / Beweistheoreme ... es ist, als würde man den Unterschied zwischen CS / Mathe fragen ... zu welchem ​​haben Sie eine größere Affinität? Ein weiterer Punkt ist , dass einige die Graphentheorie theoretisch bedeutsam ist noch nicht praktikabel oder „ relativ schlechte“ und kann nicht für Algorithmen verwendet werden , oder ist eine offene Frage , ob irgendwelche Algorithmen existieren ... auch eine saubere Fläche von starken Überlappung „Graph Komplexität“ ...
vzn

Antworten:

9

Frage 1

Ich würde sagen, dass die beiden Bereiche definitiv nicht identisch sind, es jedoch eine enorme Überschneidung gibt. Zum Teil hängt es davon ab, wo Sie einige sehr unscharfe Linien zeichnen. Lass uns beginnen mit:

  • In der Graphentheorie geht es um die Eigenschaften von Graphen als mathematische Objekte
  • Graph-Algorithmen als Forschungsgebiet befassen sich mit der Lösung von Rechenproblemen , die mithilfe von Graphen dargestellt werden.

Natürlich ist die Graphentheorie bei der Entwicklung von Graph-Algorithmen nicht überraschend nützlich, und Graph-Algorithmen können Fragen in der Graphentheorie beantworten. Wie Sie offensichtlich bemerkt haben, können viele Probleme in der Graphentheorie als Rechenprobleme gewertet und durch Angabe eines Algorithmus (in gewissem Sinne ist dies ein Aspekt der Curry-Howard-Korrespondenz ) beantwortet werden , insbesondere auf der Einführungsebene ist wenig mehr als der Präsentationsstil, der sie voneinander trennt.

Um die Sache noch verwirrender zu machen, haben die meisten Forscher in einem Bereich zumindest ein gewisses Interesse und Erfahrung in dem anderen, aber es gibt einige Punkte, an denen wir bestimmte Unterscheidungslinien ziehen können:

  • Die Graphentheorie (als Feld) wird sich gerne mit unendlichen Graphen befassen, die aus algorithmischer Sicht nicht so interessant sind.
  • Graphentheoretiker sind tendenziell mehr an existenziellen Aussagen interessiert ("die chromatische Zahl einer Klasse von Graphen ist höchstens blah"), wohingegen Graphalgorithmen nach dem besten Algorithmus suchen, um ein Problem zu lösen ("wie berechnen wir die Istwert der chromatischen Zahl so schnell wie möglich? ").
  • Graph-Algorithmen umfassen / überschneiden sich mit der Anwendung und Anpassung von Graph-Algorithmen, um Probleme zu lösen, bei denen es nicht wirklich um Graphen geht (z. B. die Entwicklung eines guten Algorithmus für Cluster-Protein-Interaktionsnetzwerke), an denen ein Graph-Theoretiker (zumindest als Graph) nicht interessiert wäre Theoretiker).

Frage 2

Wenn Sie Zugriff auf Universitätsabonnements oder ähnliches haben (dies ist keineswegs vollständig):

Um die Sache noch schlimmer zu machen, enthalten viele Beispiele sowohl für reine Graphentheorie als auch für Graphalgorithmen.

Einige Listen zur weiteren Erkundung:

Es gibt den arXiv-Preprint-Server , der über Preprint-Versionen von Forschungsberichten verfügt. Aber auch hier müssen Sie ein wenig Zeit aufwenden, um nach gewünschten Informationen zu suchen (es ist eher darauf ausgelegt, ein Papier zu finden, von dem Sie bereits wissen, dass es vorhanden ist ).

Frage 3

Diese Frage kann nicht wirklich objektiv beantwortet werden. Es hängt ganz von Dingen ab, die Sie nicht kennen (dh die Zukunft), und ich habe keine Möglichkeit zu wissen (wie gut die Leute an Ihrer Universität sind, welche Chancen Sie durch das Praktikum gewinnen oder verlieren).

Wenn Sie meine subjektive allgemeine Meinung wollen, würde ich ja sagen. Die Graphentheorie ist ein wichtiger Teil der Mathematik und der Informatik (ich persönlich behaupte, sie sind sowieso keine unterschiedlichen Dinge), und Vielseitigkeit und Wissensbreite sind wichtige Merkmale eines guten Forschers, auch wenn Sie später entscheiden, dass Sie nicht die Absicht haben, eine zu sein Graphentheoretiker - es hindert Sie nicht daran, komplexe Analysen oder Topologien durchzuführen.

Auch hier geht es darum, ob ein beliebiger Schüler von der Arbeit in Diagrammen (Algorithmen oder Theorie) profitieren würde - Sie befinden sich möglicherweise in einer bestimmten Situation, in der dies nicht vorteilhaft wäre, und wir können dies hier nicht beantworten. Wenn zum Beispiel das Praktikum bedeutet, dass Sie nicht das Praktikum in der Kategorietheorie absolvieren können, das eigentlich das ist, was Sie tun möchten, kann dies Sie zurückwerfen. Zu Beginn einer Forschungskarriere ist es schwierig, einem bestimmten Pfad zu entkommen, ohne zu Schritt eins zurückzukehren. Später ist der Übergang einfacher, aber es gibt eine Zeit wie eine Lehre, in der Sie nicht einfach zu einem Job wechseln können, an dem Sie interessiert sind, aber das ist eine Frage für Academia.SE.

Luke Mathieson
quelle
"Graph-Algorithmen sind ein Forschungsgebiet, in dem es darum geht, Rechenprobleme zu lösen, die mithilfe von Graphen dargestellt werden." Oder einfach nur Rechenprobleme in Diagrammen. Der Graph muss nichts darstellen, damit Algorithmen als Graph-Algorithmen gelten.
David Richerby