Файл: Дискретная математика.pdf

42

Вариант 14

а) матрица инцидентности графа G1

диаграмма графа G2

7

6

б) последовательности вершин

1.(2, 6, 7, 1)

2.(4, 3, 2, 1, 6, 2)

3.(7, 1, 2, 6, 7)

4.(6, 2, 7, 1, 2, 6)

5.(3, 2, 6, 1, 2, 6, 7)

43

Вариант 15

а) диаграмма графа G1

3

2

4

1

5

матрица инцидентности графа G2

б) последовательности вершин

1.(3, 4, 1, 6, 7)

2.(5, 3, 4, 1, 6, 7, 1, 2)

3.(2, 3, 4, 1, 6, 7, 1, 2)

4.(6, 7, 1, 2, 6)

5.(1, 4, 3, 2, 1, 7, 6, 1)

44

Л а б о р а т о р н а я р а б о т а № 4.2

Циклы

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

Задания

1.Разработать и реализовать алгоритм генерации случайного графа, содержащего n вершин и m ребер.

2.Написать программу, которая:

а) в течение десяти секунд генерирует случайные графы, содер-

жащие n вершин и m ребер;

б) для каждого полученного графа определяет, является ли он эйлеровым или гамильтоновым;

в) подсчитывает общее количество сгенерированных графов и количество графов каждого типа.

Результат работы программы представить в виде таблицы (табл. 6).

3.Выполнить программу при n = 8,9,10 и сделать выводы.

4.Привести пример диаграммы графа, который является эйлеровым, но не гамильтоновым. Найти в нем все эйлеровы циклы.

5.Привести пример диаграммы графа, который является гамильтоновым, но не эйлеровым. Найти в нем все гамильтоновы циклы.

6.Привести пример диаграммы графа, который является эйлеровым и гамильтоновым. Найти в нем все эйлеровы и гамильтоновы циклы.

7.Привести пример диаграммы графа, который не является ни эйлеровым, ни гамильтоновым.

45

Л а б о р а т о р н а я р а б о т а № 4.3

Связность

Цель занятия: изучить алгоритм Краскала построения покрывающего леса, научиться использовать его при решении различных задач.

Задания

1.Реализовать алгоритм Краскала построения покрывающего леса.

2.Используя алгоритм Краскала, разработать и реализовать алгоритм решения задачи (см. варианты заданий).

3.Подобрать тестовые данные. Результат представить в виде диаграммы графа.

Варианты заданий

1.Найти все мосты в связном графе.

2.Найти минимальное множество ребер, удаление которых из связного графа делает его несвязным.

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

4.Получить все покрывающие деревья связного графа G = (V,E), исключая всеми способами |E| – |V| + 1 ребер графа.

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

1.Произвольно выбрать некоторую вершину v1 и ребро {v1,v2}, инцидентное вершине v1. Этому ребру присвоить номер 1. Перейти

ввершину v2.

2.Находясь в вершине vi, следует не выбирать ребро {vi,v1}, ес-

ли имеется возможность другого выбора.

3.Находясь в вершине vi, следует не выбирать ребро {vi,vj}, которое является мостом, если имеется возможность другого выбора.

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

6.Найти все множества вершин, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин.

7.Найти все k-элементные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты.

46

8.Найти все множества ребер, исключение которых из связного графа разбивает его на две связные компоненты, причем каждая компонента не содержит изолированных вершин.

9.Найти максимальное множество ребер, исключение которых из связного графа разбивает его на две связные компоненты.

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

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

12.Найти все точки сочленения в связном графе.

13.Найти все k-элементные множества вершин, исключение которых из связного графа разбивает его на две связные компоненты.

14.Найти максимальное множество вершин, исключение которых из связного графа разбивает его на две связные компоненты.

15.Найти все максимальные множества ребер, исключение которых из связного графа разбивает его на две связные компоненты.

Л а б о р а т о р н а я р а б о т а № 4.4

Кратчайшие пути во взвешенном орграфе

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

Задания

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

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

3.Подобрать тестовые данные. Результат представить в виде диаграммы графа.

Варианты заданий

1. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от заданной вершины не превосходит заданной величины. Вывести кратчайшие пути от заданной вершины до каждой из найденного множества и длины путей.

47

2.Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей от заданной вершины до всех остальных. Вывести кратчайшие пути от заданной вершины до каждой вершины орграфа.

3.Найти множество вершин взвешенного орграфа, от которых длина кратчайшего пути до заданной вершины превосходит заданную величину. Вывести кратчайшие пути от каждой из вершины из найденного множества до заданной вершины и длины путей.

4.Найти путь наименьшей длины во взвешенном орграфе от вершины x до вершины y, проходящий через вершину z. Вывести найденный путь и его длину.

5.Найти кратчайший путь во взвешенном орграфе от вершины x до вершины y, проходящий сначала через вершину v, а затем — через вершину w. Вывести найденный путь и его длину.

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

7.Во взвешенном орграфе найти путь между вершинами x и y, в котором длина кратчайшей дуги максимальна (временная метка вершины z — это длина кратчайшей дуги на пути от x до z). Вывести найденный путь и длины дуг этого пути.

8.Во взвешенном орграфе найти простой цикл наименьшей длины

сначальной вершиной v. Вывести найденный путь и его длину.

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

10. Определить, существуют ли во взвешенном орграфе две вершины, до которых длины кратчайших путей от заданной вершины одинаковы. Если существуют, то вывести кратчайшие пути от заданной вершины до найденных.

11. Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей до заданной вершины от всех остальных. Вывести кратчайшие пути от каждой вершины орграфа до заданной вершины.

12. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от первой заданной вершины равна длине кратчайшего пути от второй заданной вершины. Вывести найденное множество вершин, кратчайшие пути от заданных вершин до вершин найденного множества и длины этих путей.