Лекции по "Развитию операционных систем"

 

 

 

 

 

 

 

 

 

Решение.  1) Используя определение степени вершины графа, находим:

d(v1)=3, d(v2)=3,  d(v3)=4,   d(v4)=3,   d(v5)=2,   d(v6)=3.

 

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

Поскольку количество ребер, соединяющих первую вершину с первой равно 0 (в графе нет петель, соответствующих первой вершине), соединяющих первую со второй равно 1, первую с третьей равно 1, первую с четвертой равно 1, первую с пятой равно 0, первую с шестой равно 0, то первая строка матрицы имеет вид (0 1 1 1 0 0). Заполняя аналогично остальные строки, получаем матрицу вида:

.

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

 

 

 

 

 

 

 

 

 

Так как граф имеет девять ребер, то матрица смежности ребер является квадратной матрицей девятого порядка. Ребро u1 имеет общую вершину с ребрами u3 и u5, а также общую вершину с ребрами u2 и u4. Поэтому первая строка матрицы имеет вид    (0 1 1 1 1 0 0 0 0). Заполняем аналогично остальные строки, получаем матрицу вида:

.

 

Граф имеет шесть вершин и девять ребер, поэтому матрица инциденций является матрицей размерности 6´9. Поскольку вершина инцидентна ребрам , и , и не инцидентна остальным ребрам, то первая строка матрицы имеет вид (0 0 1 1 0 0 1 0 0). Остальные строки матрицы заполняем аналогично. Следовательно, матрица имеет вид:

.

 

3)  Для того, чтобы  найти число остовных деревьев, сначала составим матрицу Кирхгофа.

.

Используя теорему Кирхгофа, найдем, например, алгебраическое дополнение элемента .

=[четвертую и пятую строчки оставляем,

третью умножаем на (-1) и складываем со второй,

потом третью умножаем на 3 и складываем с первой]=

 

.

Таким образом, для данного графа можно построить 64 остовного дерева.

 

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

 

 

 

 

 

 

 

 

 

 

Используем для построения остовного дерева алгоритм В графе выбираем ребро с минимальным весом. В нашем случае это ребро, соединяющее вершины и с весом, равным 4. Пусть, например, вершина будет корнем дерева. Далее выбираем ребра, инцидентные вершинам , и имеющие минимальный вес. Таким является ребро с весом 5, соединяющее вершины и . Включаем его в строящееся дерево. Затем к вершине присоединяем ребро с весом 7, соединяющее вершины и . К вершине присоединяем ребро с весом 7, соединяющее вершины и . И в заключение, к вершине присоединяем ребро с весом 6, соединяющее вершины и . Таким образом, получаем минимальное остовное дерево (рис. 1). Минимальный вес построенного дерева равен: wmin(T)=4+5+7+7+6=29.

Так как мы в качестве корня дерева выбрали вершину , то высота дерева будет равна h(T)=4.

Замечание. Если бы в качестве корня выбрали вершину , то высота дерева была бы равна h(T)=5.

 

ИЛИ

 

Построим минимальное корневое остовное дерево данного взвешенного графа с помощью алгоритма Прима. Выбираем вершину , которая будет корнем дерева. Из трех ребер, которые инцидентны вершине , выбираем те, что имеют наименьший вес. Два ребра с весом, равным 7, инцидентны вершине . Присоединяем эти ребра к выбранной вершине. К вершине присоединяем ребро с весом 5, соединяющее вершины и . К вершине присоединяем ребро с весом 4, соединяющее вершины и . К вершине присоединяем ребро с весом 6, соединяющее вершины и .Таким образом, получаем следующее минимальное корневое дерево с весом, равным wmin(T)=7+7+6+5+4=29. Высота построенного дерева равна h(T)=3.

 

Ответ. 1) d(v1)=3, d(v2)=3, d(v3)=4, d(v4)=3, d(v5)=2, d(v6)=3;

             3)  число остовных деревьев  равно 64;

             4) минимальный вес дерева равен wmin(T)=29, высота равна h(T)=4.