ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с

• Название: В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
• Дата: 12.09.2022
• Размер: 4.33 Mb.
• Имя файла: ДИСКРЕТНАЯ МАТЕМАТИКА (1).pdf
• Тип: Реферат; #673155
• страница: 20 из 25

Варианты заданий
1. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от заданной вершины не превосходит заданной величины. Вывести кратчайшие пути от заданной вершины до каждой из найденного множества и длины путей.
2. Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей от заданной вершины до всех остальных. Вывести кратчайшие пути от заданной вершины до каждой вершины орграфа.
3. Найти множество вершин взвешенного орграфа, от которых длина кратчайшего пути до заданной вершины превосходит заданную величину. Вывести кратчайшие пути от каждой из вершины из найденного множества до заданной вершины и длины путей.
4. Найти путь наименьшей длины во взвешенном орграфе от вершины до вершины y, проходящий через вершину z. Вывести найденный путь и его длину.
5. Найти кратчайший путь во взвешенном орграфе от вершины x до вершины y, проходящий сначала через вершину v, а затем — через вершину. Вывести найденный путь и его длину.
6. Найти кратчайший путь во взвешенном орграфе от вершины x до вершины y, содержащий в себе вершины v ив любом порядке. Вывести найденный путь и его длину.

240 7. В орграфе заданы вероятности успешного прохождения дуг. Вероятность успешного прохождения пути определяется как произведение вероятностей составляющих его дуг. Найти наиболее надежный (имеющий наибольшую вероятность успешного прохождения) путь от вершины до вершины y . Вывести путь и вероятность успешного его прохождения. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от первой заданной вершины больше, чем длина кратчайшего пути от второй заданной вершины. Вывести найденное множество вершин, кратчайшие пути от заданных вершин до вершин найденного множества и длины этих путей.
9. Во взвешенном орграфе найти путь между вершинами x ив котором длина кратчайшей дуги максимальна (временная метка вершины
z — это длина кратчайшей дуги на пути от x до z). Вывести найденный путь и длины дуг этого пути.
10. Во взвешенном орграфе найти простой цикл наименьшей длины с начальной вершиной v. Вывести найденный путь и его длину.
11. Во взвешенном орграфе найти путь наименьшей длины между двумя вершинами, проходящий по заданной дуге. Вывести найденный путь и его длину.
12. Во взвешенном орграфе найти простой цикл наименьшей длины из вершины А, проходящий через вершину В. Вывести найденный цикли его длину.
13. Во взвешенном орграфе найти путь наименьшей длины между двумя вершинами, проходящий по заданной дуге дважды. Вывести найденный путь и его длину.
14. Определить, существуют ли во взвешенном орграфе две вершины, до которых длины кратчайших путей от заданной вершины одинаковы. Если существуют, то вывести кратчайшие пути от заданной вершины до найденных.
15. Найти во взвешенном орграфе вершину, до которой есть хотя бы два пути наименьшей длины от заданной вершины. Вывести длину кратчайшего пути от заданной вершины до найденной и два пути этой длины между ними.
16. Найти вершину взвешенного орграфа, через которую проходит наибольшее число кратчайших путей до заданной вершины от всех остальных. Вывести кратчайшие пути от каждой вершины орграфа доза- данной вершины.
17. Во взвешенном орграфе найти путь наименьшей длины между двумя вершинами, не проходящий по заданной дуге. Вывести найденный путь и его длину.

