- •Вопрос 5. Множества. [л.3, стр. 5, №1.2 (14)].
- •Вопрос 6. Теория отношений. [л.3, стр. 11, №2.2 (19)].
- •Вопрос 7. Отображения. Функции. [л.3, стр. 14, №3.2 (5)].
- •Вопрос 8. Отношения порядка. [л.3, стр. 16, №4.1 (12)].
- •Вопрос 9. Решетки. [л.3, стр. 19, №5.2 (6)].
- •Вопрос 10. Для графа g найти диаметр графа, радиус графа, центр графа, эйлеров обход, гамильтонов путь и цикл. [л.3, стр. 29, №6.2 (14)].
- •Вопрос 11. Булева алгебра. [л.3, стр. 35, №7.4 (14)].
- •Вопрос 12. Алгебра высказываний. [л.3, стр. 37, №8.1 (4)].
Министерство образования Республики Беларусь
Министерство образования и науки Российской Федерации
Государственное учреждение высшего профессионального образования
«Белорусско-Российский Университет»
Кафедра «Автоматизированные системы управления»
Индивидуальная работа №2 по курсу
«Математические модели информационных процессов и управления»
Задание № 25
Выполнил ст. гр. АСОИ-091
Фарух В. Ж.
Проверил преподаватель
Якимов А.И.
Могилев, 2012
Вопрос 4. На заданной сети [Л.2, стр. 335, №85] указаны пропускные способности ребер. Предполагается, что пропускные способности в обоих направлениях одинаковы. Требуется: 1) сформировать на сети поток максимальной мощности, направленный из истока I в сток S; 2) выписать ребра, образующие на сети разрез минимальной пропускной способности.
Составим матрицу пропускных способностей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
* |
8 |
3 |
0 |
5 |
9 |
0 |
0 |
0 |
2 |
8 |
* |
0 |
4 |
6 |
0 |
0 |
0 |
0 |
3 |
3 |
0 |
* |
0 |
0 |
7 |
0 |
9 |
0 |
4 |
0 |
4 |
0 |
* |
5 |
0 |
7 |
0 |
0 |
5 |
5 |
6 |
0 |
5 |
* |
4 |
8 |
0 |
6 |
6 |
9 |
0 |
7 |
0 |
4 |
* |
0 |
5 |
3 |
7 |
0 |
0 |
0 |
7 |
8 |
0 |
* |
0 |
9 |
8 |
0 |
0 |
9 |
0 |
0 |
5 |
0 |
* |
4 |
9 |
0 |
0 |
0 |
0 |
6 |
3 |
9 |
4 |
* |
Далее вычисляем по алгоритму Форда-Фалкерсона потоки в сети:
1 2 4 7 9 : =4;
1 2 5 9 : =6;
1 5 9 : =5;
1 6 9 : =3;
1 : =3;
1 3 8 9 : =3;
1 8 9 : =4;
Таким образом, поток максимальной мощности из истока 1 в сток 9 будет равна сумме найденных потоков:
= 4+6+5+3+3+3+4=28.
Ребра, образующие минимальный разрез сети:
R=A\B={(1, 2), (1, 5), (5, 6), (6, 9), (8, 9)}
Вопрос 5. Множества. [л.3, стр. 5, №1.2 (14)].
Доказать тождество:
Доказательство:
Вопрос 6. Теория отношений. [л.3, стр. 11, №2.2 (19)].
Для отношений определить, какими свойствами они обладают.
Отношение определено на множестве {7, 9, 10, 14, 15, 18, 19, 21}: xpy |x-y|/7.
Построим матрицу отношения p на этом множестве.
-
x\y
7
9
10
14
15
18
19
21
7
1
0
0
1
0
0
0
1
9
0
1
0
0
0
0
0
0
10
0
0
1
0
0
0
0
0
14
1
0
0
1
0
0
0
1
15
0
0
0
0
1
0
0
0
18
0
0
0
0
0
1
0
0
19
0
0
0
0
0
0
1
0
21
1
0
0
1
0
0
0
1
По матрице отношений можно определить свойства отношений. Диагональные элементы матрицы равны 1; это говорит о том, что отношение рефлексивно.
Матрица симметрична относительно главной диагонали, следовательно, отношение симметрично. Если для всех пар <x, y>, <y,z> выполняется также < x, z>, то отношение транзитивно. Например, на пересечении <7, 14> стоит 1, и на пересечении <14, 21> тоже стоит 1. Следовательно, для этих пар свойство транзитивности выполняется. Исходя из того, что отношение симметрично, получим, что оно является транзитивным.
Вопрос 7. Отображения. Функции. [л.3, стр. 14, №3.2 (5)].
Построить композиции отображений и проверить, являются ли они инъективными, сюръективными или биективными.
Решение:
Композиция функций является сюръекцией, так как нет ни одного элемента у которого нет образа. Композиция функций не является инъекцией, так как не каждый элемент есть образ только одного элемента . Таким образом, - сюръекция
Композиция функций является сюръекцией, так как нет ни одного элемента у которого нет образа. Композиция функций не является инъекцией, так как не каждый элемент есть образ только одного элемента . Таким образом, – сюръекция.