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

Материал из Википедии — свободной энциклопедии

граф с шестью вершинами и семью рёбрами

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

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

[править] Терминология теории графов

До настоящего времени терминология теории графов не определена совсем строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано «В программистском мире нет единого мнения о том, какой из двух терминов "граф" или "сеть". Мы выбрали термин "сеть", так как он, по-видимому, чаще встречается в прикладных областях»

[править] Некоторые задачи теории графов

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

[править] Применение теории графов

Теория графов в химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано, как задача теории графов)
Теория графов в информатике и программировании
Теория графов в экономике

[править] Литература

Оре О. Теория графов. — 2-е изд. — М.: Наука. Главная редакция физико-математической литературы, 1980, 336 с.
Харари Ф. Теория графов. — М.: Мир, 1973
Харари, Палмер. Теория графов. 1977
Зыков А.А. Основы теории графов. — М.: Наука. Главная редакция физико-математической литературы, 1987, 384 с.