Файл: Контрольная работа Вариант 3 Фамилия Чудинов Имя Кирилл Отчество.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.11.2023
Просмотров: 37
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
в 
: 
Пометки вершин:
Добавка к потоку:
Строим новый поток
: 
Путь из s в t, на котором возможно увеличение потока не построить, поскольку невозможно дойти до стока. Значит поток , построенный на основе заданного в условии, максимален: 
.
Помеченная вершина:
= {1}.
Непомеченные вершины:
= {3,2,4}.
Минимальное сечение:
Величина минимального сечения: 11+2+7 =20 =
Задание 5
На множестве А={1,2,3,4,5,6} задано отношение взаимной простоты: xRy тогда и только тогда, когда x и y взаимно просты, т.е. их наибольший общий делитель:
D (x, y) =1 (нет других общих делителей, кроме 1).
Для заданного отношения нужно:
а) записать отношение R;
б) построить матрицу смежности и граф отношения;
в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.
Решение
Отношение R определяется множеством пар:
Матрица смежности отношение взаимной простоты на множестве А={1,2,3,4,5,6} имеет вид
Граф отношения представлен на рисунке:
Отношение не рефлексивно, симметрично, транзитивно
Использованные источники
3. Поздняков С.Н. Дискретная математика / С.Н. Поздняков, С.В. Рыбин. – М.: Академия, 2008. – 447 с.
4. Е.Л. Рабкин, Ю.Б. Фарфаровская, Дискретная математика/ГУТ.СПб., 2003. – 66 с.
: Пометки вершин:
Добавка к потоку:
Строим новый поток
: Путь из s в t, на котором возможно увеличение потока не построить, поскольку невозможно дойти до стока. Значит поток
, построенный на основе заданного в условии, максимален: .Помеченная вершина:
= {1}.Непомеченные вершины:
= {3,2,4}. Минимальное сечение:
Величина минимального сечения: 11+2+7 =20 =
Задание 5
На множестве А={1,2,3,4,5,6} задано отношение взаимной простоты: xRy тогда и только тогда, когда x и y взаимно просты, т.е. их наибольший общий делитель:
D (x, y) =1 (нет других общих делителей, кроме 1).
Для заданного отношения нужно:
а) записать отношение R;
б) построить матрицу смежности и граф отношения;
в) проверить, является ли отношение рефлексивным, симметричным, транзитивным.
Решение
Отношение R определяется множеством пар:
Матрица смежности отношение взаимной простоты на множестве А={1,2,3,4,5,6} имеет вид
Граф отношения представлен на рисунке:
Отношение не рефлексивно, симметрично, транзитивно
Использованные источники
-
О.М. Дмитриева, И.С. Перфилова, Г.М. Полевая, Н.К. Яновская, Дискретная математика / Методические указания и контрольные задания, - Санкт – Петербург 2012. - 36 с. -
Палий И.А. Дискретная математика / И.А.Палий – М.: Эксмо, 2008. – 350 с.
3. Поздняков С.Н. Дискретная математика / С.Н. Поздняков, С.В. Рыбин. – М.: Академия, 2008. – 447 с.
4. Е.Л. Рабкин, Ю.Б. Фарфаровская, Дискретная математика/ГУТ.СПб., 2003. – 66 с.