Применение теории графов в информатике

11

Я студент CS. Мы делали теорию графов в одном курсе. Я нашел это интересным.

Каковы реальные применения теории графов в области компьютерных наук?

Например, я обнаружил, что некоторые понятия в теории графов могут использоваться для проектирования сетей. Какие есть другие похожие приложения?

nbro
источник
1
это может быть ужасно длинный список. Я думаю CW?
Суреш Венкат
4
Это кажется слишком общим даже для CW. Теория графов повсеместна в TCS.
Гек Беннетт
30
Спрос на темы в CS, которые не используют графики, мог бы привести к более короткому списку.
Рафаэль
1
@peedarpk: Если вы изучаете теорию графов в курсах CS, почему бы вам не спросить профессора?
Энтони Лабарр
3
Действительно, мы можем закрыть это сейчас? Ответ на этот вопрос находится в Википедии ( en.wikipedia.org/wiki/Graph_theory#Applications ) или в любом вводном учебнике для студентов.
RJK

Ответы:

12

Это ни в коем случае не является окончательным ответом, и я не намерен это делать как таковой.

Многие проблемы, представляющие интерес для компьютерных ученых, могут быть сформулированы как проблемы графов, и в результате теория графов обнаруживает довольно много в теории сложности. Например, вычислительные усилия, необходимые для определения изоморфности двух графов, в настоящее время представляют большой интерес для теории сложности (известно, что она не является NP-полной и не содержится в P, BPP или BQP, но явно в NP) , С другой стороны, неизоморфизм графов имеет очень хорошее доказательство с нулевым знанием (еще одна область исследования в теории сложности). Многие классы сложности имеют проблемы с графами, которые являются полными для этого класса (при некотором сокращении).

Однако не только теория сложности использует теорию графов. Как видно из некоторых других ответов, существует целый ряд проблем, для которых язык теории графов является наиболее подходящим. Существует много приложений, которые могут предоставить дифференциальный список, поэтому вместо этого я оставлю вам пример того, как теория графов играет фундаментальную роль в моей области исследований.

Квантовые вычисления на основе измерений - это модель вычислений, которая не имеет аналогов в классическом мире. В этой модели вычисление осуществляется путем проведения измерений на специальном классе квантовых состояний. Эти состояния известны как состояния графа, потому что каждое состояние может быть однозначно идентифицировано неориентированным графом с числом вершин, равным количеству кубитов в состоянии графа. Однако эта связь с теорией графов более чем случайна. Мы знаем, что важный класс измерений (измерения на основе Паули, если вас это интересует) отображает основное состояние графа в новое состояние графа на одном меньшем кубите, и правила, по которым это происходит, хорошо понятны. Кроме того, свойства базового семейства графов (это поток и g-поток) полностью определили, поддерживает ли он универсальные вычисления. И, наконец, для любого графа G ', который может быть достигнут из другого графа G произвольной последовательностью дополнения ребер окрестности вершины, может быть достигнут только однокбитными операциями, и поэтому они одинаково мощны в качестве ресурса для вычислений. Это интересно, потому что число ребер, максимум степеней вершин и т. Д. Может сильно измениться.

Джо Фицсимонс
источник
Отличный ответ на то, о чем вряд ли спрашивал ОП! Но, тем не менее, почему бы нам не забыть оригинальную (плохую) версию вопроса и притвориться, что мы играем в «Опасность»: «Какова интуиция за повсеместным распространением графов почти во всех дисциплинах теоретической информатики?»
RJK
@RJK: Возможно, мне следовало бы прочитать вопрос более внимательно, но я подумал, что это может быть по крайней мере интересно человеку, задающему вопрос.
Джо Фицсимонс
Нет-нет, это был отличный ответ.
Montagist
5

Приложения теории графов широко распространены в информатике и повседневной жизни:

  • Нахождение кратчайших маршрутов в автомобильных навигационных системах
  • Поисковые системы используют алгоритмы ранжирования, основанные на теории графов
  • Оптимизация расписания для школ или университетов
  • Анализ социальных сетей
  • Оптимизация использования железнодорожных систем
  • Компиляторы используют алгоритмы раскраски для назначения регистров переменным
  • Планирование пути в робототехнике
Фолькер Турау
источник
3

Теория графов имеет множество применений. Мои любимые приложения в:

  • Крупные сети
  • Социальные вычисления
  • Биоинформатики
Нихилу
источник
2

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

  • гиперграфы
  • полные графики
  • звездные графики
  • сетки

Когда вы моделируете сети с использованием графов, вы можете использовать всю мощь теории графов для анализа сети.

Это всего лишь одно из многих применений теории графов в информатике.

Gprime
источник
-2

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

Geetanjali
источник