241 18. Найти множество вершин взвешенного орграфа, до которых длина кратчайшего пути от первой заданной вершины равна длине кратчайшего пути от второй заданной вершины. Вывести найденное множество вершин, кратчайшие пути от заданных вершин до вершин найденного множества и длины этих путей.
19. Найти путь наименьшей длины во взвешенном орграфе от вершины до вершины y, проходящий через вершину z. Вывести найденный путь и его длину. Практическое занятие 4.7 Анализ алгоритмов поиска кратчайших путей во взвешенном орграфе между каждой парой вершин Цель занятия изучить алгоритмы поиска кратчайших путей во взвешенном орграфе между каждой парой вершин и выполнить их сравнительный анализ. Задания
1. Разработать и реализовать алгоритм построения случайного слабо связного взвешенного орграфа с заданным числом вершин n и дуг m.
2. Реализовать алгоритмы поиска кратчайших путей во взвешенном орграфе между каждой парой вершин
1. Алгоритм Дейкстры.
2. Алгоритм Шимбелла.
3. Алгоритм Флойда.
3. Разработать и написать программу, которая генерирует 100 случайных слабо связных взвешенных орграфов с заданным числом вершин и дуг m, для каждого орграфа находит кратчайшие пути между каждой парой вершин тремя алгоритмами и определяет время выполнения каждого алгоритма. Выполнить программу при n = 8, 9 и 10. Результат для каждого n представить в виде таблицы (табл. Таблица 4.9 Время выполнения алгоритмов Количество дуг в графе
(n
2
+ 3n) / 6
n
2
/ 3
(n
2
– n) / 2
min среднее max min среднее max min среднее max Алгоритм Дейкстры Алгоритм Шимбелла Алгоритм Флойда

242 Практическое занятие 4.8 Кратчайшие пути между каждой парой вершин во взвешенном орграфе Цель занятия:изучить алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе, научиться использовать их при решении различных задач. Задания
1. Изучить алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе.
2. Разработать и реализовать алгоритм решения задачи (см. варианты заданий.
3. Подобрать тестовые данные. Результат представить в виде диаграммы графа.
Варианты заданий
1. Во взвешенном орграфе найти все пары вершин v
i и v
j
, такие, что кратчайшее расстояние от v
i до v
j
равно кратчайшему расстоянию от v
j до v
i
. Вывести кратчайшие пути между найденными парами вершин.
2. Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей минимальной стоимости.
3. Во взвешенном орграфе найти все такие вершины v
i
, что сумма кратчайших расстояний от всех вершин орграфа до v
i
равна сумме кратчайших расстояний от v
i
до всех вершин орграфа.
4. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней медианой, и внутренним центром. Привести пример орграфа с такой вершиной.
5. Во взвешенном орграфе найти все такие вершины v
i
, что кратчайшее расстояние от самой удаленной вершины орграфа до v
i
равно кратчайшему расстоянию от v
i
до самой удаленной от нее вершины.
6. Используя алгоритм нахождения кратчайших расстояний между каждой парой вершин в орграфе определить а) является ли заданный орграф сильно связным б) является ли заданный орграф односторонне связным.

243 7. Найти все внешние, внутренние и внешне-внутренние центры взвешенного орграфа. Привести примеры орграфов, которые имеют более одного центра каждого вида.
8. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит заданное число дуг.
9. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешней, и внутренней медианой. Привести пример орграфа с такой вершиной.
10. Во взвешенном орграфе найти все пары вершин v
i и v
j
, такие, что кратчайшее расстояние от v
i до v
j
меньше кратчайшего расстояния от v
j до v
i
. Вывести кратчайшие пути между найденными парами вершин.
11. Дерево кратчайших путей назовем покрывающим, если все вершины взвешенного орграфа принадлежат дереву. Сумму длин дуг дерева назовем стоимостью. Построить все покрывающие деревья кратчайших путей максимальной стоимости.
12. Во взвешенном орграфе найти все такие вершины v
i
, что сумма кратчайших расстояний от всех вершин орграфа до v
i
меньше суммы кратчайших расстояний от v
i
до всех вершин орграфа.
13. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешним центром, и внутренней медианой. Привести пример орграфа с такой вершиной.
14. Во взвешенном орграфе найти все такие вершины v
i
, что кратчайшее расстояние от самой удаленной вершины орграфа до v
i
меньше кратчайшего расстояния от v
i
до самой удаленной от нее вершины.
15. Найти множество вершин во взвешенном орграфе, внешние и внутренние передаточные числа которых совпадают.
16. Найти все внешние, внутренние и внешне-внутренние медианы взвешенного орграфа. Привести примеры орграфов, которые имеют более одной медианы каждого вида.
17. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит не более заданного числа дуг.
18. Найти множество вершин во взвешенном орграфе, числа внешнего и внутреннего разделения которых совпадают.
19. Определить, есть ли в заданном взвешенном орграфе вершина, которая является и внешними внутренним центром. Привести пример орграфа с такой вершиной.
20. Найти все пары вершин взвешенного орграфа, кратчайший путь между которыми содержит более заданного числа дуг.

244 Контрольные вопросы и задания
1. Дайте определение графа, орграфа, псевдографа, мультиграфа, ги- перграфа, взвешенного графа. Что такое степень вершины, полустепень исхода и полустепень захода Дайте определение понятиям смежности и инцидентности.
2. Что такое матрица смежности и матрица инцидентности? Предложите различные способы хранения взвешенных графов и орграфов в памяти ЭВМ. Разработайте алгоритмы преобразования одного способа хранения графа в другой.
3. Какие графы называются изоморфными Сколько существует графов, изоморфных заданному Разработайте алгоритмы проверки изоморфизма двух графов.
4. Дайте определение маршрута, цепи, простой цепи. Опишите алгоритмы получения всех маршрутов, цепей и простых цепей заданной длины. Как можно подсчитать количество маршрутов заданной длины между каждой парой вершин графа
5. Что называется расстоянием между заданными вершинами, эксцентриситетом вершины, диаметром и радиусом графа Какая вершина графа называется переферийной, центральной Что называется центром графа Какая цепь называется диаметральной
6. Дайте определение цикла и простого цикла. Опишите алгоритм получения всех простых циклов в графе.
7. Какой цикл называется гамильтоновым? Как определить, является ли граф гамильтоновым? Какой цикл называется эйлеровым? Как определить, является ли граф эйлеровым? Опишите алгоритмы получения всех гамильтоновых и эйлеровых циклов.
8. Какой граф называется связным
9. Что такое матрица связанности вершин Как ее вычислить
10. Что называется мостом, точкой сочленения, разрезом, реберной и вершинной связностью
11. Дайте определение дереву и лесу. Какими свойствами обладают дерево и лес
12. Что такое лист и корень дерева Сколько корней может иметь дерево Докажите.
13. Сколько различных деревьев можно построить на n вершинах Докажите.
14. Дайте определение покрывающему дереву и покрывающему лесу. Сколько ребер нужно удалить из связного графа, чтобы получить покрывающее дерево Сколько ребер нужно удалить из несвязного графа, чтобы получить покрывающий лес

245 15. Опишите алгоритм Краскала. Что такое букет
16. Опишите алгоритм формирования всех покрывающих деревьев связного графа.
17. Как определяется стоимость покрывающего дерева взвешенного графа Опишите алгоритмы построения покрывающего дерева минимальной стоимости.
18. Что называется поиском в орграфе Опишите алгоритмы поискав глубину ив ширину.
19. Какие виды связности существуют в орграфе
20. Дайте определения отношениям достижимости, контрдостижи- мости и взаимодостижимости вершин орграфа.
21. Что называется компонентой сильной связности орграфа Опишите алгоритм нахождения компонент сильной связности орграфа.
22. Что называется конденсацией орграфа Что называется базой и антибазой орграфа
23. Что называется кратчайшим путем и кратчайшим расстоянием между двумя вершинами во взвешенном орграфе Опишите алгоритмы нахождения кратчайших путей между заданной парой вершин во взвешенном орграфе.
24. Что такое дерево кратчайших путей Как его построить
25. Опишите различные алгоритмы нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе.
26. Что называется числом внешнего, внутреннего и внешне- внутреннего разделения вершины Что называется внешним, внутренними внешне-внутренним центром взвешенного орграфа
27. Что называется внешним, внутренними внешне-внутренним передаточным числом вершины во взвешенном орграфе Что называется внешней, внутренней и внешне-внутренней медианой взвешенного орграфа. Дайте определение клики, максимальной клики и наибольшей клики. Опишите алгоритмы поиска всех максимальных клики наибольшей клики.
29. Дайте определение независимому множеству вершин, максимальному и наибольшему независимому множеству. Установите связь между кликами и независимыми множествами вершин.
30. Что такое раскраска графа, правильная раскраска, хроматическое число, минимальная раскраска
31. Опишите алгоритм получения всех раскрасок графа в число цветов, не превышающее заданного.
32. Опишите алгоритм получения минимальной раскраски.

246
5. БУЛЕВЫ ФУНКЦИИ
5.1. Табличные способы задания булевых функций Функция f, зависящая от переменных x
1
, x
2
, …, x
n
называется булевой, или переключательной, если функция и любой из ее аргументов x
i
,
i = (1, … , n) принимают значения только из множества {1, 0}. Аргументы булевой функции также называется булевыми. Произвольная булева функция может быть задана табличным способом. При таком способе булева функция f(x
1
, …, x
n
) задается таблицей истинности (табл. 5.1), в левой части которой представлены всевозможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах. Под двоичным набором y = (y
1
, y
2
, … , y
n
),
y
i

{1, 0} понимается совокупность значений аргументов x
1
, x
2
, …, булевой функции f. Двоичный набор имеет длину n, если он представлен цифрами из множества {0, 1}. Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x
1
, x
2
,…, в порядке возрастания их индексов. Тогда любой двоичный набор
y = (y
1
, y
2
, … , y
n
), y
i

{1, 0} можно рассматривать как двоичное число, называемое номером набора у. Например, двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл. 5.2).
Таблица 5.1 Таблица 5.2 Таблица истинности Таблица истинности
x
1
x
2
x
3
f Номер набора
f
0 0
0 0
0 0
0 0
1 1
1 1
0 1
0 0
2 0
0 1
1 0
3 0
1 0
0 1
4 1
1 0
1 1
5 1
1 1
0 0
6 0
1 1
1 1
7 1

247 Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать
2 8
= 256 строк. Поэтому для задания функции многих переменных удобно использовать модифицированную таблицу истинности. В этом случае множество из n переменных функции разбивается на два подмножества и {x
j+1
, …, x
n
}. Переменными x
1
, x
2
, …, x
j
отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j, а переменными x
j+1
, …, x
n
отмечают столбцы таблицы, задавая в каждом столбце значение соответствующего двоичного набора длины n – Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 5.3). Таблица 5.3 Модифицированная таблица истинности
x
1
, x
2
, …, x
j
x
j+1
, …, x
n
00…0 0…1
…
00…0
…
00…1
…
…
…
…
…
…
11…1
5.2. Элементарные булевы функции Булева функция, зависящая от двух аргументов, называется элементарной. Таблица истинности элементарной булевой функции содержит четыре двоичных набора, а значения функции на этих наборах представляют собой четырехразрядный двоичный вектор. Всего существует
2 4
= 16 различных четырехразрядных двоичных векторов и каждый из них определяет одну элементарную булеву функцию, следовательно, всего существует 16 различных элементарных булевых функций. Построим таблицу всех элементарных булевых функций. Таблица состоит из 18 строки столбцов. Первые две строки содержат значения аргументов x
1
и x
2
соответственно, таких, что столбцы этих строк представляют собой различные наборы значений аргументов. Следующие 16 строк содержат значения функций на всех четырех наборах значений аргументов. Набор значений функции будем рассматривать как четырехразрядное двоичное число j, изменяющееся в пределах от 0000
(2)
= до 1111
(2)
= 15
(10)
. Присвоив это число, но уже в десятичной системе, соответствующей функции в качестве нижнего индекса при ее буквенном изображении f
0
,…,f
15
, расположим все функции в таблице по порядку в соответствии сих индексами (табл. 5.4).

248 Таблица 5.4 Элементарные булевы функции
x
1 0
0 1
1
x
2 0
1 0
1 Наименование Обозначение
f
0 0
0 0
0 Константа нуль функция 0)
f
0
= 0
f
1 0
0 0
1 Конъюнкция функция И)
f
1
= x
1

x
2
= x
1
x
2
f
2 0
0 1
0 Запрет го аргумента нет)
f
2
= x
1

x
2
f
3 0
0 1
1 Повторение го аргумента (да)
f
3
= x
1
f
4 0
1 0
0 Запрет го аргумента нет)
f
4
= x
2

x
1
f
5 0
1 0
1 Повторение го аргумента (нет)
f
5
= x
2
f
6 0
1 1
0 Неравнозначность, сложение по модулю 2
(или-или)
f
6
= x
1

x
2
f
7 0
1 1
1 Дизъюнкция или)
f
7
= x
1

x
2
f
8 1
0 0
0 Операция Пирса
(или-не)
f
8
= x
1

x
2
f
9 1
0 0
1 Эквивалентность функция и-и)
f
9
= x
1

x
2
f
10 1
0 1
0 Отрицание го аргумента (не)
f
10
=
2
x =

x
2
f
11 1
0 1
1 Импликация от го аргумента к 1-му
(нет-не)
f
11
= x
2

x
1
f
12
1 1
0 0 Отрицание го аргумента (не)
f
12
=
1
x =

x
1
f
13 1
1 0
1 Импликация от го аргумента кому
(нет-не)
f
13
= x
1

x
2
f
14 1
1 1
0 Операция Шеффера
(и-не)
f
14
= x
1
| x
2
f
15 1
1 1
1 Константа единица (1)
f
15
= Заметим, что функция счетным индексом может быть получена как отрицание функции с нечетным индексом 15 – j: f
j
=
j
f

15

249