Примеры выполнения заданий. Решение с): матрица смежности

1. Задан граф V=(1,2,3,4) Е=(a, b, c, d), Постройте граф и его матрицы смежности и инцидентности.
Решение с): матрица смежности А=	матрица инцидентности В=   a b c d

 

2. Графы G₁(V₁,E₁) и G₂(V₂,E₂) заданы геометрически.

Постройте:

а) для графаG₁(V₁,E₁) матрицу смежности,

б) для графаG₂(V₂,E₂) матрицу смежности и матрицу инцидентности.

 

Решение: Матрица смежности: Вершины графа v1v2v3v4   А(G) =

e1 e2 e3   e4 e5 e6 e7   Решение: Матрицы смежности и инцидентности: Вершины графа А(G) = В(G) =

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

Постройте для графа 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) задан геометрически. Постройте для орграфа:

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

e b a c d k g f	Решение а): матрица смежности А(G1)=
Решение б): матрица инцидентности В(G1)=   a b c d e g f k     -1                   -1             -1     -1     -1             -1                   -1

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

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

0)	1)
2)	3)
4)	5)
6)	7)
8)	9)

 

Дана матрица смежности орграфа. а) Задайте орграф геометрически, в) постройте матрицу инцидентности.

0) 1) 2) 3) 4)

5) 6) 7) 8) 9)

Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются.

 

Практическое занятие №3.
Комбинаторика.