Лабораторный Практикум по Дискрмат2

Вопросы для самопроверки

1.Определите понятие перестановки и перестановки с повторениями.

2.Определите понятие сочетания и сочетания с повторениями.

3.Чем отличаются перестановки от сочетаний?

4.Определите понятие производящей функции последовательности.

Литература: [2], Часть 3, с. 60 – 67; [7], гл. 9, стр. 351 –399. [12],

Задания для самостоятельной работы

1.Для данного слова A перечислить все различные перестановки букв слова и для слова B - перестановки с повторениями.

2.Для данного множества A перечислить все различные сочетания его элементов по k элементов. Для множества B перечислить все сочетания по k элементов с повторениями, в которых первый элемент множества может

встречаться не более k1 раз, второй элемент – не более k2 раза, третий элемент – не более k3 раза, четвертый элемент – не более k4 раза.

Вариант 1.

1)A= «башня»; B= «сессия».

2)A ={a, b, c, d, e, f, g}, k=3; B ={a, b, c, d}, k=5, k1 =2, k2 =2, k3 =3,

k4=1.

Вариант 2.

1)A= «музыка»; B= «студент».

2)A ={a, b, c, d, e, f}, k=4; B ={a, b, c, d}, k=3, k1 =2, k2 =4, k3 =4, k4=3.

Вариант 3.

1)A= «весна»; B= «гномон».

2)A ={a, b, c, d, e, f, g}, k=5; B ={a, b, c, d}, k=6, k1 =1, k2 =3, k3 =3, k4=4.

111

Вариант 4.

1)A= «песня»; B= «город».

2)A ={a, b, c, d, e, f, g}, k=6; B ={a, b, c, d}, k=4, k1 =3, k2 =3, k3 =1,

k4=3.

Вариант 5.

1)A= «танец»; B= «облако».

2)A ={a, b, c, d, e, f, g, h}, k=4; B ={a, b, c, d}, k=5, k1 =3, k2 =4, k3 =2,

k4=2.

Вариант 6.

1)A= «стрела»; B= «ворота».

2)A ={a, b, c, d, e, f}, k=2; B ={a, b, c, d}, k=6, k1 =2, k2 =3, k3 =4, k4=2.

Вариант 7.

1)A= «улица»; B= «ворона».

2)A ={a, b, c, d, e, f, g}, k=3; B ={a, b, c, d}, k=5, k1 =3, k2 =5, k3 =1,

k4=2.

Вариант 8.

1)A= «сироп»; B= «молоко».

2)A ={a, b, c, d, e, f }, k=4; B ={a, b, c, d}, k=6, k1 =2, k2 =3, k3 =3, k4=4.

Вариант 9.

1)A= «книга»; B= «топот».

2)A ={a, b, c, d, e, f, g}, k=5; B ={a, b, c, d}, k=3, k1 =3, k2 =4, k3 =4, k4=1.

Вариант 10.

1)A= «рябина»; B= «олово».

2)A ={a, b, c, d, e, g}, k=3; B ={a, b, c, d}, k=5, k1 =2, k2 =3, k3 =3, k4=4.

Вариант 11.

1)A= «столица»; B= «огород».

2)A ={a, b, d, e, f, g}, k=4; B ={a, b, c, e}, k=6, k1 =3, k2 =4, k3 =2, k4=2.

Вариант 12.

1)A= «дворник»; B= «космос».

2)A ={a, b, c, e, f, g}, k=5; B ={a, b, c, f}, k=4, k1 =2, k2 =2, k3 =3, k4=4.

Вариант 13.

1)A= «огурец»; B= «колонна».

2)A ={a, c, d, e, f, g}, k=3; B ={a, b, e, d}, k=7, k1 =4, k2 =1, k3 =2, k4=3.

112

1)A= «зарево»; B= «дерево».

2)A ={a, b, c, d, e, f, g, h}, k=6; B ={a, b, e, h}, k=7, k1 =2, k2 =3, k3 =3,

k4=4.

Вариант 23.

1)A= «свеча»; B= «золото».

2)A ={a, b, c, d, e, f, g}, k=3; B ={a, e, c, d}, k=8, k1 =4, k2 =3, k3 =4,

k4=2.

Вариант 24.

1)A= «цветок»; B= «зарница».

2)A ={a, b, c, d, e, f, g, h}, k=5; B ={a, b, c, h}, k=6, k1 =2, k2 =2, k3 =4,

k4=3.

Вариант 25.

1)A= «функция»; B= «шалаш».

2)A ={a, b, c, d, e, g}, k=6; B ={a, b, c, d}, k=5, k1 =3, k2 =5, k3 =2, k4=2.

Практическое занятие № 5

