Теория графов
Материал из Википедии — свободной энциклопедии
Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G={R,V}, где V есть подмножество любого счётного множества, а R — подмножество V×V.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередач и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока недоказанных гипотез.
Содержание |
[править] История возникновения теории графов
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
[править] Терминология теории графов
Терминология теории графов поныне не определена строго. В частности в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин „сеть“, так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация для «вершина/точка»
[править] Изображение графов на плоскости
При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.
Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет. В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
[править] Некоторые задачи теории графов
- Семь мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.
- Проблема четырёх красок — была сформулирована в 1852 году, но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).
- Задача коммивояжёра — одна из наиболее известных NP-полных задач.
- Задача о клике — ещё одна NP-полная задача.
- Нахождение минимального стягивающего дерева.
К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
[править] Применение теории графов
- В химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
- В информатике и программировании
- В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
- В экономике
- В логистике
- В схемотехнике
[править] Литература
- Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
- Берж К. Теория графов и ее приложения. М.: ИЛ, 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
- Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд.. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1
- Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336.
- Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997. — ISBN 5-02-015033-9
- Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
- Diestel R. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005. — С. 422.
[править] См. также
[править] Ссылки
- Толковый словарь по теории графов
- Лекции 5 и 6 «Алгоритмы на графах» вводного курса «Информатика»
- Алгоритмы и краткие описания и программ на C++
- Дискретная математика, алгоритмы, апплеты, визулизация графов
- Графы в химии
- Программа для работы с графами
