Вариант № 5.

1. Упростить запись множества, используя основные равенства множеств:

.

2. Доказать тождество: (AB)C=(AC)(BC).

3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦^-1, ^-1◦, если ={(x,y) | x,y R и 3x≥5y}.

4. Проверить, какими свойствами обладает бинарное отношение

={((a,b),(c,d)) | a/c=b/d}, заданное на множестве NN.

5. Задать некоторое разбиение множества А={2, 3, 4, 5, 7}. Записать отношение эквивалентности, соответствующее данному разбиению. Найти фактор-множество множества А.

Вариант № 6.

1. Упростить запись множества, используя основные равенства множеств:

.

2. Доказать тождество: (A \ B)C=(AC) (BC).

3. Найти область определения, область значений бинарного отношения , инверсию бинарного отношения и композиции ◦, ◦^-1, ^-1◦, если ={(x,y) | x,y R и x²+y²<3}.

4. Проверить, какими свойствами обладает бинарное отношение

={(x,y)| общая часть треугольников x и y есть треугольник}, заданное на множестве всех треугольников плоскости.

5. На множестве А={1,3,5,7,9} задано отношение эквивалентности

={(1,1),(3,3),(5,5),(7,7),(9,9)}. Найти классы эквивалентности, порожденные элементами данного множества и фактор-множество множества А.

Часть 2. Теория графов Вариант № 1.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Дан граф G. Задать длины ребер данного графа. Составить матрицу длин ребер. Найти взвешенные эксцентриситет, радиус и центр.

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности:

4. Дан граф G=(V,X). V=1,2,3,4,5, X=(1,2), (1,3), (2,3), (2,4), (2,5), (3,4),( 3,5), (5,1). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти количество вершин и ребер в графе Е⁴.

Вариант № 2.

1. Найти диаметр, радиус и центр графа G.

2. Орграф задан матрицей смежности. Найти по формуле матрицу сильной связности орграфа. Выделить компоненты сильной связности. Построить реализацию графа и его компонент сильной связности.

А=

3. Используя алгоритм фронта волны, найти минимальный путь из вершины v₁ в вершину v₅ в орграфе, заданном матрицей смежности

4. Дан граф G=(V, X). V=1, 2, 3, 4, 5. X=(1, 3), (2, 4), (2, 5), (3, 2), (3, 4), (3, 5), (4, 1), (4, 5). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Найти хроматическое число графа К₆.

Вариант № 3.

1. Дан граф G. Построить соответствующий реберный граф. Найти матрицу смежности реберного графа через матрицу инцидентности исходного графа. Определить степени вершин и число ребер реберного графа через исходный граф.

2. Найти по формуле матрицу связности графа G, заданного матрицей смежности:

3. Используя алгоритм Форда-Беллмана, найти минимальный путь из вершины v₁ в вершину v₅ в нагруженном орграфе, заданном матрицей длин дуг:

4. Дан граф G=(V,X). V=1,2,3,4,5, X=(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4),( 3,5), (4,5). Построить остов графа. Найти цикломатическое число графа. Выделить базис циклов графа.

5. Существует ли полный граф с четырнадцатью ребрами? Ответ пояснить.