Теория графов
Теория графов — раздел дискретной математики, изучающий свойства
графов. В общем смысле граф представляется как множество вершин (узлов),
соединённых рёбрами. В строгом определении графом называется такая пара множеств
G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество
V?V.
Теория графов находит применение, например, в геоинформационных системах
(ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п.
рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии
электропередачи и т. п. — как рёбра. Применение различных вычислений,
производимых на таком графе, позволяет, например, найти кратчайший объездной
путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не
доказанных гипотез.
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из
своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских
мостах, ставшей впоследствии одной из классических задач теории графов.
Терминология теории графов поныне не определена строго. В частности в монографии
Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о
том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как
он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация
для «вершина/точка»
При изображении графов чаще всего используется следующая система обозначений:
каждой вершине сопоставляется точка на плоскости, и если между вершинами
существует ребро, то соответствующие точки соединяются отрезком. В случае
ориентированного графа отрезки заменяют стрелками.
Не следует путать изображение графа с собственно графом (абстрактной
структурой), поскольку одному графу можно сопоставить не одно графическое
представление. Изображение призвано лишь показать, какие пары вершин соединены
рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос,
являются ли два изображения моделями одного и того же графа или нет. В
зависимости от задачи, одни изображения могут давать более наглядную картину,
чем другие.
Некоторые задачи теории графов
•Семь мостов Кёнигсберга — один из первых результатов в теории графов,
опубликован Эйлером в 1736.
•Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое
доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на
сфере (плоскости).
•Задача коммивояжёра — одна из наиболее известных NP-полных задач.
•Задача о клике — ещё одна NP-полная задача.
•Нахождение минимального стягивающего (оставного) дерева.
•Изоморфизм графов — можно ли путем перенумерации вершин одного графа получить
другой или его часть.
•Планарность графа — можно ли изобразить граф на плоскости без пересечений ребер
(или с минимальным числом слоев, что находит применение при трассировке
межсоединений элементов печатных плат или микросхем).
К теории графов также относится целый ряд математических проблем, не решенных на
сегодняшний день.
Применение теории графов
•В химии (для описания структур, путей сложных реакций[1], правило фаз также
может быть интерпретировано как задача теории графов); компьютерная химия —
сравнительно молодая область химии, основанная на применении теории графов.
Теория графов представляет собой математическую основу хемоинформатики. Теория
графов позволяет точно определить число теоретически возможных изомеров у
углеводородов и других органических соединений.
•В информатике и программировании
•В коммуникационных и транспортных системах. В частности, для маршрутизации
данных в Интернете.
•В экономике
•В логистике
•В схемотехнике
2022 © kurs-dollar-euro.ru