Ориентированные графы

Определите тип графа.

Подсчитайте валентность вершин.

Матрицу смежности и матрицу инцидентности.

Постройте для графа G(V,E), заданного геометрически,

а) матрицу смежности; б) матрицу инцидентности.

0)

1)

2)

3)

4)

5)

6)

7)

8)

9)  

5.

7)

Постройте для графа G(V,E), заданного геометрически

		c
	a

f

d

b

9)

Ориентированный граф (или орграф) G₁ (V, E) – непустое конечное множество узлов (вершин) V и набор упорядоченных пар вершин (дуг) E.

Пусть v ₁, v ₂,... v_n - вершины графа G₁ (V, E), а e ₁, e ₂,... e_m - его дуги.

Матрицей смежности графа G₁ называется матрица A(G₁)= || a_ij ||, i =1,..., n; j = 1,..., n, у которой элемент a_ij равен числу дуг, соединяющих вершины v_i и v_j (соответственно, идущих из вершины v_i в вершину v_j).

Свойства матрицы смежности:

1) несимметричная, в общем случае, относительно главной диагонали,

2) значениями являются натуральные числа и ноль,

3) количество петель записывается на главной диагонали,

4) сумма значений по строке (столбце) равна валентности вершины.

Матрицей инцидентности для ориентированного графа с n вершинами и m дугами называется матрица В(G₁) = [b_ij], i=1, 2,..., n, j = 1,2,..., m, строки которой соответствуют вершинам, а столбцы - дугам. Ее элемент: b_ij=1, если дуга е_i выходит из вершины v_j; b_ij= -1, если дуга e_i входит в вершины v_j; b_ij=0, если вершина v_j не инцидентна дуге е_i.

Свойства матрицы инцидентности:

1) несимметричная, 2) значениями являются -1, ноль и 1.

Примеры выполнения заданий

1. Орграф G₁(V,E) задан геометрически. Постройте для орграфа:

а) матрицу смежности; б) матрицу инцидентности.

b

a

e

c

d

k

g

f

Решение а): матрица смежности А(G₁)=

Решение б): матрица инцидентности В(G₁)=

	a	b	c	d	e	g	f	k
		-1
			-1
	-1			-1			-1
					-1
						-1

Задания для самостоятельного выполнения

6.Орграф задан геометрически. Укажите валентность вершин.Постройте матрицу смежности орграфа.

0)

1)

2)

3)

4)

5)

6)

7)

8)    

9)

Дата добавления: 2014-12-16