Исследования в теории графов против алгоритмов графов

У меня есть очень общий вопрос. Это связано с исследованиями. Я интересуюсь теорией графов. Я прошел курс в этом. Я рассмотрел некоторые темы, связанные с теорией графов, с точки зрения того, чтобы изучать математику, а также изучил некоторые алгоритмы графов. Я собираюсь пройти стажировку в области теории графов. Но в моем уме есть некоторый сбой, который я не могу исправить из-за моего реального интереса к графам из-за отсутствия надлежащих отличительных представлений о реальной разнице в проведении исследований в алгоритме графов или в теории графов в качестве студента-математика . Я хотел бы знать следующие вещи:

1. Какая реальная разница в занятиях теорией графов в математике или в алгоритмах графов? У них обоих есть какая-то реальная разница?
2. Может кто-нибудь сказать мне хороший источник для получения научных работ по теории графов и алгоритмов графов.
3. Это хорошо, чтобы начать делать графики, как студент математики?

Я не знаю, правильное ли это место, чтобы выдвигать такие проблемы. Пожалуйста, дайте мне знать, если это не подходит здесь.

Вопрос 1

Я бы сказал, что эти две области определенно не идентичны, однако существует огромное совпадение. Отчасти это зависит от того, где вы рисуете очень размытые линии. Давайте начнем с:

• Теория графов о свойствах графов как математических объектов
• График Алгоритмы как область исследования о решении вычислительных задач, которые представлены с помощью графов.

Конечно, теория графов, что неудивительно, очень полезна при разработке алгоритмов графов, и алгоритмы графов могут отвечать на вопросы теории графов. Действительно, как вы, очевидно, заметили, многие проблемы в теории графов могут быть представлены как вычислительные проблемы, и на них можно дать ответ, предложив алгоритм (в некотором смысле это аспект соответствия Карри-Ховарда ), поэтому, особенно на начальном уровне, существует немного больше, чем стиль представления, который разделяет их.

Просто чтобы сделать вещи еще более запутанными, большинство исследователей в одной области имеют по крайней мере некоторый интерес и опыт в другой, но есть пара моментов, в которых мы можем провести определенные линии различия:

• Теория графов (как поле) будет успешно иметь дело с бесконечными графами, которые не так интересны с алгоритмической точки зрения.
• Теоретики графов будут больше интересоваться экзистенциальными утверждениями («хроматическое число класса графов - самое большее»), тогда как алгоритмы графов люди будут искать лучший алгоритм для решения проблемы («как мы вычисляем фактическое значение хроматического числа как можно быстрее? ").
• Алгоритмы графов включают / пересекаются с применением и адаптацией алгоритмов графов для решения задач, которые на самом деле не относятся к графам (например, разработка хорошего алгоритма для кластеризации сетей взаимодействия белков), который теоретик графов не заинтересовал бы (по крайней мере, в виде графов). теоретик).

вопрос 2

Если у вас есть доступ к университетским подпискам или аналогичным (это не является исчерпывающим):

• Журнал теории графов
• Журнал SIAM по дискретной математике
• Журнал комбинаторной теории: серия B
• Дискретная прикладная математика
• Журнал графовых алгоритмов и приложений

Более того, многие из них включают примеры как чистой теории графов, так и алгоритмов графов.

Пара списков для дальнейшего изучения:

• Список журналов по теории графов
• По несвязанным причинам у Джона Лампа есть несколько списков, в которых есть интересные журналы, но вам придется поискать по ключевым словам: чистая математика , прикладная математика , теоретическая информатика

Существует сервер препринтов arXiv , который имеет препринтные версии исследовательских работ, но опять же, вам придется потратить небольшое количество времени, чтобы исследовать и найти то, что вы хотите (он больше настроен на поиск бумаги, о которой вы уже знаете, там). ).

Вопрос 3

На этот вопрос нельзя дать объективный ответ. Это полностью зависит от того, что у вас нет возможности узнать (например, будущее), и я не могу узнать (насколько хороши люди в вашем университете, какие возможности вы получите или потеряете, пройдя эту стажировку).

Если вы хотите мое субъективное общее мнение, я бы сказал, да. Теория графов - важная часть математики и информатики (я лично утверждаю, что они в любом случае не разные вещи), а универсальность и широта знаний являются важными характеристиками хорошего исследователя, даже если впоследствии вы решите, что не собираетесь быть Теоретик графов - это не остановит вас от возможности выполнять сложный анализ или топологию.

Опять же, речь идет о том, получит ли произвольный студент пользу от работы с графиками (алгоритмами или теорией) - вы лично можете оказаться в конкретной ситуации, когда это не будет выгодно, и мы не можем ответить на этот вопрос здесь. Например, если прохождение стажировки означает, что вы не можете пройти стажировку в теории категорий, а это именно то, чем вы хотите заниматься, то это может вас отбросить. В начале научной карьеры трудно избежать определенного пути, не возвращаясь к первому шагу. Позже переход легче, но, к лучшему или к худшему, есть период, подобный ученичеству, когда вы не можете легко перейти на любую интересующую вас работу, но это вопрос для Academia.SE.