Методические рекомендации (стр. 7 )

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

Список ребер графа является сокращенным представлением матрицы инцидентности (в каждой ее строке только два элемента отличны друг от 0 или один, если ребро – петля).

Построение матрицы инцидентности по списку ребер:

Каждая строка списка соответствует строке матрицы с тем же номером. Для н – графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1. Для орграфа в этой строке первым стоит номер элемента, равного 1. При совпадении номеров в строке списка ребер в названном элементе строки матрицы инцидентности проставляется, например, 2.

Построение по матрице смежности списка ребер:

Элементу матрицы, расположенному в iой строке и jом столбце, соответствует строк списка ребер (при = 0 ни одной строки), в каждой из которых записаны номера i и j. Для Н – графа эти строки соответствуют только элементам верхнего правого треугольника матрицы смежности, т. е. элементам с , а для орграфа нужно рассматривать все элементы все элементы .

Примеры:

1) Даны графы

 

Рис. 1

Задать граф G1, представленный на рис. 1, через множества вершин V1, и ребер Е1.

Решение: Граф G1 может быть полностью определен:

·  двумя множествами – поименованных вершин и поименованных ребер ;

·  множеством ребер, каждое из которых представлено парой своих концевых вершин .

Порядок указания вершин безразличен, т. к. все ребра в графе G1 неориентированные.

2) Задать графы G2 – G3 (рис.1) множествами их вершин и рёбер. Сравнить G1 – G3 .

3) Равны ли графы G1 – G2 (рис.2).

Задать графы G1 – G3 множествами их вершин и рёбер. Сравнить графы.

4) Определить дополнение графа , если:

а) G – пятиугольник;

б) G – треугольник.

Какой ориентированный граф соответствует графу G (представить графически)?

G

 

5) Даны графы

 

Рис. 3

Определить, изоморфны ли графы G1, G2, изображенные на рис. 3.

Решение: В первом G1 и во второмG2 графах |V1| = |V2| = 5, |E1| = |E2| = 7.

Построим для этих графов матрицы инцидентности и смежности, а также список рёбер.

Матрица инцидентности:

Табл. 1

G1	a	b	c	d	e	F	g
1	1	0	0	0	0	1	0
2	1	1	1	0	0	0	0
3	0	0	1	1	1	0	0
4	0	0	0	0	0	1	1
5	0	0	0	0	1	0	1

G2	a	b	c	d	e	F	g
1	1	0	0	0	1	1	0
2	1	1	0	0	0	0	0
3	0	1	1	0	0	0	0
4	0	0	1	1	0	0	0
5	0	0	0	1	0	1	1

Матрица смежности:

Табл. 2

G1	1	2	3	4	5
1	0	1	0	1	0
2	1	1	1	0	0
3	0	1	1	0	1
4	1	0	0	0	1
5	0	0	1	1	0

G2	1	2	3	4	5
1	1	1	0	0	1
2	1	0	1	0	0
3	0	1	0	1	0
4	0	0	1	0	1
5	1	0	0	1	1

Список рёбер: