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 не изоморфны. Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.