Инцидентность вершин графа. Изоморфизм. Маршруты на графах

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

Рассматривая инцидентность вершин и ребер (p и q) - графа, можно представить его матрицей инцидентности размера p x q, строки которой соответствуют вершинам, а столбы - ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина v_i, инцидентна ребру e_i, и равен нулю, если v_i, и e_i, не инцидентны. В случае орграфа ненулевой ij-элемент равен 1, если v_i начальная вершина дуги e_i, и равен - 1, если v_i - конечная вершина дуги e_i.

Например, матрица инцидентности графа, приведенного на рис. 5, а, имеет вид:

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

Рис. 6. Изоморфные графы

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

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

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

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

Маршруты. Нередко задачи на графах требуют выделения различных маршрутов, обладающих определенными свойствами и характеристиками. Маршрут длины m определяется как последовательность т ребер графа (не обязательно различных) таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Примерами маршрутов на графе рис. 5, а могут служить последовательности ( ), ( ). Первый маршрут проходит через последовательность вершин ( ) и соединяет вершины и a второй — через последовательность вершин ( ) и соединяет вершины и . Замкнутый маршрут приводит в ту же вершину, из которой он начался.

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

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

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

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

Части графа.Граф G' = (V', Е') является частью графа G = (V, Е), если V' V и Е' Е, т. е. граф содержит все вершины и ребра любой его части. Часть, которая, наряду с некоторым подмножеством ребер графа, содержит и все инцидентные им вершины, называется подграфом. Часть, которая наряду с некоторым подмножеством ребер графа, содержит все вершины графа (V’=V, Е' Е), называется суграфом. Рассмотренные графы показаны на рис. 7.

Рис. 7. Граф и его части: а - граф; б - часть графа; в - подграф; г – суграф.

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу - сверхграфом. Совокупность всех ребер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа. Говорят, что подграфы G' = (V', Е') и G" = (V", Е") разделены ребрами, если они не имеют общих ребер (Е' Е" =Ø) и разделены вершинами, если у них нет общих вершин (V' V" =Ø).

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

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

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

Простая Цепь   Рис. 8. Связный граф.	Рис. 9. Несвязный граф, состоящий из трех компонент (G1, G2, G3)

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

Разделимость. Связный граф может быть разделен на несвязные подграфы удалением из него некоторых вершин и ребер (при удалении вершин исключаются и все инцидентные им ребра, а при удалении ребер вершины сохраняются). Если существует такая вершина, удаление которой превращает связный граф (или компоненту несвязного графа) в несвязный, то она называется точкой сочленения (рис. 10, а). Ребро с такими же свойствами называется мостом (рис. 10, б). Ясно, что при наличии моста в графе имеется, по крайней мере, две точки сочленения.

Граф называется неразделимым, если он связный и не имеет точек сочленения (например, граф на рис. 7, а неразделим). Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из котооых представляет собой максимальный неразделимый подграф (на рис. 10, в показаны блоки B₁,B₂,B₃ графа рис. 10, б).

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

Рис. 10. Разделимые графы: а - с точкой сочленения; б - с мостом; в - блоки B1 - B3 графа с мостом

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

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

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

р - к ребер). Сказанное иллюстрируется на примере дерева (рис. 11, а), которое превращается в циклический граф добавлением ребра (рис. 11, б) и распадается на лес из двух деревьев T₁ и T₂ при удалении ребра е (рис. 11, в).

Рис. 11. Дерево (а), образование цикла при введении дополнительного ребра (б) и лес, который образуется после удаления ребра е (в).

Обычно деревья считаются существенно различными, если они не изоморфны. На рис. 12 показаны все возможные различные деревья с шестью вершинами. С увеличением числа вершин количество различных деревьев резко возрастает (например, при р = 20 их насчитывается около миллиона). Среди различных деревьев выделяются два важных частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.

Рис. 12. Существенно различные деревья с шестью вершинами.	Рис. 13. Прадерево с корнем .

Рассматриваются также деревья с ориентированными ребрами (дугами). Ориентированное дерево называется прадеревом с корнем , если существует путь между вершиной любой другой его вершиной (рис. 13). Ясно, что прадерево имеет единственный корень.

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

Ребра графа, которые принадлежат его дереву, называют ветвями. Если дерево покрывает граф, то множество ребер графа разбивается на два подмножества: подмножество ветвей и подмножество ребер дополнения дерева, называемых хордами. При этом связный (р, q) - граф содержит v = р - 1 ветвей и = q - р + 1 хорд. Если граф несвязный, то совокупность, остовов R его компонент образует покрывающий лес. В этом случае = р - R

и = q - р + R.

Рис. 14. Дерево как часть графа (выделено жирными линиями): а — дерево; б — остов (покрывающее дерево).

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

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

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

Рис. 15. Графы Понтрягина - Куратовского: а - полный пятиугольник; б — двудольный граф.

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

Строго доказывается, что граф является плоским тогда и только тогда, когда он не содержит подграфа, гомеоморфного одному из графов Понтрягина - Куратовского.

Рис. 16. Гомеоморфные графы.

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

Графы и отношения.Пусть на множестве Х задано бинарное отношение А. Ему соответствует ориентированный граф, вершины которого отображают элементы из X, а дуга (х_i, x_j), где (х_i, x_j X), существует тогда и только тогда, когда(х_iАx_j). Обратно, множество ориентированных дуг графа (без строго параллельных дуг), заданных упорядоченными парами (х_i, x_j), можно рассматривать как бинарное отношение на множестве X.

Если бинарное отношение хАy устанавливает связь между элементами х из множества Х и элементами у из множества Y (х X, у У), то граф такого отношения будет ориентированным биграфом.

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