3.2. Изоморфизм графов. Связность графов

Ранее было отмечено, что любой граф в абстрактном смысле идентичен, или, используя более принятый термин, изоморфен некоторому геометрическому графу. Изоморфизм графов формально определяется следующим образом: графы G = (V, Е) и G^/ = (V^/, Е^/) изоморфны друг дру­гу, если существует взаимно однозначное соотношение между V и V^/ и между Е и Е^/, сохраняющее отношения инцидентности. Если граф G, изоморфен геометрическому графу G^/, тогда G^/ называется геометри­ческой реализацией графа G.

Граф называется плоским тогда и только тогда, когда он имеет геомет-рическую реализацию в пространстве [10].

Рис.3.4 иллюстрирует очевидный, но важный факт: геометричес­кий граф монет быть плоским, даже если его нельзя преобразовать в плоский граф с помощью непрерывной деформации. Хотя G и G^/ имеют существенные отличия с точки зрения топологии, с точки зрения теории грифов они эквивалентны.

Рис. 3.4

В качестве примеров неплоских графов приведем графы Куратовского. (рис.3.5).

K_3,3

Рис. 3.5

Для конечного графа имеет место следующее утверждение: любой конечный граф G имеет геометрическую реализацию в На основа­нии этого в [10] доказана теорема: граф G = (V, Е) имеет геометрическую реализацию в тогда и только тогда, когда элементам V и Е можно поставить во взаимно однозначное соответствие некоторое подмножество множества действительных чисел. Исходя из понятия кардинального числа сказанное означает, что G имеет реализацию тогда и только тогда, когда кардинальные числа множеств V и Е совпадают с кардинальными числами континуума. Идея доказательства этой теоремы состоит в том, что точки пространства можно однозначно отобразить на множество действительных чисел. Очевидно, что граф G = (V, Е) не имеет реализации в (и даже в любого положительного целого n), если нельзя установить взаимно однозначного соответствия между некоторыми множествами его вершин или ребер и подмножеством точек в

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

Теорема [10]. Граф G = (V, Е) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V₁ и V₂ так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.

Доказательство этого утверждения почти очевидно. Пусть G несвязен. Выберем произвольную вершину v₁, и пусть множество V₁ состоит из вершины v₁ вместе всеми вершинами, которые могут быть соединены с v₁ цепью. Так как G несвязен, V₁ V, поэтому дополнение V₂ = V – V₁, непусто. Согласно метода построения множества V₁ ни одно ребро не соединяет вершину из V₁ ни с одной вершиной из V₂, откуда и получаем разбиение, указанное в формулировке теоремы. Обратно, если такое разбиение существует, произвольно выбираем вершины v₁ V₁ и v₂ V₂. Цепь, соединяющая v₁ и v₂, обязательно должна содержать, по крайней мере, одно ребро, имеющее граничные точки в обоих множествах V₁ и V₂, а так как такого ребра не существует, то граф G несвязен. Доказательство закончено.

Пусть G = (V, Е) – произвольный граф. Рассмотрим бинарное отношение р, определенное между некоторыми упорядоченными парами вершин следующим образом: vрw тогда и только тогда, когда v = w или когда существует цепь, соединяющая v с w. Очевидно оно рефлексив­но, симметрично и транзитивно, т.е. является отношением эквивалентности. Оно разбивает множество V единственным образом на классы эквивалентности взаимно связанных вершин. Для графа, изображенного на рис.3.1, такими классами эквивалентности являются . Каждый класс эквивалентности вершин вместе c ребрами из Е, инцидентными этим вершинам, образует связный подграф, называемый просто компонентой G. Легко видеть, что компонента G₁, графа G является максимальным связным подграфом в том смысле, что граф G₁ не имеет связного собственного подграфа.

