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

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

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

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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

[править] История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

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

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

[править] Изображение графов на плоскости

При изображении графов чаще всего используется следующая система обозначений: каждой вершине сопоставляется точка на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками.

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

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

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

К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.

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

В химии (для описания структур, путей сложных реакций^[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия в сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
В информатике и программировании (граф-схема алгоритма)
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
В экономике
В логистике
В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф) ^[2].

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

Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. в М.: Высш. школа, 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.

Diestel R. Graph Theory, Electronic Edition. в NY: Springer-Verlag, 2005. в С. 422.

[править] Примечания

в‘ Г. С. Яблонский, В. И. Быков, А. Н. Горбань, Кинетические модели каталитических реакций, Новосибирск: Наука (Сиб. отделение), 1983.- 255 c.
в‘ Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

[править] См. также

[править] Ссылки

[0] в‘ Г. С. Яблонский, В. И. Быков, А. Н. Горбань, Кинетические модели каталитических реакций, Новосибирск: Наука (Сиб. отделение), 1983.- 255 c.

[1] в‘ Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

[1]

[2]

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

Содержание

[править] История возникновения теории графов

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

[править] Изображение графов на плоскости

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

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

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

[править] Примечания

[править] См. также

[править] Ссылки

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках