Лекции были перечислены способы задания графов. Рассмотрим способ задания графа с помощью матрицы смежности или матрицы инциденции

Лекция-15. Операции над графами. Способы задания графа. Матрица смежности и инциденции. Изоморфизм графов.
В предыдущей лекции были перечислены способы задания графов. Рассмотрим способ задания графа с помощью матрицы смежности или матрицы инциденции.
Матрица смежности - представляет собой квадратную таблицу размером , где
n – число вершин графа. На строках и столбцах матрицы записываются числа, соответствующие вершинам графа, а на пересечении строк и столбцов записываются
числа показывающие, сколько ребер соединяют соответствующую пару вершин.
Матрица смежности является транспонированной матрицей.

1 2 3 4 5 6 1 0 3 1 0 0 2 2 3 0 0 1 0 0 3 1 0 0 0 1 0 4 0 1 0 2 2 1 5 0 0 1 2 1 1 6 2 0 0 1 1 1

Рисунок 34. Псевдограф и соответствующая ей матрица смежности

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

Число ребер по матрице смежности определяется по следующей формуле:

По матрице смежности легко определить вид графа:

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

Матрица инциденции
Матрица инциденции представляет собой прямоугольную таблицу размером , где – соответствует числу вершин матрицы, а соответствует числу ребер. На строках матрицы записываются вершины, на столбцах матрицы записываются ребра.
Степень вершины
Р



исунок 35.

	{1,2}	{1,5}	{2,3}	{2,4}	{3,4}	{4,5}	{1,1}
1	1	1	0	0	0	0	2
2	1	0	1	1	0	0	0
3	0	0	1	0	1	0	0
4	0	0	0	1	1	1	0
5	0	1	0	0	0	1	0

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





Рисунок 37.
Однако одинаковое число вершин и одинаковые степени вершин не всегда говорят об изоморфизме графа.
Например:
Пусть даны графы с одинаковым числом вершин, в которых число вершин со степенью ноль, число вершин со степенью один, два и т.д. Но такие графы не всегда являются изоморфными (рис38)
Для проверки на изоморфность необходимо совершить попыток (перестановок), где число вершин, если хотя бы в одном из них графы будут выполнять или удовлетворять условию изоморфизма, то они изоморфны.


Рисунок 38.