Множества и бинарные отношения

1. При голосовании в городскую думу в бюллетене в списке из трех кандидатов требовалось оставить не более одного. При подведении итогов оказалось, что кандидатов и вычеркнули 60% избирателей, кандидатов и - 80% избирателей, а кандидатов и - 70% избирателей. Какой процент избирателей проголосовал против всех кандидатов и какой кандидат набрал наибольшее число голосов?

2. Сколько бинарных отношений можно определить на множестве из элементов?

3. На множестве задано бинарное отношение . Какими свойствами это бинарное отношение обладает? Является ли оно отношением эквивалентности? порядка? В том случае, если - отношение эквивалентности, указать разбиение множества на классы эквивалентности.

4. Рассмотрим на множестве действительныхчисел бинарные отношения , определенные условиями:

, , , .

Выяснить, какими свойствами обладают перечисленные бинарные отношения.

5. Приведите пример рефлексивного, транзитивного, но не симметричного бинарного отношения на множестве из 4-х элементов.

6. Приведите пример рефлексивного, симметричного, но не транзитивного бинарного отношения на множестве из 4-х элементов.

7. Приведите пример транзитивного, симметричного, но не рефлексивного бинарного отношения на множестве из 4-х элементов.

8. Пусть - конечное множество. Сопоставим каждому бинарному отношению на матрицу размера , называемую матрицей отношения, в которой на пересечении -й строки и -го столбца стоит 1. если и 0 в противном случае.

Что представляет собой матрица отношений в случае, если :

а) рефлексивно; б) симметрично; г) антисимметрично.

9. Пусть - конечное множество. Определим на булеане бинарное отношение : (здесь , ). Является ли отношение отношением эквивалентности? Отношением частичного (линейного) порядка?

10. Доказать, что если бинарное отношение одновременно симметрично и антисимметрично, то оно транзитивно.

11. а) Сколько существует рефлексивных бинарных соотношений на множестве из элементов?

б) Сколько существует симметричных бинарных соотношений на множестве из элементов?

в) Сколько существует антисимметричных бинарных соотношений на множестве из элементов?

Контрольная работа 3.

1. Граф задан множеством вершин и ребер:

а) построить диаграмму;

б) указать какой-либо путь, не являющийся цепью; какую-либо цепь, не являющуюся простой цепью; цикл, не являющийся простым; простой цикл (в каждом варианте что-нибудь одно).

2. Для данного графа найти:

а) цикломатическое число;

б) хроматическое число.

3. Построить граф (или орграф) по матрице смежности или инцидентности или, наоборот, найти матрицу смежности или инцидентности графа.

4. Написать код дерева (в одних вариантах бинарный, в других – из натуральных чисел).

5. Построить дерево по коду (в одних вариантах по бинарному, в других – из натуральных чисел).

6. Построить на связном графе остов минимального веса, указать его вес.

Контрольная работа рассчитана на 30-40 минут.

Образцы вариантов контрольной работы 3.

Вариант 1
1.	Пусть - граф с вершинами и ребрами , , , , , , . а) Построить диаграмму графа . б) Указать на графе какой-либо путь, не являющийся цепью, и простой цикл.
2.	Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число.
3.	Построить граф по матрице инцидентности .
4.	Нарисовать какое-нибудь дерево с 8-ю ребрами, занумеровать его вершины и построить его код из натуральных чисел.
5.	Построить дерево по коду (0000010101011111).
6.	Построить для основания ориентированного графа (рис. 1) остов минимального веса (вес указать).

 

 

Вариант 2
1.	Пусть - граф с вершинами и множеством ребер , , , , , , , , . а) Построить диаграмму графа . б) Указать на графе какую-либо цепь, не являющуюся простой цепью, и простой цикл.
2.	Для графа (задание 1) найти: а) цикломатическое число; б) хроматическое число.
3.	Построить граф по матрице инцидентности .
4.	Нарисовать какое-нибудь корневое дерево с 9-ю ребрами и построить его бинарный код.
5.	Построить дерево по коду[2 2 5 5 5 9 5 9].
6.	Построить для основания ориентированного графа (рис. 2) остов минимального веса (вес указать).
Рис. 1	Рис. 2

Структуры варианта БДЗ

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

2. Найти базис циклов на графе (граф задан матрицей инцидентности).

3. Найти эйлерову цепь (цикл) на графе (граф задан списком ребер) (цепь задать в виде последовательности номеров ребер).

4. С помощью алгоритма Дейкстры найти расстояния от вершины ориентированного графа до остальных его вершин; указать кратчайший путь от вершины до вершины (граф задан списком дуг и весовым отображением).

5. С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети (граф задан списком дуг и весовым отображением).

Образец варианта БДЗ

1. Используя теорему Кирхгофа, найти число остовов в обыкновенном графе с вершинами 1,2,3,4,5 и ребрами . Нарисовать диаграммы нескольких остовов.

2. Найти базис циклов на графе, заданном матрицей инцидентности

.

3. Найти эйлерову цепь на графе с вершинами 1,2,3.4.5,6,7.8,9 и ребрами , , ,

4. С помощью алгоритма Дейкстры найти расстояния от вершины 3 ориентированного графа до остальных его вершин; указать кратчайший путь от вершины 3 до вершины 9 (граф задан списком дуг и весовым отображением), если граф имеет вершины 1,2,3,4,5,6,7,8,9, дуги , , , а расстояние между вершинами определяется как сумма их номеров.

5. С помощью алгоритма Форда-Фалкерсона найти максимальный поток и минимальный разрез в сети с вершинами 1,2,3,4,5,6,7,8,9 и дугами , , , если расстояние между вершинами определяется как сумма их номеров, вершина 1 является источником, а вершина 9 стоком.