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

Пример 2: Пусть дан сетевой граф:

Рис. 3

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

1) Графически (Рис 3).

2) С помощью задания двух множеств:

V = {1, 2, 3, 4, 5, 6} и Е= {(1, 2), (1, 3), (2, 5), (2, 4), (5, 6), (4, 4), (3, 4)}.

3) Матрицей инцидентности: Табл. 4

	а (1, 2)	b (1, 3)	d (2, 4)	e (2, 5)	c (3, 4)	g (4, 6)	f (5, 6)
1	-1	-1	0	0	0	0	0
2	1	0	-1	-1	0	0	0
3	0	1	0	0	-1	0	0
4	0	0	1	0	1	-1	0
5	0	0	0	1	0	0	-1
6	0	0	0	0	0	1	1

Особенностью графа является то, что начального события 1 только выходят, а в конечное 6 – только входят. Поэтому в первой строке единицы со знаком минус, а в последней - со знаком плюс.

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

Табл. 5

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

5) Список ребер:

Табл. 6

ребро	Вершины
а	(1, 2)
в	(1, 3)
с	(3, 4)
d	(2, 4)
e	(2, 5)
f	(5, 6)
g	(4, 6)

Пример 3: Задать различными способами графы G1, G2 (рис.4,5) соответственно.

Как вычислить число вершин и число ребер по матрицам и списку ребер? Сформировать правила переходов от описания графа списком ребер и матрице инцидентности и от матрицы смежности к списку ребер.

Матрицы инцидентности н – графа G1 и орграфа G2 приведены в таблице 7 и таблице 8. Список ребер – в таблице 9, матрицы смежности – в таблице 10.

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

Табл. 7

G1	I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	0	1	1	0	0	0
6	0	0	1	1	0	0	0
7	0	0	0	1	0	0	0
8	0	0	1	0	1	0	0
9	0	0	0	1	0	0	1
10	0	0	0	0	1	1	0
11	0	0	0	0	0	1	1

Табл. 8