Контрольная по дискретной математике. Контрольная решение полное. Решение. Задание 2 Изобразить множество d с помощью кругов Эйлера. (А B) (A C)

• Название: Решение. Задание 2 Изобразить множество d с помощью кругов Эйлера. (А B) (A C)
• Анкор: Контрольная по дискретной математике
• Дата: 10.11.2019
• Размер: 1.61 Mb.
• Имя файла: Контрольная решение полное.doc
• Тип: Решение; #94328
• страница: 15 из 18

Задание № 2

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

:
Решение.

Радуис графа: 2 (1⇒3⇒4). Диаметр графа: 3 (3⇒1⇒8⇒7).

Рассчитаем степени вершин



Граф не является эйлеровым, так степень первой вершины равна 3.

Граф незамкнутый. Поэтому нет системы фундаментальных циклов, полностью его покрывающих.

Задание № 3

Для графа G , заданного матрицей весов, построить минимальный по весу остов G' и найти его вес ω(G').



Решение.

Построим граф



Минимальный остов найдем с помощью алгоритма Краскала.

Алгоритм Краскала изначально помещает каждую вершину в своё дерево, а затем постепенно объединяет эти деревья, объединяя на каждой итерации два некоторых дерева некоторым ребром. Перед началом выполнения алгоритма, все рёбра сортируются по весу (в порядке неубывания). Затем начинается процесс объединения: перебираются все рёбра от первого до последнего (в порядке сортировки), и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву, и ответ найден.



G' = (3,1), (5,4), (4,2), (6,1), (6,4), (7,5). Вес этого остова равен 33.