Теория графов
Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств , где есть подмножество любого счётного множества, а — подмножество .
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
История возникновения теории графов[править | править код]
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature[1].
Терминология теории графов[править | править код]
Терминология теории графов поныне не определена строго. В частности, в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация с терминами «вершина/точка».
Виды графов:
- неориентированный (неорграф)
- ориентированный (орграф)
Изображение графов на плоскости[править | править код]
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф — это граф, который можно изобразить на рисунке (плоскости) без пересечения рёбер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих рёбер и содержит одну корневую вершину, в которую нет входящего ребра.
Не следует путать изображение графа собственно с графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
Некоторые задачи теории графов[править | править код]
- Проблема семи мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.
- Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).
- Задача коммивояжёра — одна из наиболее известных NP-полных задач.
- Задача о клике — ещё одна NP-полная задача.
- Нахождение минимального стягивающего (остовного) дерева.
- Изоморфизм графов — можно ли путём перенумерации вершин одного графа получить другой.
- Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).
К теории графов также относится целый ряд математических проблем, не решённых на сегодняшний день.
Применение теории графов[править | править код]
- В химии (для описания структур, путей сложных реакций[2], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров углеводородов и других органических соединений.
- В информатике и программировании (граф-схема алгоритма, автоматы)[3]
- В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
- В экономике[4]
- В логистике
- В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф)[5].
См. также[править | править код]
Примечания[править | править код]
- ↑ Sylvester, James Joseph. Chemistry and Algebra (англ.) // Nature. — 1878. — Vol. 17, no. 432. — P. 284. — doi:10.1038/017284a0. — .
- ↑ Г. С. Яблонский, В. И. Быков, А. Н. Горбань, Кинетические модели каталитических реакций, Новосибирск: Наука (Сиб. отделение), 1983.- 255 c.
- ↑ Евстигнеев В.А. Применение теории графов в программировании. - М., Наука, 1985. - Тираж 20000 экз. - 352 c.
- ↑ Ерёменко А. О. Использование теории графов при решении задач в экономике // Прогрессивные технологии и экономика в машиностроении : сборник трудов VII Всероссийской научно-практической конференции для студентов и учащейся молодежи, г. Юрга, 7-9 апреля 2016 г. : в 2 т. — Томск : Изд-во ТПУ. — 2016. — Т. 2. — С. 279—281.
- ↑ Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
Литература[править | править код]
- Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X.
- Diestel R. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005. — С. 422.
- Басакер Р., Саати Т. Конечные графы и сети = Finite Graphs and Networks. — М.: Наука, 1974. — 368 c.
- Белов В. В., Воробьёв Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976. — С. 392.
- Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
- Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
- Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664. — ISBN 5-9502-0057-8.(М.: Наука, 1987. 383c.)
- Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.
- Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
- Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.
- Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1.
- Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336.
- Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9.
- Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
- Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.
- Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.
- Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
- Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
- Сергей Мельников. Сим и Крэм под «электронным микроскопом» (рус.) // Наука и жизнь. — 1996. — Вып. 3. — С. 144—145. В статье идёт речь об игре на графе Сим, придуманной Густавом Симмонсом.
Ссылки[править | править код]
- WikiGrapp — толковый словарь по теории графов
- Алгоритмы и краткие описания программ на C++
- Дискретная математика, алгоритмы, апплеты, визуализация графов
- Intelligent Graph Visualizer (автоматическое размещение на плоскости, поиск кратчайшего пути, поиск центра и др.)
- Graph Theory Software
- Visual Graph: программа, предоставляющая пользователю, широкий набор средств и методов для визуализации и поиска информации в графах
Некоторые внешние ссылки в этой статье ведут на сайты, занесённые в спам-лист. |