Файл: Diskretnaya_matematika.doc

Дополнительным частичным графом Н(А) графа G(X) явля­ется единственный граф, состоящий из ребер графа G(X), не при­надлежащих некоторому частичному подграфу Н_А(А) графа G(X) (рис. 3.11).

3.1.5. Связность в графах

Рассмотрим вопрос о связности в графах. Пусть G(X) – неори­ентированный граф. Две вершины х_iиx_jназываютсясвязными, если существует цепьSс концами х_iиx_j. ЕслиSпроходит через некото­рую вершинуx_kболее одного раза, то можно удалить цикл в верши­неx_kиз цепиS. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.

Неориентированный граф называется связным, если любая па­ра его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности (x_i~x_j, х_j~ х_kx_i~ х_k).

Компонентой связ­ностинеориентирован­ного графаG(X) называ­ется подграф Н_А(А) графаG(X) с множеством вер­шин АXи множеством ребер вG(X), инцидент­ных только вершинам из А, причем ни одна вершинаx_i А не смежна с вершинами из множества Х \ А (рис. 3.12).

Рис. 3.12. Граф с двумя компонентами связности

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

Компонентой сильной связностиориентированного графаG(X) называется подграф Н_А(А) графаG(Х) (подчиняющийся опре­делению сильно связного графа) с множеством вершин АХ и мно­жеством дуг, имеющих начало и конец в А, причем ни одна из вер­шин х_iА и х_jX\ А не смежны между собой (рис. 3.13).

Рис. 3.13. Ориентированный граф с двумя компонентами сильной связности

Очевидно, что ориентированный граф G(X) сильно связан то­гда и только тогда, когда он имеет одну компоненту связности.

На практике широко используются такие виды графов, как де­ревья и прадеревья.

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

Ветвямидерева называются ребра графа, вхо­дящие в дерево.Хордами дереваназываются ребра, входящие в граф, дополнительный к данному дереву.Лагранжевым дере­вомназывается дерево, все ветви которого имеют общую вершину.

Рис. 3.14. Дерево

Лесом называется несвязный граф, каждая компонента связно­сти которого является деревом.

Прадеревомназывается ориентированный графG(X) с корнем х₀ X, если в каждую вершину х_iх₀(х_iX) заходит ровно одна дуга, а в корень х₀не заходит ни одна дуга. Прадерево не содержит контуров (рис.3.15).

Рис. 3.15. Прадерево

3.1.6. Изоморфизм. Плоские графы

В изображении графа имеется относительно большая свобода в размещении вершин и в выборе формы соединяющих их ребер. По­этому один и тот же граф может быть представлен по-разному (рис. 3.16).

Р

G₁(X₁)

Графы G₁(X₁) иG₂(X₂) называютсяизоморфными, если между множествами их вершин существует взаимно однозначное соответ­ствие, сохраняющее смежность вершин. Иначе, если вершины являются смежными (соединены ребрами) в одном из графов, то соответствующие им вершины в другом графе также являются смежными. Если ребра графов ориентированы, то их направление в изоморфных графах также должно соответствовать друг другу.

ГрафG(X) называется плоским, если он может быть изобра­жен на плоскости так, что все пересечения его ребер являются вер­шинами графаG(X) (рис. 3.17).

а) б)

Рис. 3.17. Примеры плоского (а) и неплоского (б) графов

3.2. Отношения на множествах и графы

Каждый ориентированный граф G(X) определяет некоторое от­ношение на множествеXсвоих вершин. Это отношение может быть записано какx_i Gx_j. Оно означает, что в графе есть дуга, идущая отx_iкx_j.

Отношению со свойством рефлексивности(xRх) должна со­ответствовать на графепетля в вершине. Если это отношение со­блюдается во всех вершинах хX, то соответствующий графG(X) должен иметь петлю в каждой своей вершине.

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

Симметрическомуотношению на множествеXсоответствует граф снеориентированными ребрами и, наоборот, граф с неориенти­рованными ребрами определяет некоторое симметрическое отношение.

В случае антисимметрическогоотношения на графе невоз­можно присутствие двух дуг (x_i,x_j), (x_j,x_i) на графе, то есть сущест­вование неориентированного ребра. Кроме того, на этих графах нет петель, то есть соответствующее антисимметрическое отношение антирефлексивно.

Отношение, обладающее свойствомтождественности, соот­ветствует графу с антисимметричным отношением на множестве вершин (ориентированному графу) и добавлением петли в каждой вершине. Этот граф не должен иметь контуров.

Рис. 3.18. Свойство транзи­тивности на графе

Граф, соответствующий транзитивномуотношению (рис. 3.18), обладает следующи­ми свойствами: для любой пары ориентированных ребер (дуг) графа (x_i,x_j), (x_j,x_k) имеется за­мыкающая дуга (x_i,x_k). Можно сказать, что в графе, который соответствует транзитивному отношению, для каждого путиS(x_i,x_k) имеется дуга (x_i,x_k) (рис.3.19).

а) б)

Рис. 3.19. Транзитивный (а) и нетранзитивный (б) графы

Отношение, обладающее свойством полноты, опреде­лено на множестве вершин полного ориентированного графа.

Нулевоеотношение определено на множестве вершин ноль-графа.

Универсальноеотношение определено на множестве вершин полного неориентированного графа с петлями.ДополнительноекRотношениеRопределено на множестве вершин дополнительного графаG_d(Х) кG(X).

Графы, соответствующие отношению эквива­лент­ности, пред­ставляют собой совокупность компонент связности (для каждого класса эквивалентности своя компонента) несвязного графа. Каждая компонента несвязного графа должна быть полным неориентиро­ванным графом с петлями (рис. 3.20).

Рис. 3.20. Граф, соответствующий отношению эквивалентности

3.3. Матрицы смежности и инциденций графа

Если в графе G(X) через а_ijобозначить число дуг, идущих изx_i вx_j, то матрицаA= || а_ij || (i= 1, ...,n;j=1, ...,n; гдеn– число вершин графа) называетсяматри­цей смежности вершин графа.

Наличие нулевого элемента на главной диагонали означает от­сутствие петли в соответствующей вершине.

Матрица А^тсоответствует графуG^-1(X). Матрица А является симметрической тогда и только тогда, когда графG(X) – симметри­ческий. Матрица А антисимметрична тогда и только тогда, когда графG(X) – антисим­мет­рический. Матрица А полна тогда и только тогда, когда графG(X) – полный (а_ij+ а_ji1).

Рис. 3.21. Пример графа для определения матрицы

смежности A

Матрицей смежности ребер графа называется такая матрица В = || b_ij|| (I= 1, ...,m;j= 1, ...,m; гдеm- число ребер графа), что:

1

b_ij =

0 в противном случае.

Пусть g₁, ..., g_m – дуги, х₁, ..., х_n – вершины ориентиро­ванного графа G(X). Матрица S = || s_ij || (I = 1, ..., n – номер вершины графа, j = 1, ..., m – номер дуги графа), такая что:

s_ij =

-1, если g_j заходит в х_i,

0, если g_j не инцидентна х_i

называется матрицей инциденций для дуг графа.

Для неорграфа матрица R = || r_ij || размером n х m, где:

1

r_ij =

0 в противном случае

называетсяматрицей инциденций для ребер графа.