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

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

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

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

Графы являются основным объектом изучения теории графов.

Определения

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

Простой граф

Определение. Простой граф G ( V , E ) {displaystyle G(V,E)} есть совокупность двух множеств – непустого множества V {displaystyle V} и множества E {displaystyle E} неупорядоченных пар различных элементов множества V {displaystyle V} . Множество V {displaystyle V} называется множеством вершин, множество E {displaystyle E} называется множеством рёбер

G ( V , E ) = ⟨ V , E ⟩ , V ≠ ∅ , E ⊆ V × V , { v , v } ∉ E , v ∈ V {displaystyle G(V,E)=leftlangle V,E ight angle ,quad V eq varnothing ,quad Esubseteq V imes V,quad left{v,v ight} otin E,quad vin V} ,

то есть множество E {displaystyle E} состоит из 2-элементных подмножеств множества V {displaystyle V} .

Сопутствующие термины

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

• Вершина (узел, точка) (англ. vertex, node, point) графа G {displaystyle G} есть элемент множества вершин v ∈ V ( G ) {displaystyle vin V(G)} ;

• Ребро (линия) (англ. edge, line) графа G {displaystyle G} есть элемент множества ребер e ∈ E ( G ) {displaystyle ein E(G)} , или e = { v 1 , v 2 } {displaystyle e=left{v_{1},v_{2} ight}} , где v 1 ∈ V ( G ) , v 2 ∈ V ( G ) {displaystyle v_{1}in V(G),quad v_{2}in V(G)} ;

• Элементами графа G {displaystyle G} называются его вершины v ∈ V ( G ) {displaystyle vin V(G)} и рёбра e ∈ E ( G ) {displaystyle ein E(G)} графа;

• Порядок (англ. order) графа G {displaystyle G} есть кардинальное число множества вершин n = | V ( G ) | {displaystyle n=|V(G)|} или, другими словами, количество вершин;

• Размер (англ. size) графа G {displaystyle G} есть кардинальное число множества ребер m = | E ( G ) | {displaystyle m=|E(G)|} или, другими словами, количество ребер;

• Вершина v {displaystyle v} инцидентна (англ. incident) ребру e {displaystyle e} , если v ∈ e {displaystyle vin e} ; тогда еще говорят, что e {displaystyle e} есть ребро при v {displaystyle v} ;

• Концевые вершины (концы) (англ. endvertices, ends) есть две вершины, инцидентные ребру. Ребро соединяет (англ. joins) свои концевые вершины;

• Соседние (смежные) вершины (англ. neighbours, adjacent) есть такие вершины v 1 {displaystyle v_{1}} и v 2 {displaystyle v_{2}} что { v 1 , v 2 } ∈ E ( G ) {displaystyle left{v_{1},v_{2} ight}in E(G)} или, другими, словами обе вершины являются концевыми для одного ребра;

• Смежные ребра (англ. adjacent edges) это ребра, инцидентные одной вершине или e 1 = { v , v 1 } {displaystyle e_{1}=left{v,v_{1} ight}} и e 2 = { v , v 2 } {displaystyle e_{2}=left{v,v_{2} ight}} - смежные;

• Степень (валентность) вершины (англ. degree, valency) есть количество инцидентных ей рёбер. Степень вершины обозначается как d ( v ) {displaystyle d(v)} ;

• Изолированной вершиной (англ. isolated) называется вершина со степенью d ( v ) = 0 {displaystyle d(v)=0} , то есть не является концом ни для одного ребра;

• Висячей вершиной (листом) (англ. leaf) называется вершина со степенью d ( v ) = 1 {displaystyle d(v)=1} , то есть которая является концом ровно одного ребра.

Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.

Псевдограф

Псевдограф G ( V , E ) {displaystyle G(V,E)} есть совокупность двух множеств – непустого множества V {displaystyle V} и множества E {displaystyle E} неупорядоченных пар элементов множества V {displaystyle V} .

G ( V , E ) = ⟨ V , E ⟩ , V ≠ ∅ , E ⊆ V × V {displaystyle G(V,E)=leftlangle V,E ight angle ,quad V eq varnothing ,quad Esubseteq V imes V}

В множестве ребер псевдографа разрешен элемент { v , v } ∈ E ( G ) {displaystyle left{v,v ight}in E(G)} .

• Петлей (англ. loop) называется элемент e = { v , v } {displaystyle e=left{v,v ight}} , являющийся ребром, у которого концевые вершины совпадают.

Другими словами, если элементами множества E могут быть петли, то граф называется псевдографом .

Мультиграф

Мультиграф G ( V , E ) {displaystyle G(V,mathbf {E} )} есть совокупность двух множеств – непустого множества V {displaystyle V} и мультимножества E {displaystyle mathbf {E} } неупорядоченных пар различных элементов множества V {displaystyle V} .

G ( V , E ) = ⟨ V , E ⟩ , V ≠ ∅ , E ⊆ V × V { v , v } ∉ E , v ∈ V {displaystyle G(V,mathbf {E} )=leftlangle V,mathbf {E} ight angle ,quad V eq varnothing ,quad mathbf {E} subseteq V imes Vquad left{v,v ight} otin mathbf {E} ,quad vin V}

