Теория.

Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству.

Частичный граф (суграф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер.

1) Граф G1 (рис. 1.1) является подграфом графа G (рис. 1).

Рис. 1.1

2) Граф G2 (рис. 1.2) является суграфом графа G (рис. 1).

Рис. 1.2

Задание № 4

Выполнить бинарные операции над графами ( , ∩,).

1) Граф G1 (рис. 1.1) является подграфом графа G (рис. 1).

Рис. 1.1

Матрица смежности графа G1:

2) Граф G2 (рис. 1.2) является суграфом графа G (рис. 1).

Рис. 1.2

Матрица смежности графа G2:

Объединение G3 = G1 G2 :

Пересечение G4 = G1∩ G2:

Задание № 5

Определить аналитическим способом число маршрутов длины L = 3 для каждой пары вершин графа своего варианта.

Теория.Для определения маршрутов длины L=3 в графе его матрицу смежности возводят в степень, равную L. Тогда для каждого значения степени L значение элемента матрицы определяет количество маршрутов длиной L. В нашем случае возводим матрицу R в куб.

R:

R³:

Каждый r_i,j-й элемент матрицы R³ равен числу маршрутов длиной 3, ведущих из вершины x_i в x_j.

Начало формы

Конец формы

Задание № 6

Построить все маршруты длины L = 3 между вершинами, указанным преподавателем.

Рассмотрим вершины х3 и х5. r_3,5= 6 означает, что в графе 6 маршрутов длины L=3 , ведущих из x₃ в x₅ :

S₁ = (x₃,u₁,x₁,u₄,x₄,u₉,x₅)

S₂ = (x₃,u₁,x₁,u₄,x₄,u₁₀,x₅)

S₃ = (x₃,u₁,x₁,u₄,x₄,u₁₁,x₅)

S₄ = (x₃,u₃,x₁,u₄,x₄,u₉,x₅)

S₅ = (x₃,u₃,x₁,u₄,x₄,u₁₀,x₅)

S6 = (x₃,u₃,x₁,u₄,x₄,u₁₁,x₅)

Задание № 7

Построить метрику графа своего варианта (рис.1). Определить радиус, диаметр графа, периферийные и центральные вершины.

Решение:

1. Задаём матрицу метрики M=(m_i,j)_nxn. Размерность матрицы M равна размерности матрицы R. Все элементы mi,j матрицы M не определены.

2. Начальное значение степени k матрицы S равно 1: k=1. Главной диагонали матрицы M присваиваем значения 0.

3. Всем элементам m_i,j, значения которых не определены, присвоить значение степени k, если соответствующие им элементы матрицы S^k ≠ 0.

4. Проверяем, в матрице M имеются элементы m_i,j, значения которых еще не определены? Если такие элементы имеются, то переходим к шагу 4; в противном случае – к шагу 7.

5. Повышаем степень k матрицы R: k=k+1.

6. Проверяем, является ли матрица R^k-1 устойчивой. Если матрица R^k-1 – неустойчивая, то переходим к пункту 3. Иначе – переходим к пункту 7.

7. Всем элементам m_i,j матрицы M, значения которых остались неопределёнными, присваиваем значение бесконечность.

8. Матрица метрики M=(m_i,j)

Булевская матрица смежности R=

Единичная матрица E=

Полученная суммарная матрица S=R+E:

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

Возведём матрицу S с обнулённой главной диагональю в степень 1 и заменим все элементы неравные 0 на 1.Все остальные элементы остаются неопределёнными. Это и есть фундамент матрицы метрики.

М1:

При последовательном возведении матрицы в степень получаем соответствующую матрицу метрики:

М2:

М3:

В полученной матрице метрики не осталось неопределенных мест, значит, она построена.

Определим радиус, диаметр, центральные и периферийные вершины.

Матрица метрики и максимальные значения элементов

Наибольшее из значений – диаметр графа D=3.

Наименьшее из значений – радиус графа R=2.

Вершины, имеющие наибольшую удаленность равную диаметру, называются периферийными.

Периферийные вершины: х2, х5, х7.

Вершины, имеющие наибольшую удаленность равную радиусу, называются центральными.

Центральные вершины: х1, х3, х3, х6.