Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

< >,< >,< >, то матрица инцидентности будет иметь вид

.

Для того чтобы найти полустепени захода ^(v) вершины, необходимо в матрице инцидентности подсчитать количество «– 1» в строке этой вершины. Если же мы хотим найти ⁺(v), то необходимо в матрице инцидентности подсчитать количество +1 в строке этой вершины.

5.4. Матричное задание неориентированных графов

Неориентированный граф G(V, Q), где V={ ,..., } может быть задан квадратной матрицей смежности A = размерности , где – это число ребер, соединяющих вершины и , причем петли, "соединяющие" вершину с самой собой, считаются дважды.

Матрица смежности неориентированного графа симметрична относительно главной диагонали, т.е. A = . По главной диагонали для простых графов стоят нули, однако, если в вершине псевдографа находятся р петель, то на главной диагонали в строчке с номером k стоит число р. Если вершина i связана с вершиной j одним ребром, то элемент матрицы смежности a_ij равен единице, если эти вершины связаны s ребрами в мультиграфе, то а_ij= s.

Можно заметить, что матрица D = = АА составлена из целых чисел , которые равны числу путей длины 2, соединяющих вершины и . Матрица будет составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины в вершину .

Для простого неориентированного графа, изображенного на рис. 11, матрица смежности будет иметь вид

.

Неориентированный граф G(V, Q), где V={ ,..., }; Q={ ,..., } может быть задан матрицей инцидентности размерности n m, где n – число вершин, а m – число ребер графа. Элементы матрицы инцидентности B= равны 1, если ребро q_j инцидентно вершине i и не является ее петлей; равны 2, если q_j – петля при вершине vi, равны 0, если ребро q_j неинцидентно вершине v_i.

В матрице инцидентности сумма единиц в строке указывает на степень вершины .

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

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

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

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

Например, три графа, представленные на рис. 12, изоморфны, а графы на рис. 13 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.

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

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

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

Удаление вершины. При удалении вершины из графа удаляются не только сама вершина, но и все инцидентные ей ребра (дуги). Пример удаления центральной вершины v из графа приведен на рис.14.

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

Стягивание ребра (дуги). Эта операция означает удаление ребра и отождествление его концевых вершин. Граф G₁ называется стягиваемым к графу G₂, если граф G₂ может быть получен из G₁ в результате некоторой последовательности стягиваний ребер. На рис.15 указан исходный граф, а так же граф, полученный стягиванием ребра _.

Подразбиение ребра. С графической точки зрения эта операция означает «внесение в ребро новой вершины». Операция разбиения ребра проиллюстрирована на рис.16.

Рассмотрим алгебраические операции над графами.

О бъединение графов. Объединением графов и называется граф , множество вершин которого является объединением вершин графов и , а множество ребер – объединением множеств ребер и (рис.17).