Граф называется деревом, если он связен и не имеет циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. Удаление любого ребра из дерева делает его несвязным, так как удаляемое ребро составляет единственную цепь, соединяющую его граничные точки. Если дерево Т является подграфом графа G и включает все его вершины, то говорят, что дерево Т покрывает граф G. Каждое дерево с n вершинами имеет в точности n – 1 ребро. Лес, сос­тоящий из k деревьев, имеет в точности n – k ребер. С понятием связности тесно увязаны понятия разделяющего множества и разреза. Они возникают при изучении потоков в сетях. В этих задачах фунда­ментальную роль играет изучение поперечных сечений сети, отделяющих источник потока от стока, и нахождение ограничивающего поперечного сочения, которое является самим узким местом. Ясно, что узкие места определяют пропускную способность сети в целом. Пусть G = (V, Е) – связный граф F Е – подмножество множества его ребер. При этом F называется разделяющим множеством тогда и только тогда, когда подграф G^/ = (V, Е\ F) несвязен. Здесь Е\ F – разность множеств Е и F. Разделяющее множество всегда существует (если граф G имеет хотя бы две вершины), так как всегда можно положить F = Е. Примеры разделяющих множеств графа G показаны штрихом на рис. 3.6.

Рис. 3.6

Разделяющее множество разбивает граф на три компоненты, одна из которых содержит вершины множества W, обведенные кружком. Очевидно, для разбиения графа достаточно удалить только те ребра, которые соединяют множество вершин W с вершинами W'= V\W (е₁, е_2, е_3, е_4, е₅).

В общем случае, если задан связный граф G = (V, Е) и множество вершин разбито на два непустых подмножества W и W^/, множество ребер, соединяющих W с W', называется разрезом. Для любого множества W это множество ребер будет непусто в силу связности графа G,, и, следовательно, разрез определен. Для любого заданного графа совокупность разрезов, определенных различными множествами W, образует подкласс всех разделяющих множеств и, более того, любое разделяющее множество содержит, по крайней мере, один разрез в качестве своего подмножества. Особый интерес для изучения представляют минимальные разделяющие множества, т.е. такие разделяющие множества, которые не содержат собственного подмножества, разделяющего граф [10].

Минимальные разделяющие множества называются простыми разрезами. Имеют место [10, 11] следующие утверждения:

– покрывающее дерево имеет, по крайней мере, одно общее ребро с любым из разрезов графа;

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

С точки зрения связности интересны .два случая (рис. 3.7): наличие точки сочленения (вершины V_с , удаление которой вместе с инцидентными ей ребрами делает граф не связным) и наличие моста (удаление «моста» - одного ребра е делает граф несвязным).

Рис. 3.7

Минимальное число вершин, удаление которых делает граф несвязным, называется вершинной связностью (G) графа. Минимальное число ребер, удаление которых делает граф несвязным, называется ре­берной связностью (G). Если обозначить (G) минимальную сте­пень вершины в графе G', то имеет место следующее неравенство:

(G) (G) (G). (3.4)

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

С точки зрения введенных понятий отметим ряд специальных клас­сов графов. Граф называется обыкновенным, если он не содержит петель и параллельных ребер. Граф называется полным, если любые две вершины являются смежными, т.е. соединяются ребром. Обычно этот термин­ относится к обыкновенным графам и для каждого имеется только один полный граф (все остальные ему изоморфны). Граф называется двудольным, если его вершины могут быть разбиты на два непересекающихся подмножества V₁ и V₂ так, что каждое ребро имеет одну гра­ничную точку в V₁, а другую в V₂ (рис.3.8). В общем случае граф называется k-дольным, если множество вершин можно разбить на k непересекающихся подмножеств так, что не существует ребер, соединяющих вершины одного и того же подмножества. Граф называется k-связным, если любая пара вершин v и w соединена, по крайней мере, k цепями, которые не имеют общих вершин за исключением v и w.

Граф называется k-однородным, если (v) = k, v V. Кроме топологических свойств графов, определяющих их структуру, существует целый ряд методов приближения структуры к реальным системам. Один из

этих методов – придание свойств элементам структуры (вершинам и ребрам). Зададим одно из свойств элементам множества Е графа G = (V, Е) – направлен-ность.