АЛГОРИТМЫ ПОСТРОЕНИЯ МИНИМАЛЬНОГО ОСТОВА ГРАФА. МЕТОД КРУСКАЛА. МЕТОД ПОЛНОГО ПЕРЕЧИСЛЕНИЯ ОСТОВОВ ГРАФА

Цель работы

При помощи метода Крускала определить остовов графа, имеющий минимальный суммарный вес. При помощи метода полного перечисления всех остовов найти все остовы, имеющие минимальный суммарный вес. Разработать программу, на одном из алгоритмических языков, реализующую алгоритм метода полного перечисления всех остовов данного графа и получить все минимальные остовы данного графа.

Краткая теория

Графом называется пара множеств V , E , где V - конечное

множество объектов или предметов, E - множество отношений между этими объектами или предметами. Обозначают элементы множества V строчными буквами или цифрами и называют вершинами графа. Граф называется ориентированным, если для всех ребер графа указаны их направления. В противном случае – называется неориентированным. Элементы множества E обозначаются упорядоченными парами элементов

114

множества V и называются ребрами графа. Например, V {1,2,3,4},

E {(1,2), (1, 3), (2, 4), (3,4)}.

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

Рис. 18. Геометрическая реализация графа: а) G = <V, E>; б) один из

остовов графа G.

Граф называется связанным, если для любой вершины графа существует маршрут, проходящий через ребра, к любой другой вершине графа. Остовом графа G называется связанный подграф графа G, не имеющий циклов и содержащий все вершины графа. Цикломатическим числом графа называется разность между числом ребер графа и числом вершин, увеличенная на одну единицу, то есть n m 1. Цикломатическое число равно числу ребер, которые необходимо удалить из данного графа, чтобы граф не имел циклов. Цепью или маршрутом называется последовательность ребер, соединяющая две вершины данного графа. Для каждого ребра графа может быть указан вес ребра или его длина. Тогда длина маршрута будет равна сумме длин ребер данного маршрута.

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

1.Составим последовательность из всех ребер данного графа, располагая ребра в порядке возрастания их весов (длин ребер).

2.Обозначим через V множество всех вершин данного графа и через W обозначим множество ребер, которое изначально будем считать пустым.

115

Во множество W будем включать элементы последовательности в порядке возрастания длины ребер и, одновременно, исключая вершины выбранных ребер из множества V.

3.Если на каком-то промежуточном шаге выполнения алгоритма окажется, что ни одна вершина выбранного ребра не входит во множество оставшихся вершин V, то такую вершину не включаем во множество ребер

W.

4.Алгоритм завершает работу, как только будут исчерпаны все вершины множества V. Составляя из полученных ребер граф, получим один из остовов. По построению, остов будет минимальной длины.

Метод Крускала не позволяет определить все остовы минимальной длины. Для некоторых задач может быть существенным определение всех минимальных остовов. В этом случае можно воспользоваться методом перечисления всех остовов, который заключается в выполнении следующего алгоритма:

1. Вычисляем цикломатическое число для данного графа n m 1.

2.Обозначим через E множество ребер данного графа и построим все выборки из множества E по элементов.

3.Среди графов, построенных для каждой выборки, будут, в частности,

ивсе остовы данного графа. Исключив подграфы, которые не являются остовами, получим все остовы данного графа.

4.Вычислим в веса остовов и найдем все остовы, имеющие минимальные веса.

Порядок выполнения работы

1.Для данного графа построить геометрическую реализацию и определить цикломатическое число.

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

3.При помощи метода полного перечисления всех остовов найти все остовы, имеющие минимальный суммарный вес всех маршрутов.

4.Разработать программу, на одном из алгоритмических языков, реализующую алгоритм метода полного перечисления всех остовов данного графа и получить, при помощи программы, все минимальные остовы данного графа.

Образец выполнения заданий

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

116

Рис.21. Остовы минимального веса.

Других остовов минимального веса не существует. Задача полного перечисления всех остовов требует достаточно большого объема вычислений. Поэтому, для ее решения в работе предполагается разработка алгоритмической программы и решение задачи при помощи этой программы.

Контрольные вопросы

1.Что называется графом?

2.Определите понятие геометрической реализации графа.

3.Определите понятия остова, веса остова.

4.Чем отличаются методы Крускала и метод полного перечисления остовов?

Литература: [2], Часть 5, с. 81 – 99; [7], гл. 4, стр. 88 –131. [6], гл. 2, стр.

108 –163.

Задания для самостоятельной работы

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

G = (V, E), V = {1, 2, 3, 4, 5, 6}, E = {a, b, c, d, e, f, g, h}.

Веса ребер приведены в заданиях.

120