Граф (математика)

Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Графы находят широкое применение в современной науке и технике. Они используются и в естественных науках (физике и химии) и в социальных науках (например, социологии), но наибольших масштабов применение графов получило в информатике и сетевых технологиях.
В качестве простейшего примера из жизни можно привести схему перелётов определённой авиакомпании, которая моделируется графом, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. Дерево каталогов в компьютере также является графом: диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски. Строение Википедии моделируется ориентированным графом, в котором статьи — вершины графа, а гиперссылки — дуги (тематическая карта).
Графы являются основным объектом изучения теории графов.
Моделируемые графами системы реальной природы обладают большим разнообразием, поэтому существуют графы различных типов. Простейшей абстракцией систем с элементами, обладающими парными связями, является простой граф.
Определение. Простой граф G ( V , E ) {\displaystyle G(V,E)} есть совокупность двух множеств — непустого множества V {\displaystyle V} и множества E {\displaystyle E} неупорядоченных пар различных элементов множества V {\displaystyle V} . Множество V {\displaystyle V} называется множеством вершин, множество E {\displaystyle E} называется множеством рёбер
то есть множество E {\displaystyle E} состоит из 2-элементных подмножеств множества V {\displaystyle V} .
Сопутствующие термины
Теория графов не обладает устоявшейся терминологией. Поэтому в некоторых публикациях могут использоваться термины, отличные от приведенных ниже.
Обычно граф изображают диаграммой: вершины — точками, ребра — линиями.
Псевдограф G ( V , E ) {\displaystyle G(V,E)} есть совокупность двух множеств — непустого множества V {\displaystyle V} и множества E {\displaystyle E} неупорядоченных пар элементов множества V {\displaystyle V} .
В множестве ребер псевдографа разрешен элемент { v , v } ∈ E ( G ) {\displaystyle \left\{v,v\right\}\in E(G)} .
Другими словами, если элементами множества E могут быть петли, то граф называется псевдографом .
Мультиграф G ( V , E ) {\displaystyle G(V,\mathbf {E} )} есть совокупность двух множеств — непустого множества V {\displaystyle V} и мультимножества E {\displaystyle \mathbf {E} } неупорядоченных пар различных элементов множества V {\displaystyle V} .
Другими словами Если E {\displaystyle E} не множество, а семейство, то есть если E {\displaystyle \mathbf {E} } содержит одинаковые элементы, то такие элементы называются кратными рёбрами, а граф называется мультиграфом .
Псевдомультиграф G ( V , E ) {\displaystyle G(V,\mathbf {E} )} есть совокупность двух множеств — непустого множества V {\displaystyle V} и мультимножества E {\displaystyle \mathbf {E} } неупорядоченных пар элементов множества V {\displaystyle V} .
Другими словами, если E {\displaystyle \mathbf {E} } — семейство, содержащее одинаковые элементы (кратные ребра), и E {\displaystyle \mathbf {E} } может содержать петли, то граф называется псевдомультиграфом.
Ориентированный граф (орграф) (англ. directed graph or dirgaph) G ( V , E ) {\displaystyle G(V,E)} есть совокупность двух множеств — непустого множества V {\displaystyle V} и множества E {\displaystyle E} дуг или упорядоченных пар различных элементов множества V {\displaystyle V}
совместно с двумя отображениями
где отображение i n i t : E → V {\displaystyle init:E\rightarrow V} ставит в соответствие каждой дуге ее начальную вершину (начало дуги) i n i t ( e ) {\displaystyle init(e)} , а отображение t e r : E → V {\displaystyle ter:E\rightarrow V} ставит в соответствие каждой дуге ее конечную вершину (конец дуги) t e r ( e ) {\displaystyle ter(e)} . Говорят что дуга e {\displaystyle e} ведет из i n i t ( e ) {\displaystyle init(e)} в t e r ( e ) {\displaystyle ter(e)}
Смешанный граф (англ. Mixed graph) G ( V , E , U ) {\displaystyle G(V,E,U)} — это совокупность трех множеств — непустого множества вершин V {\displaystyle V} , и множества дуг E {\displaystyle E} или упорядоченных пар различных элементов множества V {\displaystyle V} и множества ребер U {\displaystyle U} неупорядоченных пар различных элементов множества V {\displaystyle V}
совместно с двумя отображениями
Ориентированный и неориентированный графы являются частными случаями смешанного.
Граф G {\displaystyle G} называется изоморфным графу H {\displaystyle H} , если существует биекция f {\displaystyle f} из множества вершин графа G {\displaystyle G} в множество вершин графа H {\displaystyle H} , обладающая следующим свойством: если в графе G {\displaystyle G} есть ребро из вершины A {\displaystyle A} в вершину B {\displaystyle B} , то в графе H {\displaystyle H} должно быть ребро из вершины f ( A ) {\displaystyle f(A)} в вершину f ( B ) {\displaystyle f(B)} и наоборот — если в графе H {\displaystyle H} есть ребро из вершины A {\displaystyle A} в вершину B {\displaystyle B} , то в графе G {\displaystyle G} должно быть ребро из вершины f − 1 ( A ) {\displaystyle f^{-1}(A)} в вершину f − 1 ( B ) {\displaystyle f^{-1}(B)} . В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.
Маршрутом в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром. Цепью называется маршрут без повторяющихся рёбер. Простой цепью называется маршрут без повторяющихся вершин (откуда следует, что в простой цепи нет повторяющихся рёбер).
Ориентированным маршрутом (или путём) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему.
Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u {\displaystyle u} и v {\displaystyle v} являются концами некоторого ребра, то согласно данному определению, последовательность ( u , v , u ) {\displaystyle (u,v,u)} является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если рёбра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются (за исключением начальной и конечной в случае цикла).
Простейшие свойства путей и циклов:
Бинарное отношение на множестве вершин графа, заданное как «существует путь из u {\displaystyle u} в v {\displaystyle v} », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Всякий максимальный связный подграф графа G {\displaystyle G} называется связной компонентой (или просто компонентой) графа G {\displaystyle G} . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.
Ребро графа называется мостом, если его удаление увеличивает число компонент.
Граф называется:
Также бывает:
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку ( V , E , φ ) {\displaystyle (V,E,\varphi )} , где V {\displaystyle V} и E {\displaystyle E} — некоторые множества (вершин и рёбер, соотв.), а φ {\displaystyle \varphi } — функция инцидентности (или инцидентор), сопоставляющая каждому ребру e ∈ E {\displaystyle e\in E} (упорядоченную или неупорядоченную) пару вершин u {\displaystyle u} и v {\displaystyle v} из V {\displaystyle V} (его концов). Частными случаями этого понятия являются:
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Это наиболее удобный способ представления плотных графов.
Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.
Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки i {\displaystyle i} со столбцом j {\displaystyle j} записывается:
Данный способ является довольно ёмким (размер пропорционален | V | | E | {\displaystyle |V||E|} ) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).
Список, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такая структура данных не является таблицей в обычном понимании, а представляет собой «список списков».
Размер занимаемой памяти: O ( | V | + | E | ) {\displaystyle O(|V|+|E|)} .
Это наиболее удобный способ для представления разреженных графов, а также при реализации базовых алгоритмов обхода графа в ширину или глубину, где нужно быстро получать «соседей» текущей просматриваемой вершины.
Список, где каждому ребру графа соответствует строка, в которой хранятся две вершины, инцидентные ребру.
Размер занимаемой памяти: O ( | E | ) {\displaystyle O(|E|)} .
Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.
Для описания графов, пригодного для машинной обработки и одновременно удобного для человеческого восприятия, используется несколько стандартизированных языков, среди которых:
Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).
Также существует свободная программа для построения графов igraph и свободная библиотека Boost.
Для визуализации графов применяются следующие программные средства: