- •Министерство образования и науки российской федерации
- •Лабораторная работа №1 операции над множествами
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Примеры записи нечеткого множества
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №3 бинарные отношения
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа № 4 комбинаторные алгоритмы
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа № 5 Машинное представление графа
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №6 алгоритмы построения кратчайших путей в графе и кратчайшего остова графа
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №7 алгоритмы построения эйлерова и гамильтонова цикла
- •Теоретические сведения
- •Пример выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Лабораторная работа №8 совершенные нормальные формы булевых функций
- •Теоретические сведения
- •Технология выполнения работы.
- •Контрольные вопросы
- •Задание для лабораторной работы.
- •Библиографический список
Контрольные вопросы
Дайте определения размещений, перестановок и сочетаний с повторениями и без повторений элементов.
Приведите формулы для вычисления соответствующих комбинаторных чисел.
Объясните порядок генерации комбинаций в каждом из алгоритмов.
Задание для лабораторной работы.
1. Для задания варианта определить теоретическое число комбинаций, удовлетворяющих условию или требуемых для решения задачи.
2. Написать программу, которая выполняет задание варианта с помощью генерации всех соответствующих комбинаций, используя комбинаторные алгоритмы. При этом:
во время генерации производить подсчет общего числа сгенерированных вариантов и число вариантов, удовлетворяющих условию задачи, вывести эти значения на экран;
если решение не единственное, то вывод комбинаций осуществлять в файл.
3. Формулу для расчета теоретического значения числа комбинаций, текст программы и результат её работы для контрольного примера оформить в отчёт.
Лабораторная работа № 5 Машинное представление графа
Цель работы: изучение способов аналитического представления графа, программная реализация представления графа с помощью списков инцидентности.
Теоретические сведения
Рассмотрим конечный граф G=(V, E), где |V|=n, |E|=m.
Способами аналитического представления графа являются:
1. Матрица инциденций.
Ориентированный граф задается прямоугольной матрицей B(nm), элементы которой определяются по правилу:
Кроме нерационального использования памяти (nm единиц) недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы:
а) существует ли ребро (дуга) (vi, vj);
б) к каким вершинам ведут ребра (дуги) из вершины vi
требуется, в худшем случае, перебор nm элементов, т.е. порядка nm шагов алгоритма.
2. Матрица смежности.
Элементы квадратной матрицы A(nn) определяются следующим образом:
Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n2 шагов алгоритма.
3. Матрица ребер.
Она представляет собой матрицу размером m2, каждая строка которой содержит вершины инцидентные i-му ребру (i-ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг).
Этому способу представления графа присущ тот же недостаток, что и матрице инциденций, - неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Поиск можно ускорить, введя лексикографический порядок в упорядочении пар и применяя двоичный поиск.
4. Списки инцидентности.
Для каждой вершины viV создается список записей, характеризующих ребра (дуги), инцидентные этой вершине.
Таким образом, это представление использует объем памяти порядка (n+m), поиск вершины смежной с данной требует порядка (n+m) шагов, проверка свойств графа осуществляется за число шагов порядка. Поэтому остановимся подробнее на этом способе задания графа.
Технология выполнения работы.
Списки инцидентности графа в языке C++ могут быть реализованы вектором, размерность которого равна количеству вершин графа. Каждый его элемент является списком, содержащим номера вершин, смежных с данной. Предварительно определения контейнерных классов vector и list должны быть подключены к файлу.
Если определить вектор, составленный из списков, как тип graf, т.е.
typedef vector <list <int>> graf ;
то исходный граф G будет описан graf G;.
Если граф взвешенный, то элементами его списков являются записи, содержащие помимо номера смежной вершины веса ребра (дуги), инцидентного этой вершиной.
Ввод графа осуществляется из текстового файла одного из двух видов: «таблица смежности» или «таблица ребер». Такие файлы по-разному формируются и интерпретируются для неориентированных и ориентированных графов: для неориентированного графа задаются ребра графа, а для ориентированного – дуги. То есть, ребро неориентированного графа задается один раз, а соответствующие ему записи автоматически включаются в списки инцидентности обоих его концов.
Файл «таблица смежности» состоит из блоков, соответствующих вершинам графа. Каждый блок имеет следующую структуру:
начальная вершина : список смежных с ней вершин
соответствующие ребрам (дугам) веса
Количество строк с весами ребер равно числу весов, число вершин списка равно числу весов в строках. Блоки в таком файле могут располагаться в произвольном порядке, причем, если вершина не является начальной ни для одного ребра (дуги) или ребро уже включено в список инцидентности другого его конца, то соответствующий ей блок отсутствует в файле.
Например, для неориентированного графа
Рис. 2
файл «таблица смежности» имеет вид
1 : 3 4
5 10
3 : 4
7
4 : 5
4
а ориентированный граф
Рис. 3
задается «таблицей смежности»
1 : 2 3
2 : 3
3 : 1
Для ориентированных графов могут формироваться как списки вершин, следующих за текущей, так и предшествующих ей вершин.
Файл «таблица ребер» имеет следующую структуру:
начальная вершина конечная вершина вес(а) ребра (дуги)
Также как и для «таблицы смежности» количество элементов в каждой из строк должно быть одинаковым, а число весов равно kv.
Например, файл «таблица ребер» графа, изображенного на рис.2 имеет вид.
1 3 5
1 4 10
3 4 7
4 5 4
Для формирования машинного представления графа необходимо построить список инцидентности для каждой вершины графа. Формирование списка инцидентности может осуществляться по принципу стека (LIFO), когда новая запись включается в начало списка, или по принципу очереди (FIFO), когда новая запись ставится в конец списка.
Определение количества вершин и рёбер (дуг) исходного графа выполняется программно при формировании списков инцидентности графа. Количество вершин определяется как максимальный номер вершины. Число рёбер (дуг) подсчитывается как суммарное число вершин для всех списков в исходном файле – для «таблицы смежности» и число строк – для «таблицы рёбер». Эти значения и построенные списки инцидентности выводятся на экран (или выходной файл).
Приведём алгоритмы построения списков инцидентности графа по входным файлам обоих видов. Используемые в алгоритмах обозначения:
nv – начальная вершина ребра (дуги);
kv – конечная вершина ребра (дуги).
Файл «таблица смежности».
while ( не конец файла )
{ ввод и проверка nv;
while ( не конец строки )
{ ввод и проверка kv;
добавить запись kv в список nv;
добавить запись nv в список kv; (для не-
ориентированного графа)
}
}
Файл «таблица ребер».
while ( не конец файла )
{ ввод и проверка nv;
ввод и проверка kv;
добавить запись kv в список nv;
добавить запись nv в список kv; (для неориентированно-
го графа)
}
Вывод списков инцидентности графа на экран или в файл осуществляется в соответствии со структурой аналогичной файлу «таблица смежности». При этом просматривается список каждой вершины, если он не пуст, то выводится: СП, затем в скобках вершина, : , список вершин смежных с ней. Например, выводимая информация имеет вид:
а) для графа (рис. 2)
СП(1): 3 4
СП(3): 1 4
СП(4): 1 3 5
СП(5): 4
б) для графа (рис. 3)
Списки следования: Списки предшествования:
СП [1]: 2 3 СП [1]: 3
СП [2]: 3 СП [2]: 1
СП [3]: 1 СП [3]: 2 1
Для вывода списка инцидентности или любого другого вида его обработки необходимо просмотреть этот список. Просмотр списка выполняется с помощью итераторов, которые являются аналогами указателей для контейнерных классов. Для этого итератору текущего элемента списка присваивается значение начала списка, а также запоминается итератор конца списка. Пока не достигнут конец списка, выполняются действия по обработке элемента списка и увеличение итератора текущего элемента списка. Обращение к элементу, адресуемому итератором, выполняется так же, как и для указателей, операторами * или >.
Например, фрагмент программы просмотра i-го списка графа имеет вид:
list <int> :: iterator pl = G[i].begin(), el = G[i].end();
while(pl!=el) блок обработки элемента;
При работе с графом часто требуется выполнить действия, изменяющие его структуру. К ним относятся:
Добавление ребра (дуги) (vi, vj) в граф G.
Для этого нужно:
а) добавить запись с вершиной vj в список инцидентности вершины vi;
б) для неориентированного графа добавить запись с вершиной vi в список инцидентности вершины vj.
Удаление ребра (дуги) (vi, vj) из графа G (осуществляется аналогично добавлению ребра (дуги)).
Удаление вершины vi из графа G.
Для этого нужно удалить все ребра (дуги) инцидентные вершине vi(т.е. удалить все записи из списка вершиныvi, а для неориентированных графов – и соответствующие записи из списков смежных с ней вершин).
Часто кроме изменения структуры графа для более эффективной работы алгоритмов требуется сортировка (упорядочение) списков инцидентности.
Выполнить сортировку вершин в списке (для графа без весов) и поиск вершины в списке для удаления ребра (дуги), а следовательно, и вершины, в языке С++ можно, пользуясь абстрактными алгоритмами контейнерных классов. Для этого нужно подключить к файлу определение класса алгоритмов algorithm. Если элементами списков являются записи, то сортировка вершин выполняется одним из алгоритмов сортировки.