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

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

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

Определение графу является настолько общим, что этим термином можно описывать множество событий и объектов повседневной жизни. Высокий уровень абстракции и обобщения позволяет использовать типовые алгоритмы теории графов для решения внешне непохожих задач в транспортных и компьютерных сетях, строительном проектировании, молекулярном моделировании т.д..

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

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

Формальное определение графа:

Пусть X = {x 1,..., x n} - некоторая конечное множество (множество вершин), M 2 - множество всех неупорядоченных пар элементов из X,

M 2 = {(x i, x j): x i ∈ X, x j ∈ X, i ≠ j}


1. Граф G (X, W) - пара множеств X, W ⊂ M 2. Множество X - множество вершин, множество W - это множество ребер. Если (x i, x j) ∈ W, то мы говорим, что ребро (x i, x j) соединяет вершину x i с вершиной x j; другая терминология - ребро (x i, x j) и вершины x i и x j инцидентны.

2. Граф G (X, W) называется полным, если W = M 2.

Если множество X содержит n вершин, то, очевидно, число ребер полного графа равна C n 2. Полный граф с n вершинами сказывается K n.

3. Граф G (X, W) называется пустым, если W = ∅.

4. Вершины x i и x j графа G (X, W) инцидентны, если (x i, x j) ∈ W.

5. Степень d (x i) вершины x i графа G (X, W) называется число вершин x j, которые инцидентны вершине x i (число отрезков, выходящих из вершины x i).

6. Если d (x i) = 1, то вершина x i называется конечной вершиной графа G (X, W). Если d (x i) = 0, то вершина x i называется изолированной.


1. История возникновения теории графов

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

Толчок к развитию теория графов получила на рубеже XIX и ХХ веков, когда резко возросло количество работ в области топологии и комбинаторики, с которыми ее связывают тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена ​​в работе венгерского математика Кенига в 30-е годы ХХ века.

Последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др.. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже является частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.


2. Алгоритмы на графах

  1. Поиск в глубину.
  2. Поиск в ширину.
  3. Топологическое сортировки.
  4. Фундаментальная множество циклов.
  5. Эйлеров цикл. Теорема Эйлера.
  6. Гамильтонов цикл.
  7. Алгоритм Беллмана - Форда.
  8. Алгоритм Дейкстры.
  9. Алгоритм Флойда-Уоршела.
  10. Транзитивное замыкание графа.
  11. Системы неперетинаючих множеств.
  12. Связность. Алгоритмы Прима и Крускала. Остовное дерево
  13. Коды Прюфера.
  14. Матричная формула Кирхгофа.
  15. Нахождение точек соединения и мостов в графе.
  16. Алгоритм Эдмондс-Карпа.
  17. Поиск максимального паросочетания.

3. Терминология теории графов

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

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

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

Лесом называется граф, не содержащий циклов. Связный лес называется деревом.

Плоским графом называется граф, в диаграмме которого линии, соответствующие ребрам, пересекаются в точках, соответствующих вершинам графа.

Планарным графом называется граф G, изоморфный некоторому плоском графу. Последний называется плоской картой графа G.

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

Множество всех граней плоского связного графа сказывается P. Замкнутый маршрут, ограничивающий грань, называется пределом грани, а длина этого маршрута - степенью грани. Степень грани сказывается Pr.

Максимальным планарным графом называется планарный граф, который при добавлении к нему любого ребра перестает быть планарным.

Плоский связный граф, каждая грань которого (включая внешнюю) ограничена треугольником, называется триангуляции.


4. Изображение графов на плоскости

При изображении графов чаще всего используется следующая система обозначений: каждая вершина изображается в виде точки на плоскости, и если между вершинами существует ребро, то соответствующие точки соединяются отрезком. В случае ориентированного графа отрезки заменяют стрелками или явно показывают направление ребра. Различают планарные и непланарни графы. Планарный граф - это граф, который можно изобразить на рисунке без пересечения ребер (простейшие - треугольник или пара связанных вершин), иначе - непланарний. В случае, когда граф не содержит циклов (путей однократного обхода ребер и вершин с возвращением в исходную точку), его принято называть "деревом". Важные виды деревьев в теории графов - бинарные деревья, где каждая вершина имеет одно входное ребро и ровно два выходных, или является конечной - не имеет выходных ребер.

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


5. Некоторые задачи теории графов

? Проблема семи мостов Кенигсберга - один из первых результатов в теории графов, опубликован Эйлером в 1736.

? Проблема четырех красок - была сформулирована в 1852, но неклассическое доказательство получено лишь в 1976 (достаточно 4-х красок для карты на сфере (плоскости).

? Задача коммивояжера - одна из наиболее известных NP-полных задач.

? Задача о клик - еще одна NP-полная задача.

? Нахождение минимального стягивающего (остовного) дерева.

? Изоморфизм графов - можно путем перенумерации вершин одного графа получить другой.

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

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


6. Применение теории графов

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

? В информатике и программировании (граф-схема алгоритма)

? В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

? В экономике

? В логистике

? В схемотехнике (топология мижзьеднання элементов на печатной плате или микросхеме представляет собой граф или гиперграфа).


Литература

? Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.

? Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов - М.: Высшее. школа, 1976. - С. 392.

? Берж К. Теория графов и ее применения. М.: ИЛ, 1962. 320c.

? Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)

? Зыков А. А. Основы теории графов - М.: "Вузовская книга", 2004. - С. 664. - ISBN 5-9502-0057-8. (М.: Наука, 1987. 383c.)

? Химические программы топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.

? Кирсанов М.Н. Графы в Maple. М.: Физматлит, 2007. 168

? Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 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.

? К.В. Николаева, В.В. Койбичук Дискретный анализ. Графы и их применение в экономике


См.. также

Nuvola apps edu mathematics blue-p.svg
В Википедии есть портал



Сигма Это незавершенная статья по математики.
Вы можете помочь проекту, исправив и дополнив ее.


Компьютер Это незавершенная статья о компьютеры.
Вы можете помочь проекту, исправив и дополнив ее.
Основные разделы Математики
Алгебра ? Дискретная математика ? Дифференциальные уравнения ? Геометрия ? Комбинаторика ? Линейная алгебра ? Логика ? Математическая статистика ? Математический анализ ? Теория вероятностей ? Теория множеств ? Теория чисел ? Тригонометрия ? Математическая физика ? Топология ? Функциональный анализ