Задание 7.

Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины.

Решение:

1. Определим расстояние между всеми парами вершин:

d(x₁,x₂) = 1

d(x₁,x₃) = 2 d(x₂,x₃) = 1

d(x₁,x₄) = 1 d(x₂,x₄) = 1 d(x₃,x₄) = 1

d(x₁,x₅) = 2 d(x₂,x₅) = 2 d(x₃,x₅) = 1 d(x₄,x₅) = 1 .

2. Определим диаметркак d(G) = max d(x_i,x_j): d(G) = 2.

3. Определим эксцентриситет каждой вершины:

r(x₁) = 2 r(x₂) = 2 r(x₃) = 2 r(x₄) = 1 r(x₅) = 2 .

4. Определим радиус графа как r(G) = min r(x_i) : r(G) = 1 .

5. Определим центральные вершины: х₄.

Задание 8.

Используя метод Магу, определить совокупность максимальных внутренне устойчивых множеств вершин, семейство минимальных внешне устойчивых множеств вершин заданного графа, а также ядро графа.

Решение:

1. Определим совокупность максимальных внутренне устойчивых множеств вершин[3]:

Примечание: Y’i – отрицание Yi, опустим символ &.

&_aij=1(Y’i Ú Y’j) = (Y’2 Ú Y’1)(Y’2 Ú Y’3)(Y’2 Ú Y’4)(Y’4 Ú Y’1)(Y’4 Ú Y’3)& &(Y’4ÚY’5) &(Y’5ÚY’3)º

(используя (10.6) из пособия [3])

º Y’1 Y’3Y’4 Ú Y’2Y’4Y’5Ú Y’2Y’3Y’4 Ú Y’1 Y’2Y’3Y’5 .

Следовательно, искомыми внутренне устойчивыми множествами вершин данного орграфа являются U1 = {x₂,x₅}, U2 = {x₁,x₃}, U3 = {x₁,x₅}, U4 = {x₄}при этом U1,U2, U3 – являются максимальными.

2. Определим совокупность минимальных внешне устойчивых множеств [3]:

&_i=1,n(Yi Ú Ú_{aij =1} Yj) = Y1 (Y2Ú Y1 Ú Y3 Ú Y4) Y3 ( Y4 Ú Y3 Ú Y5 Ú Y1) (Y5Ú Y3)º ( используя закон поглощения, равносильности (10.6) из пособия [3] ) ºY1Y3 .

Следовательно, искомым минимальным внешне устойчивым множеством данного графа являются множество {x₁,x₃}.

3. Определим ядро графа:

Поскольку множество {x₁,x₃} одновременно является минимальным внешне устойчивым и максимальным внутренне устойчивым, то оно является ядром.

Задание 9.

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

Решение:

Граф называется эйлеровым, если содержит замкнутый эйлеров цикл, для этого степени исхода каждой вершины должны быть равны степеням захода каждой вершины.

Данный граф не является эйлеровым, поскольку не выполняется условие равенства степеней захода и исхода каждой вершины (см. задание 2).

Преобразуем данный граф в эйлеров граф:

Х2 Х3