Прямым (декартовым) произведением графов G1(x1,г1x1) и G2(x2,г2x2) называется граф G(x,гx), для которого X=X1 X2 и гx=г1x1 г2x2.
Пример.
Найти декартово произведение графов G1 и G2 (рис. 3.1.16):
Рис. 3.1.16.
Обозначим каждую получившуюся вершину через , тогда
Геометрическая реализация графа G имеет вид (рис. 3.1.17):
Рис. 3.1.17
Матрицы для графов
Матрицей смежности данного графа G(x,гx) называется квадратная матрица порядка n, где n – мощность множества X, элемент которой определяется следующим образом:
aij =
Для графа, две вершины которого соединены не более чем одной дугой одного направления, матрица смежности состоит из единиц и нулей (K=1). В дальнейшем будем рассматривать только такие графы.
Рис. 3.1.18
Пример.
Граф, изображенный на рис. 3.1.18, имеет следующую матрицу смежности:
Полустепень исхода вершины xi равна числу единиц, стоящих в i-й строке. Полустепень захода равна числу единиц, стоящих в i-м столбце. Найдя сумму полустепеней i-й вершины, можем определить ее степень по матрице смежности. Так,
|
|
P(x2)=P++P-=1+3=4
Единицы, стоящие на главной диагонали матрицы смежности, соответствуют петлям при данной вершине.
Изолированной вершине соответствуют строка и столбец, состоящие из нулей.
Число единиц в матрице смежности равно числу дуг графа.
Транспонированной матрице смежности соответствует граф с противоположной ориентацией.
Матрица смежности полностью задает ориентированный граф. Любая квадратная матрица, состоящая из единиц и нулей, может быть рассмотрена как матрица смежности, задающая некоторый граф G.
Рис. 3.1.19 |
Так, матрице M и соответствует граф, изображенный на рис.3.1.19.
Операции над графами с помощью матриц смежности. Если следует найти объединение или пересечение графов, заданных их матрицами смежности, можно выполнить эти операции, не прибегая к аналитической записи графа или его геометрической реализации.
Пример.
Напишем матрицы смежности A и B графов G1 и G2 (рис.3.1.14), над которыми произведем операции сложения и умножения
,
а также матрицы смежности С и D для графа, являющихся их объединением (рис. 3.1.15) и пересечением (рис. 3.1.16)
,
Рассмотренный пример иллюстрирует то обстоятельство, что матрица смежности для графа суммы есть булева сумма матриц смежности складываемых графов: 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, т.е. матрица смежности графа-пересечения содержит единицы только в качестве тех элементов, которые равны единицам в обеих матрицах смежности перемножаемых графов.
|
|
Матрица инциденций
Матрицей инциденций ориентированного графа G (x, u) называется прямоугольная матрица порядка [n * m], где n – мощность множества X, m – мощность множества U, каждый элемент которого aij определяется следующим образом:
если xi – начало дуги ui | |
если xi – конец дуги ui | |
если xi – не инцидентна дуге ui |
Пример.
Напишем матрицу инциденций для графа, изображенного на рис. 3.1.20.
Рис. 3.1.20
Для этого пронумеруем дуги: u1,u2,…,u6, матрица инциденций будет иметь следующий вид: