Задача 1.

Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна. а) (A\C) Ç (B\C) = (AÇB) \ C б) (A´B)È(C´D) Í (AÈC)´(BÈD).

Решение:

а) (A\C) Ç (B\C) = (AÇB) \ C

Преобразуем левую часть:

Получена правая часть, т. е. равенство доказано.

Проиллюстрируем равенство с помощью диаграмм Эйлера-Венна.

Рис. 1. Левая часть равенства, представленная в виде диаграмм Эйлера-Венна.

Рис. 2. Правая часть равенства, представленная в виде диаграмм Эйлера-Венна.

Пересечение изображено неверно!

Видно, что диаграммы выражений (A\C) Ç (B\C) и (AÇB) \ C одинаковы. Это означает, что равенство (A\C) Ç (B\C) = (AÇB) \ C верно.

б) (A´B)È(C´D) Í (AÈC)´(BÈD).

Рассмотрим левую часть выражения. В результате декартового произведения (A´B) будет получено множество упорядоченных наборов (a, b) таких, что . Аналогично, результатом произведения (C´D) будет множество упорядоченных наборов (c, d), где . Запишем это следующим образом:

Тогда, выражение (AÈC)´(BÈD), можно записать так, как показано ниже:

Вы все перепутали. Какое выражение Вы записываете??? Исправьте.

где x и y – элементы множества упорядоченных наборов, полученных в результате объединения (A´B)È(C´D).

Произведём аналогичные преобразования и для правой части выражения:

НЕ нашли? Не то? Что вы ищете?

Здесь z и w – элементы множества упорядоченных наборов, полученных в результате декартового произведения (AÈC)´(BÈD).

Сравнив правые части выражений (1) и (2) ( и ), можно сделать вывод, что множество (A´B)È(C´D) является подмножеством (AÈC)´(BÈD). Этот же вывод можно сделать проведя ряд простых логических рассуждений. Покажем это. Пусть v – упорядоченная пара, такая что . Тогда v=(x, y), где x лежит либо во множестве A либо во множестве С, а y – либо во множестве B либо во множестве D. Иными словами , а . Таким образом . Ввиду произвольности v можно заключить, что

.

Задача 4.

Доказать утверждение методом математической индукции:
1·4 + 2·7 + 3·10 + … + n·(3·n+1) = n·(n+1)2.

Решение:

Доказательство заданного утверждения методом математической индукции будем выполнять в два шага.

1. База индукции.

Проверим выполняется ли утверждение при n =0:

n·(3·n+1) = 0·(3·0+1)=0,

n·(n+1)2= 0·(0+1)2=0.

Получаем, что левая и правая части утверждение равны, значит оно выполняется.

2. Индукционный переход.

Предположим, что при некотором n=k, заданное утверждение выполняется, т. е.:

Покажем, что тогда утверждение выполняется и при n=(k + 1):

Преобразуем левую часть равенства (2), подставив в неё левую часть равенства (1): м. б., ПРАВУЮ?

В результате преобразований получили правую часть равенства (2), значит утверждение выполняется при n=(k + 1).

Таким образом, в соответствии с принципом математической индукции равенство справедливо при любом натуральном n.

Остальное верно.

Задача 9.

 


Орграф задан матрицей смежности. Необходимо:
а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

0
0
1
1
0
1

0
0
0
0
1
0

0
0
1
1
0
1

1
0
1
0
0
0

0
1
0
0
1
1

0
0
0
0
0
1

Решение:

Граф, построенный по матрице смежности представлен на рисунке 1.

Рис. 1. Ориентированный граф

Определим компоненты сильной связности орграфа k(G). Для этого разбиваем граф на подграфы (компоненты сильной связности орграфа – это максимальные сильно связные подграфы), как показано на рисунке 2 (КСС выделены красными контурами).

Рис. 2. Компоненты сильной связности орграфа

Получаем, что k(G)=3.

Следует еще ВЫПИСАТЬ КСС в виде множеств. Сделайте это.

На рисунке 3 изображен фактор-граф орграфа G. Этот граф получается стягиванием в одну вершину каждой КСС.

Рис. 3. Фактор-граф орграфа G

Определим, существует ли в орграфе G эйлеров цикл или цепь. Для этого заменим все дуги орграфа G рёбрами:

Рис. 4. Псевдограф

Теперь определим степень всех вершин графа G:

deg(v1)=4,

deg(v2)=2,

deg(v3)=6,

deg(v4)=4,

deg(v5)=5,

deg(v6)=5.

Видим, что граф G имеет две вершины нечётной степени. Это означает, что в графе не существует эйлеров цикл, но есть эйлерова цепь. Началом и концом эйлеровой цепи являются вершины нечётной степени. В нашем случае это вершины v5 и v6. Построение эйлеровой цепи будем осуществлять начиная с вершины v5 и ребра l1. Получаем следующую цепь:

v5, l1, v2, l2, v5, l3, v5, l4, v6, l5, v6, l6, v3, l7, v3, l8, v4, l9, v1, l10, v3, l11, v4, l12, v1, l13, v6.

Ответ: количество компонент связности графа равно k(G)=3. Эйлерова цепь: v5, l1, v2, l2, v5, l3, v5, l4, v6, l5, v6, l6, v3, l7, v3, l8, v4, l9, v1, l10, v3, l11, v4, l12, v1, l13, v6.

Остальное верно.

Задача 10.

Подпись:

Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины v5 до остальных вершин графа, используя алгоритм Дейкстры.

Решение:

Граф, построенный по матрице длин дуг представлен на рисунке 1.

Рис. 1. Взвешенный граф

а). Найдём остовное дерево минимального веса, используя алгоритм Краскала. Для этого будем последовательно выбирать ребра с наименьшим весом так, чтобы не возникало циклов.

Рис. 2. Остовное дерево

Начинаем построение с ребра минимального веса - (v5, v6). Порядок присоединения ребер к остову:

(v5, v6), (v2, v4), (v2, v3), (v2, v6), (v1, v4).

Остовное дерево изображено на рисунке 10.2 (рёбра выделены красным цветом).

Вес остова: W=1+4+2+2+4=13.

б). Найдём кратчайшее расстояние от вершины v5 до остальных вершин графа, используя алгоритм Дейкстры.

a) б)

в) г)

д)

е) ж)

Рис. 3. Поиск кратчайшего расстояния

Вы потеряли начало алгоритма. Картинки есть, а описаний к ним нет. Сделайте их.

Минимальное из расстояний – 6. Выбираем вершину v1. Она становится постоянной (рис. 3 д). Расстояние через v1 до v4 равно 10. Это расстояние больше текущего расстояния до v4 через v2, которое равно 7. Значит метку вершины v4 не меняем. Расстояния до вершин v4 и v3 через вершину v2 одинаковы и равны 7. Значит выбираем любую из вершин, например v3. Она становится постоянной (рис. 3 е). Расстояние через неё до вершины v4 равно 16. Это больше расстояния до вершины v4 через вершину v2. Значит метку вершины v4 не меняем и делаем её постоянной (рис. 3 ж).

Таким образом, найдены все кратчайшие расстояния от вершины v5 до всех остальных вершин графа. Они равны:

расстояние от v5 до v6 – 1,

расстояние от v5 до v2 – 5,

расстояние от v5 до v1 – 6.

расстояние от v5 до v3 – 7,

расстояние от v5 до v4 – 7.

Ответ: вес остовного дерева равен W=13. Кратчайшее расстояние от вершины v5 до остальных вершин графа:

расстояние от v5 до v6 – 1,

расстояние от v5 до v2 – 5,

расстояние от v5 до v1 – 6.

расстояние от v5 до v3 – 7,

расстояние от v5 до v4 – 7.