• Кратными рёбрами называются одинаковые элементы мультимножества { e , e , … , e } ∈ E {displaystyle left{e,e,dots ,e ight}in mathbf {E} } , то есть ребра, чьи концевые вершины совпадают.

Другими словами Если 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} .

G ( V , E ) = ⟨ V , E ⟩ , V ≠ ∅ , E ⊆ V × V {displaystyle G(V,mathbf {E} )=leftlangle V,mathbf {E} ight angle ,quad V eq varnothing ,quad mathbf {E} subseteq V imes 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}

G ( V , E ) = ⟨ V , E ⟩ , V ≠ ∅ , ⟨ { v 1 , v 2 } , ≺ ⟩ ∈ E , v ∈ V {displaystyle G(V,E)=leftlangle V,E ight angle ,quad V eq varnothing ,quad leftlangle left{v_{1},v_{2} ight},prec ight angle in E,quad vin V} .

совместно с двумя отображениями

i n i t : E → V , t e r : E → V {displaystyle init:E ightarrow V,quad ter:E ightarrow V} ,

где отображение i n i t : E → V {displaystyle init:E ightarrow V} ставит в соответствие каждой дуге ее начальную вершину (начало дуги) i n i t ( e ) {displaystyle init(e)} , а отображение t e r : E → V {displaystyle ter:E ightarrow 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 ( V , E , U ) = ⟨ V , E , U ⟩ , V ≠ ∅ , ⟨ { v 1 , v 2 } , ≺ ⟩ ∈ E , { v 3 , v 4 } ∈ U , v ∈ V {displaystyle G(V,E,U)=leftlangle V,E,U ight angle ,quad V eq varnothing ,quad leftlangle left{v_{1},v_{2} ight},prec ight angle in E,quad left{v_{3},v_{4} ight}in U,quad vin V} .

совместно с двумя отображениями

i n i t : E → V , t e r : E → V {displaystyle init:E ightarrow V,quad ter:E ightarrow 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} . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.

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

Дополнительные характеристики графов

Граф называется:

• связным, если для любых вершин u {displaystyle u} , v {displaystyle v} есть путь из u {displaystyle u} в v {displaystyle v} .
• сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
• деревом, если он связный и не содержит нетривиальных циклов.
• полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
• двудольным, если его вершины можно разбить на два непересекающихся подмножества V 1 {displaystyle V_{1}} и V 2 {displaystyle V_{2}} так, что всякое ребро соединяет вершину из V 1 {displaystyle V_{1}} с вершиной из V 2 {displaystyle V_{2}} .
• k-дольным, если его вершины можно разбить на k {displaystyle k} непересекающихся подмножеств V 1 {displaystyle V_{1}} , V 2 {displaystyle V_{2}} , …, V k {displaystyle V_{k}} так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
• полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
• планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
• взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
• хордальным, если граф не содержит индуцированных циклов с длиной больше трёх.

Также бывает:

• k-раскрашиваемым
• k-хроматическим

Обобщение понятия графа

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

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

• эйлеровы графы — граф, в котором существует циклический эйлеров путь (эйлеров цикл);

Способы представления графа в информатике

Матрица смежности

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

Это наиболее удобный способ представления плотных графов.

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

• Двумерный массив;
• Матрица с пропусками;
• Неявное задание (при помощи функции).

Матрица инцидентности

Таблица, где строки соответствуют вершинам графа, а столбцы соответствуют связям (рёбрам) графа. В ячейку матрицы на пересечении строки i {displaystyle i} со столбцом j {displaystyle j} записывается:

1 в случае, если связь j {displaystyle j} «выходит» из вершины i {displaystyle i} , −1, если связь «входит» в вершину, 0 во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является довольно ёмким (размер пропорционален | V | | E | {displaystyle |V||E|} ) для хранения, поэтому применяется очень редко, в особых случаях (например, для быстрого нахождения циклов в графе).

Список смежности

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

Размер занимаемой памяти: O ( | V | + | E | ) {displaystyle O(|V|+|E|)} .

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

Список рёбер

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

Размер занимаемой памяти: O ( | E | ) {displaystyle O(|E|)} .

Это наиболее компактный способ представления графов, поэтому часто применяется для внешнего хранения или обмена данными.

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

Языки описания

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

• DOT
• GraphML
• Trivial Graph Format
• GML
• GXL
• XGMML
• DGML

Программы для построения

Разработана серия коммерческих программ для построения графов, так, построение графов лежит в основе прикладных программных пакетов фирмы ILOG (с 2009 года принадлежит корпорации IBM), среди других программ — GoView, Lassalle AddFlow, LEDA (есть бесплатная редакция).

Также существует свободная программа для построения графов igraph и свободная библиотека Boost.

Программы для визуализации

Для визуализации графов применяются следующие программные средства:

• Graphviz (Eclipse Public License)
• LION Graph Visualizer.
• Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом (GNU LGPL; только для Windows).
• Gephi — графическая оболочка для представления и изучения графов (GNU GPL, CDDL).
• Библиотека GraphX — свободная библиотека для .NET для расчёта и отрисовки графов, использует WPF 4.0.
• Библиотека MSAGL — свободная библиотека для .NET.