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

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

Способы задания графа:

1) аналитический (в виде алгебраической системы);

2) геометрический (в виде произвольного рисунка);

3) матричный (в виде матриц смежности и инцидентности).

Пусть 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) значениями являются натуральные числа и ноль,

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

Решение с): матрица смежности

А=

матрица инцидентности

В=

	a	b	c	d

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

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

Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица В(G) = [b_ij], i=1, 2,..., n, j = 1,2,..., m, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент b_ij=1, если вершина v_i инцидентна ребру e_j и b_ij=0, если вершина v_i не инцидентна ребру e_j.

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

1) несимметричная,

2) значениями являются ноль и единица,

3) сумма значений по строке или в столбце равна 2, если нет петель.

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

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

Постройте:

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

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

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

e4

e1 e2 e3

e5 e3 e6

e7

Решение:

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

123456 123456

А(G) = В(G) =

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

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