комп. моделирование   логика   ТПОИ   эконом. информатика   дискретная математика 3GL   4GL   5GL  

Базовые понятия теории графов

Леонард Эйлер
  1. История возникновения теории графов
  2. Терминология теории графов
  3. Изображение графов на плоскости
  4. Языки и программы построения графов
  5. Некоторые задачи теории графов
  6. Применение теории графов
  7. Литература по теории графов

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

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

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

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

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

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

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

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

Граф в математической теории графов и информатике - это совокупность непустого множества объектов - вершин и связей между ними. Объекты представляются как вершины, или узлы графа, а связи - как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Неориентированный граф, G-граф - это упорядоченная пара G := (V, E), для которой выполнены следующие условия:

V - это непустое множество вершин, или узлов,

E - это множество пар (в случае неориентированного графа - неупорядоченных) вершин, называемых рёбрами.

V (а значит и, E, иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа.

Порядок графа - это число вершин в графе |V|.

Размер графа - это число его рёбер |E|

Концевые вершины графа - это вершины, соединяющие данное множество ребер. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть e=\{v,v\}.

Степенью вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G := (V, A), для которой выполнены следующие условия:

V — это непустое множество вершин или узлов,

A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v \to w ведёт от вершины v к вершине w.

Смешанный G-граф - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G := (V, E, A), где V, E и A определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Изоморфный граф - это некоторый граф G, для которого существует биекция f из множества вершин графа G в множество вершин другого графа H, которому он изоморфен, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот - если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины f^{-1}(A) в вершину f^{-1}(B). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

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

Ориентированный путь в орграфе - это конечная последовательность вершин v_i (i=1, …,k), для которой все пары (v_i, v_{i+1}) (i=1,… k-1) являются (ориентированными) рёбрами.

Цикл - это путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких “вырожденных” случаев, вводят следующие понятия.

Простой путь (простой цикл) - это такой путь, в котором ребра не повторяются.

Элементарный путь - это простой путь в графе, вершины в котором не повторяются.

Несложно видеть, что:

Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.

Всякий простой неэлементарный путь содержит элементарный цикл.

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

Петля - это элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как “существует путь из u в v”, является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Компонента графа, связная компонента графа - это всякий максимальный связный подграф G-графа. Слово "максимальный" означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.
Мост - это ребро графа, если удаление этого ребра увеличивает число компонент графа.
Связный граф - это граф, в котором для любых вершин u,v есть путь из u в v.
Сильно связный, ориентированно связный граф - это ориентированный граф, в котором из любой вершины в любую другую имеется ориентированный путь.
Дерево - это связный граф, не содержащий простых циклов.
Полный граф - это граф, в котором любые его две (различные, если не допускаются петли) вершины соединены ребром.
Двудольный граф - это граф, в котором вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2.
k-дольный граф - это граф, в котором вершины можно разбить на k непересекающихся подмножества V_1, V_2, :, V_k так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
Полный двудольный граф - это граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
Планарный граф - это граф, который можно изобразить диаграммой на плоскости без пересечений рёбер.
Взвешенный граф - это граф, в котором каждому ребру поставлено в соответствие некоторое число, называемое весом ребра.

Существуют также k-раскрашиваемые и k-хроматические графы.

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку (V, E, Ф), где V и E — некоторые множества (вершин и рёбер, соответственно), а Ф — функция инцидентности (или инцидентор), сопоставляющая каждому ребру e < E (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:

Под данное выше определение не подходят некоторые другие обобщения:

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

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

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

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

Языки описания и программы построения графов

Для описания графов в целях, пригодных для машинной обработки и одновременно удобном для человеческого восприятия используется несколько стандартизированных языков, среди которых:

Отметим специализированные программы для построения графов. К наиболее удачным относятся коммерческие:

Из бесплатных можно отметить Boost Graph Library - Библиотека для работы с графами на языке C++

Для визуализации графов можно использовать:

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

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

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

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

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

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

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

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

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

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

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

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

Литература по теории графов

  1. Diestel R. Graph Theory, Electronic Edition. - NY: Springer-Verlag, 2005. - С. 422.
  2. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
  3. Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. — М.: Высш. школа, 1976. — С. 392.
  4. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962. 320c.
  5. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
  6. Зыков А. А. Основы теории графов. — М.: “Вузовская книга”, 2004. — С. 664. — ISBN 5-9502-0057-8(М.: Наука, 1987. 383c.)
  7. Кирсанов М. Н. Графы в Maple. - М.: Физматлит, 2007. - 168 c.
  8. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978. 429c.
  9. Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд.. — М.: Вильямс, 2006. — С. 1296. — ISBN 0-07-013151-1
  10. Оре О. Теория графов. М.: Наука, 1968. 336с.
  11. Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. - М.: Физико-математическая литература, 1997. - ISBN 5-02-015033-9
  12. Свами М., Тхулалираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
  13. Татт У. Теория графов. Пер. с англ. М.: Мир, 1988. 424 с.
  14. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.
  15. Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  16. Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
  17. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.
  18. Харари Ф. Теория графов. М.: Мир, 1973.
  19. Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.
комп. моделирование   логика   ТПОИ   эконом. информатика   дискретная математика 3GL   4GL   5GL  
Знаете ли Вы, что "тёмная материя" - такая же фикция, как черная кошка в темной комнате. Это не физическая реальность, но фокус, подмена.
Реально идет речь о том, что релятивистские формулы не соответствуют астрономическим наблюдениям, давая на порядок и более меньшую массу и меньшую энергию. Отсюда сделан фокуснический вывод, что есть "темная материя" и "темная энергия", но не вывод, что релятивистские формулы не соответствуют реалиям. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 24.05.2017 - 20:22: СОВЕСТЬ - Conscience -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
24.05.2017 - 19:39: СОВЕСТЬ - Conscience -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
24.05.2017 - 16:55: СОВЕСТЬ - Conscience -> Декларация Академической Свободы - Карим_Хайдаров.
24.05.2017 - 14:52: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
24.05.2017 - 06:20: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
24.05.2017 - 06:19: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Гипотеза о причине смещения линии апсид эллиптических орбит - Карим_Хайдаров.
23.05.2017 - 16:17: СОВЕСТЬ - Conscience -> Проблема народного образования - Карим_Хайдаров.
23.05.2017 - 13:07: СОВЕСТЬ - Conscience -> Просвещение от Сергея Салля - Карим_Хайдаров.
15.05.2017 - 05:53: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Украинский сайт ЭкоТехника - Карим_Хайдаров.
13.05.2017 - 07:01: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Опыты Майкельсона-Морли,Маринова и увлечение эфира - Сергей_Юдин.
11.05.2017 - 16:32: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
11.05.2017 - 11:36: СОВЕСТЬ - Conscience -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution