Элементы теории графов

Кафедра радиоэлектронных средств

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания
к самостоятельной работе по дисциплине
«Дискретная математика»

Киров 2013

Составители: старший преподаватель каф. РЭС Т.В.Наумович

Дискретная математика: учебно-методическое пособие к самостоятельной работе по дисциплине «Дискретная математика» для студентов направлений 210700.62 «Инфокоммуникационные технологии и системы связи», 090900.62 «Информационная безопасность» и специальности 090302 «Информационная безопасность телекоммуникационных систем» всех форм обучения/Т.В. Наумович. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2013. – 16 с.

Задание

Задание выбирается из таблицы 1 согласно номеру варианта, выданного преподавателем, и выполняется согласно требованиям, установленным на кафедре.

Таблица 1 – Номера вариантов

	№ варианта
Название темы
1.Элементы математической логики и алгебра Буля	1.2б 1.4в	1.3в 1.4к	1.3а 1.4б	1.1в 1.4з	1.2а 1.4и	1.1б 1.4д	1.1г 1.4а	1.1а 1.4е	1.3б 1.4г	1.2в 1.4ж
1.5а 1.6в	1.1д 1.6к	1.5б 1.6б	1.1и 1.6з	1.2г 1.6и	1.1к 1.6д	1.3в 1.6а	1.1ж 1.6е	1.2б 1.6г	1.1е 1.6ж
1.2д 1.4д	1.1з 1.6и	1.2г 1.6з	1.1г 1.4к	1.5а 1.6д	1.1а 1.6е	1.2а 1.4и	1.1в 1.6г	1.3а 1.4б	1.1б 1.4б
1.5б 1.6д	1.2г 1.6к	1.3а 1.6б	1.1и 1.6ж	1.1к 1.6г	1.2в 1.4б	1.3в 1.4и	1.2а 1.4к	1.3в 1.6г	1.2д 1.6ж
2.Элементы теории графов
2.2в	2.4а	2.1	2.2а	2.3а	2.3в	2.4б	2.2б	2.3б	2.2г
3.Оптимизация на графах
3.3а	3.3г	3.3б	3.1б	3.1а	3.1в	3.3в	3.2б	3.1г	3.2а
4. Конечные автоматы
4.1в	4.3а	4.2д	4.2г	4.1б	4.2в	4.1а	4.2а	4.3б	4.2б
5. Теория алгоритмов
	5.2в	5.1г	5.2д	5.2б	5.1а	5.1в	5.2а	5.1д	5.1б	5.2г

Элементы математической логики и алгебра Буля

Логические функции

	x: 0 1 0 1	Условное обозначение	Название
	y: 0 0 1 1
f0	0 0 0 0	“0”	Константа 0
f1	0 0 0 1	; “Ù”; (×)	Конъюнкция (И)
f2	0 0 1 0	; xDy;	Запрет Х
f3	0 0 1 1	y	Переменная "Y"
f4	0 1 0 0	; xDy;	Запрет Y
f5	0 1 0 1	x	Переменная X
f6	0 1 1 0	x Å y	Исключающее ИЛИ
f7	0 1 1 1	“Ú”; +	Дизъюнкция (ИЛИ)
f8	1 0 0 0	;	Стрелка Пирса (ИЛИ-НЕ)
f9	1 0 0 1	;	Равнозначность
f10	1 0 1 0		Инверсия X
f11	1 0 1 1	;	Импликация от X к Y
f12	1 1 0 0		Инверсия Y
f13	1 1 0 1	;	Импликация от Y к X
f14	1 1 1 0	x|y ;	Штрих Шеффера (И-НЕ)
f15	1 1 1 1	“1”	Константа 1

Аксиомы и теоремы булевой алгебры

1. Свойства операций И/ИЛИ/НЕ

; ; ; ; ; .

2. ; (закон идемпотентности).

3. ; .

4. (закон двойного отрицания).

5. ; (перестановочный закон).

6. ; (закон поглощения).

7. ; .

8. ; (закон склеивания).

9. ; (теорема Де Моргана).

10. (сочетательный закон).

11. (ассоциативный закон).

12. ; (дистрибутивный закон).

Задачи

1.1 Запишите таблицы истинности для следующих формул:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и)

к)

1.2 Проверьте с помощью таблиц истинности следующие тождества:

а) ;

б) ;

в) ;

г)

д)

1.3 Постройте логические схемы для обеих частей приведенных ниже тождеств и убедитесь в том, что эти схемы функционирую одинаково:

а) ;

б) ;

в) .

1.4 Запишите формулы для следующих высказываний, обозначив буквами входящие в них простые высказывания:

а) Давление падает и система не работает;

б) Вычисления выполнены точно или конструкция несовершенна;

в) Проект разработал Андрей или Петр, а эксперимент выполнил Иван;

г) Если будет хорошая погода, мы отправимся на стадион или пойдем за грибами;

д) Программа может быть выполнена, если и только если материалы поступят своевременно;

е) Если я поеду на автобусе, то опоздаю на работу, или я воспользуюсь такси;

ж) Андрей помогает Петру или Петр помогает Андрею, или они помогают друг другу;

з) Не верно, что идет дождь и очень жарко;

и) Если телевизор не сломан и подключен к сети питания, я увижу «Новости».

к) Если есть лодка и работа выполнена, то начальство отпустит на рыбалку.

1.5 Преобразуйте формулы к такому виду, чтобы операция отрицания применялась только к логическим переменным:

а)

б)

1.6 Пусть высказывания A означает: “число 2 - четное”, высказывание B - “число 3 - четное”, высказывание C - “число 4 - четное”. С помощью высказываний A, B, C и знаков логических операций построить формулы, содержанием которой является следующее высказывание

а) числа 2 и 3 четные;

б) число 3 – четное или число 4 – нечетное;

в) если число 2 - четное, то число 3 – нечетное;

г) четность числа 2 равносильна четности числа 4;

д) если числа 2 и 3 - четные, то число 4 одновременно и четное и нечетное;

е) хотя бы одно из чисел 2, 3, 4 – четное;

ж) ни одно из чисел 2, 3, 4 не является четным;

з) ровно два числа из набора чисел 2, 3, 4 - четные

и) не все числа 2, 3, 4 - нечетные;

к) по крайней мере два числа из набора чисел 2, 3, 4 – четные.

Элементы теории графов

Основные понятия и термины

Вершина графа – узловая точка графа.

Ребро графа – линия, связывающая пару вершин графа.

Дуга – ориентированное ребро (имеющее направление, указываемое стрелкой).

Ориентированный граф – граф с ориентированными ребрами (дугами).

Параллельные дуги – соединяющие одну и ту же пару вершин графа.

Строго параллельные дуги – имеющие одинаковое направление.

Нестрого параллельные дуги – имеющие противоположное друг другу направления.

Смешанный граф – содержит ребра и дуги.

Взвешенный граф – граф, каждому ребру (дуге) которого приписан некоторый вес (число).

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

Конечный граф – граф, множество вершин которого конечно.

Петля – ребро, граничными вершинами которого является одна и та же вершина.

Кратные ребра – параллельные ребра с одинаковыми граничными вершинами.

Изолированная вершина – не связанная с другими вершинами.

Степень вершины – число ребер, связанных с вершиной (петля учитывается дважды).

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

Мультиграф – граф без петель, но с кратными ребрами.

Псевдограф – граф с петлями и кратными ребрами.

Пустой (нуль-граф) – граф, не имеющий ребер, все вершины которого изолированы.

Однородный (регулярный) граф – граф, степени всех вершин которого равны.

Смежные вершины – граничные вершины одного и того же ребра.

Матрица смежности – строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij)-й элемент равен числу ребер, связывающих i-у вершину с j-й (или направленных от i-й вершине к j-й для ориентированного графа).

Инцидентность – если некоторая вершина является концом ребра, говорят что они инцидентны.

Матрица инцидентности – матрица, строки которой соответствуют вершинам, а столбцы – ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-й элемент равен 1, если i-я вершина инцидентна j-му ребру. В случае орграфа ij-й элемент равен 1, если i-я вершина является началом j-го ребра и -1, если является его концом.

Изоморфные графы – геометрически по-разному изображенные графы, имеющие одинаковую матрицу инцидентности.

Маршрут – последовательность ребер графа, таких, что граничные вершины двух соседних ребер совпадают.

Замкнутый маршрут – приводит в ту же вершину, из которой начался.

Цепь – маршрут, все ребра которого различны.

Простая цепь – маршрут, для которого различны все вершины.

Цикл – замкнутая цепь.

Простой цикл – простая замкнутая цепь.

Эйлеров цикл – цикл, который содержит все ребра графа.

Гамильтонов цикл – цикл, который содержит все вершины графа.

Ориентированный маршрут – маршрут, ребра которого являются дугами.

Путь – маршрут, не содержащий повторяющихся дуг.

Простой путь – путь, не содержащий повторяющихся вершин.

Контур – замкнутый путь.

Простой контур – простой замкнутый путь.

Подграф – часть графа, которая, наряду с некоторым подмножеством ребер графа, содержит и все инцидентные им вершины.

Сверхграф – исходный граф по отношению к его подграфу.

Связный граф – граф, любая пара вершин которого связана.

Циклический граф – граф, содержащий циклы.

Ациклический граф – граф, не содержащий циклов.

Дерево – связный ациклический граф.

Последовательное дерево – представляет собой простую цепь.

Звездное дерево – дерево, в котором одна из вершин (центр) смежна со всеми остальными вершинами.

Плоский граф – граф, который может быть изображен на плоскости без пересечения ребер.

Задачи

2.1 Какие части графа рис.1 нужно соединить, чтобы по ребрам графа можно было проложить маршрут, включающий каждое ребро один раз?

2.2 Пометьте вершины и ребра графа рис.2 буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как пары вершин и отметьте кратные ребра и петли.

б) Определите степени всех вершин, а также суммы степеней всех вершин и всех нечетных вершин графа.

в) Является ли граф однородным (если нет, то добавлением ребер преобразуйте его в однородный) ?

г) Запишите матрицу смежности графа.

Рис.1. Рис.2 Рис.3

2.3 Пометьте вершины и ребра орграфа рис.3 буквами или цифрами и выполните следующие упражнения:

а) Запишите все ребра как пары вершин и отметьте строго параллельные и нестрого параллельные ребра.

б) Определите положительные и отрицательные степени всех вершин и соответственно их суммы.

в) Запишите матрицу инцидентности графа.

2.4 Постройте графы, соответствующие следующим матрицам смежности:

а) ; б) .

Оптимизация на графах

Графы очень удобны для представления сетей. Оптимизационные задачи на сети можно описать следующими четырьмя типами моделей:

1) Минимизация сети.

2) Нахождение кратчайшего маршрута.

3) Определение максимального потока.

4) Минимизация стоимости потока в сети с ограниченными пропускными способностями коммуникаций.

Минимизация сети

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

Пример. Планируется создание кабельной сети (рис.4), для обслуживания нескольких районов-новостроек. Числа на ребрах указывает длину кабеля. Узел 1 представляет центр, остальные узлы (2-6) соответствуют пяти новостройкам. Нужно найти такие ребра, которые потребуют кабель минимальной длины для связи (прямой или через другие пункты) всех районов с центром.

Рис.4 Рис.5

На первом этапе определим два множества. Первое – с уже связанным узлами (в которое мы пока включим только узел 1), второе – с еще не связанными узлами .

Алгоритм минимизации:

1. Из множества выбираем узел, ближайший к одному из узлов множества и переносим его во множество . ( ; )

2. К выбранному узлу проводим соединение на графе.

3. Переходим к п.1.

В результате получим граф рис.5 с минимальной длиной ребер.