Матрицы для графов.

 

Матрицей смежности данного графа G(x,гx) называется квадратная матрица порядка n, где n – мощность множества X, элемент которой определяется следующим образом:

aij =

Для графа, две вершины которого соединены не более чем одной дугой одного направления, матрица смежности состоит из единиц и нулей (K=1). В дальнейшем будем рассматривать только такие графы.

Рис. 18.

Пример.

Граф, изображенный на рис.3.1.18, имеет следующую матрицу смежности:

Полустепень исхода вершины xi равна числу единиц, стоящих в i-й строке. Полустепень захода равна числу единиц, стоящих в i-м столбце. Найдя сумму полустепеней i-й вершины, можем определить ее степень по матрице смежности. Так,

P(x2)=P++P-=1+3=4

Единицы, стоящие на главной диагонали матрицы смежности, соответствуют петлям при данной вершине.

Изолированной вершине соответствуют строка и столбец, состоящие из нулей.

Число единиц в матрице смежности равно числу дуг графа.

Транспонированной матрице смежности соответствует граф с противоположной ориентацией.

Матрица смежности полностью задает ориентированный граф. Любая квадратная матрица, состоящая из единиц и нулей, может быть рассмотрена как матрица смежности, задающая некоторый граф G.

Рис. 19

 

Так, матрице M и соответствует граф, изображенный на рис.3.1.19.

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

Пример.

Напишем матрицы смежности A и B графов G1 и G2 (рис.3.1.14), над которыми произведем операции сложения и умножения

,

а также матрицы смежности С и D для графа, являющихся их объединением (рис. 3.1.15)

,

Рассмотренный пример иллюстрирует то обстоятельство, что матрица смежности для графа суммы есть булева сумма матриц смежности складываемых графов: cij=aij+bij, причем 0+0=0; 0+1=1; 1+0=1; 1+1=1.

Матрица смежности для графа-пересечения может быть получена поэлементным умножением dij=aij+bij, причем 0*1=0; 1*0=0; 0*0=0; 1*1=1, т.е. матрица смежности графа-пересечения содержит единицы только в качестве тех элементов, которые равны единицам в обеих матрицах смежности перемножаемых графов.

 








Дата добавления: 2016-01-26; просмотров: 1855;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.007 сек.