Основные операции над графами

Матричные способы задания графов.

Изоморфизм графов.

Степени вершин графа.

Степенью (валентностью) (обозначение d (v) или deg (v)) вершины v простого графа G называется число ребер или дуг инцидентных данной вершине v. При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равны k, то граф называется регулярным (однородным) степени k. Если степень вершины равна 0, то она является изолированной. Если степень вершины равна 1, то вершина называется концевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v называется полустепенью исхода (v), а входящих – полустепенью захода (v), При этом справедливо соотношение d (v) = (v) + (v).

Теорема Эйлера: Сумма степеней вершин графа равна удвоенному количеству ребер, т.е., или, где n – число вершин; m – число ребер (дуг). Данное утверждение доказывается тем, что при подсчете суммы степеней вершин каждое ребро учитывается два раза - для одного конца ребра и для другого.

Граф называется помеченным (или перенумерованным), если его вершины отличаются друг от друга какими либо пометками (номерами). Граф считается полностью заданным в строгом смысле, если нумерация его вершин и ребер фиксирована. При этом графы G₁ и G₂ называются равными ( обозначение G₁ = G₂ ),, если их множества вершин и ребер совпадают. Два графа или псевдографа G₁= (V ₁ ,E ₁) и G₂= (V ₂ ,E ₂) называются изоморфными (обозначение), если существуют два взаимно однозначных отображения: 1) и 2) такие, что для любых двух вершин в графе справедливо соотношение.

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

1) Рефлексивности -, причем биекция представляет собой тождественную функцию.

2) Симметричности. Если с биекцией, то с биекцией.

3) Транзитивности. Если с биекцией,а с биекцией, то с биекцией.

Матрицей смежности графа G= (V,E) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

а) в случае неориентированного графа

б) для ориентированного графа

v ₁

e ₉

e ₈

e ₇

e ₆

e ₅

e ₄

e ₃

e ₂

e ₁

v ₆

v ₅

v ₄

v ₂

v ₃

в) в мультиграфе = k, где k – кратность ребра (v_i v_j).

Пример. Для графа изображенного на рисунке

матрица смежности имеет вид

Свойства матрицы смежности: Матрица смежности неориентированного графа является симметричной относительно главной диагонали. Диагональные элементы этой матрицы указывают на наличие петель в соответствующем графе.

Сумма элементов матрицы А неориентированного графа по i -ой строке (или i -му столбцу) равна d (v_i). Для ориентированного графа сумма элементов матрицы А по i -ой строке равна d (v_i), а по j -му столбцу d (v_j).

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

Объём памяти для матрицы смежности – О (n ²)

Матрицей инцидентности графа G= (V, E) с n вершинами и m ребрами называется матрица В размера n×m, элементы которой определяются следующим образом:

а) для неориентированного графа

б) для ориентированного графа

Например, для графа предыдущего примера:

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

Объём памяти для матрицы инцидентности – О (nm)

Объединением графов G ₁=(V ₁, E ₁) и G ₂ = (V ₂, E ₂) называется граф G ₃ = (V ₁È V ₂, E ₁È E ₂). Объединение называется дизъюнктным, если V ₁Ç V ₂ = 0.

Пересечение графов G ₁= (V ₁, E ₁ ) и G ₂=(V ₂, E ₂) называется граф G ₃=(V ₁Ç V ₂, E ₁Ç E ₂).

Аналогично определяются объединение, дизъюнктное объединение и пересечение любого количества графов. Операции объединения и пересечения являются коммутативными, т.е. G ₁È G ₂ = G ₂È G ₁, а также G ₁Ç G ₂ = G ₂Ç G ₁

Пример. На ниже приведённом рисунке показаны: а) – граф G ₁, б) – граф G ₂, в) – их объединение, г) – пересечение.

б)

v ₂

v ₅

а)

v ₄

e ₂

e ₇

e ₁₀

v ₆

v ₅

e ₁₀

e ₆

e ₅

e ₉

e₃

e ₁

e ₈

v ₄

v₃

v ₂

v ₁

v ₆

v ₅

e ₆

e ₅

e ₉

e₃

e ₁

e ₈

v₃

v ₂

v ₁

v ₆

v ₅

e ₆

e ₅

e₃

v ₄

v₃

v ₁

в)

г)

v ₆

e ₆

e ₇

e ₅

e ₄

e₃

e ₁

e ₂

v ₄

v₃

v ₂

v ₁

Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей рёбра (дуги).

Удаление ребра (дуги). При удалении ребра (дуги) его концевые вершины не удаляются. Операцией обратной к операции удаления ребра является операция добавления ребра.

Слияние (отождествление) вершин. Говорят, что вершины v_i и v_j в графе G отождествляются (сливаются) если они заменяются новой вершиной v_k такой, что все ребра (дуги) графа инцидентные v_i и v_j становятся инцидентными к вершине v_k.

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

Подразбиение ребра. При выполнении этой операции из графа удаляется ребро (v_i, v_j) и добавляются два новых (v_i, v_k) и (v_k, v _i ), где v_k – новая вершина графа.

Пример:

На следующем рисунке представлены: а) - исходный граф, б) – граф после удаления вершины v ₃, в) - результат удаления ребра e ₂, г) –отождествления вершин v ₃ и v ₄, д) –стягивание ребра e ₁, е) – подразбиение ребра e ₂.

v ₆

e ₇

v ₅

v ₂

e ₂

e ₄

e ₅

v ₄

v ₄

v ₄

v ₂

v ₂

v ₂

e ₅

б)

а)

e ₅

e ₄

e ₃

e ₂

e ₁

v ₃

v ₁

e ₄

e ₃

v ₁

в)

e ₄

e ₃

e ₁

v ₃

v ₁

v ₂

г)

e ₅

e ₃

e ₁

v ₅

v ₁

v ₄

v ₂

е)

e ₅

e ₄

e ₃

e ₈

e ₁

v ₃

v ₁

e ₂

e ₄

д)

e ₅

e ₃

v ₁

Дата добавления: 2014-01-11