Материал: Diskretnaya_matematika

Прадеревомназывается ориентированный граф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 в противном случае

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

Рис. 3.22. Пример графа для определения матрицS и R

3.4. Операции над графами

3.4.1. Сумма графов

Пусть даны два графа G₁(X) иG₂(X) на одном и том же множе­стве вершин. ТогдасуммойграфовG₁(X) иG₂(X) является графG(X), состоящий из ребер, принадлежащихG₁(X) илиG₂(X).

Таким образом, если (х_i', х_j')G₁(X) и (х_i",х_j")G₂(X), то (х_i', х_j')G(X) и (х_i", х_j")G(X)(х_i', х_j', х_i", х_j")X.

Символически сумму двух графов обозначают следующим об­разом: G(X) =G₁(X)G₂(X). Аналогично определяется суммаnграфовG_i(X) (i= 1, ...,n):

G(X) =

как граф, состоящий из ребер, принадлежащих хотя бы одному из графов G_i(X) (рис. 3.24).

Операция суммирования графов обладает перемес­тительным свойством: G₁(X)G₂(X) =G₂(X)G₁(X).

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

G(X) = G₁(X₁)  G₂(X₂)  …  G_n (X_n) =,

для которого справедливо:

X = X₁  X₂  ...  X_n

и G(х_j) = G₁(х_j)  G₂(x_j)  …  G_n(х_j) = , х_jХ.

Сумма графов G₁(X₁) и G₂(X₂) изображена на рис. 3.23.

Пример 1

Рис. 3.23. Суммирование графов с различными множествами вершин

Пример 2

Рис. 3.24. Суммирование графов с одинаковыми множествами вершин

3.4.2. Пересечение графов

Пусть даны два графа G₁(X) иG₂(X) на одном и том же множе­стве вершин. ТогдапересечениемграфовG₁(X) иG₂(X) называется графG(X), состоящий из ребер, принадлежащих иG₁(X) иG₂(X), то есть если (х_i, х_j)G₁(X) и (х_i, х_j)G₂(X), то (х_i, х_j)G(X).

Обозначение пересечения двух графов:

G(X) =G₁(X)G₂(X).