Теория графов

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

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

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

Некоторые задачи теории графов

  • Семь мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.
  • Теорема о четырёх красках — была сформулирована в 1852, но доказательство получено лишь в 1976.
  • Задача коммивояжёра — одна из наиболее известных NP-полных задач.
  • Задача о клике — ещё одна NP-полная задача.
  • Нахождение минимального стягивающего дерева.

См. также

Популярные программы для визуализации графов

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home