- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Упражнения
1.1. Дан граф G
V6
v4
a) определить – к какому типу относится граф;
б
V5
в) указать кратности ребер (v1, v2), (v3, v5);
г
V3
V4
д) указать имеющиеся циклы, простые циклы;
е) указать ребра, смежные ребру (v1, v2);
ж) какие вершины инцидентны ребру (v6, v5)?
1.2. Составить матрицы смежности и инцидентности графов:
v2 v2
а
v3 v1
v4
в)
Какими свойствами обладают данные матрицы?
1.3. Орграф задан матрицей инцидентности. Не строя графа, определить какие имеются контуры в графе. Какова полустепень исхода вершин v1, v4 и полустепень захода вершины v3.
1.4. Орграф задан матрицей смежности. Выяснить, имеются ли контуры в графе.
а) б) в)
1.5. Орграф D c множеством вершин V{1, 2, 3, 4, 5, 6, 7} задан списком ребер X = {(1, 4), (1, 6), (2, 1), (2, 2), (2, 6), (2, 6), (3, 2), (3, 4), (4, 6), (5, 2), (5, 4), (5, 4), (5, 5), (6.2), (6, 5), (7, 1), (7, 6)}.
Построить реализацию графа D.
1.6. Зная матрицу смежности ориентированного псевдографа, определить количество путей длины 1, 2, 3 из v3 в v2, из v2 в v4.Имеет ли контур данный орграф?
А(D) =
1.7. С помощью матрицы A(D) определить, сколько путей длины 2, 3, 4 существует из вершины v1 в вершину v2:
А(D) =
Построить граф и найти эти пути.
1.8. Даны графы G1 и G2. Построить графы G1UG2, G1×G2.
§ Б 2. Булевы матрицы
Определение: (m x n) – матрицу C= [сij], у которой сij{0;1}, где i = 1,2,…,m; j = 1,2,…,n будем называть булевой матрицей.
Замечание. В случае, если G граф без кратных ребер, то матрица смежности A(G) состоит из нулей и единиц, т.е. является булевой.
Над булевыми матрицами одинаковой размерности будем производить обычные логические операции.
-
Дизъюнкция (конъюкция)
Если C=[сij] и Д=[dij] – матрицы размерности m x n, то F=[fij]=CД (СД), есть матрица размерности m x n, у которой каждый элемент fij определяется следующим образом: fij= сijdij (сijdij) (i=1,2…,m; j=1,2…,n).
2) Логическое умножение
Пусть C= [сij] – булева матрица размерности m x k, Д=[dij] – булева матрица размерности kxn. Тогда F= [fij]=C*Д – булева матрица размерности m x n, у которой каждый элемент fij определяется следующим образом:
fij=
Если К=С1* С2*…* Сk , причем С1= С2=…= Сk= С где С – квадратичная булева матрица, то будем писать .
Введем теперь операцию sign перехода от произвольной m x n матрицы Д=[dij] c неотрицательными элементами к булевой m x n матрице С= [cij]=signД, у которой cij=sign dij (i=1,2,…,m; j=1,2…,n), где для любого числа t 0: .
Свойства операции sign:
Sign(Д1+Д2) = sign Д1 sign Д2
Sign(Д1×Д2) = sign Д1 * sign Д2
Замечание. Булевы матрицы более экономичны в вычислительном отношении, чем целочисленные. Запоминание булевой матрицы требует меньшего объема оперативной памяти ЭВМ, чем запоминание целочисленной матрицы той же размерности. Кроме того, выполнение на ЭВМ логических операций над булевыми матрицами требует меньшего объема вычислений, чем над целочисленными.
Вернемся к задаче о вычислении наличия контуров в орграфе.
Утверждение: Для того, чтобы n-вершинный орграф Д c матрицей смежности А=А(Д) имел хотя бы один контур, необходимо и достаточно, чтобы матрица имела ненулевые диагональные элементы.