- •Томский государственный университет систем управления и радиоэлектроники (тусур)
- •Методические указания
- •«Дискретная математика»
- •Практическое занятие № 1. «Получение булеана конечного множества»
- •Цель работы
- •Определение булеана конечного множества
- •1.3. Алгоритмы генерации булеана конечного множества
- •1.2. Представление множеств упорядоченными списками
- •1.3. Поверка включения слиянием
- •1.4. Вычисление объединения слиянием
- •1.4. Задание на выполнение
- •1.1. Цель работы
- •1.5. Вычисление пересечения слиянием
- •1.6. Задание на выполнение
- •1.1. Цель работы
- •1.2. Генерация сочетаний
- •1.3. Генерация перестановок
- •1.4. Задание на выполнение
- •1.1. Цель работы
- •1.2. Машинные способы представления графов
- •1.3. Задание на выполнение
- •1.1. Цель работы
- •1.2. Основные определения
- •1.3. Алгоритмы получения матрицы достижимости
- •1.4. Задание на выполнение
- •1.1. Цель работы
- •1.2. Алгоритмы обходов графа
- •1.3. Алгоритмы поиска путей на графах
- •1.4. Задание на выполнение
1.4. Задание на выполнение
Задать с клавиатуры
мощность множества
,
элементы множества и мощность выборки
.
Реализовать алгоритм генерации сочетания
в лексикографическом порядке;
с помощью кодов Грея.
Задать с клавиатуры мощность множества n и элементы множества. Реализовать алгоритм генерации перестановок:
в лексикографическом порядке;
с помощью вложенных циклов;
транспозицией соседних элементов.
Практическое занятие № 4. «Машинное представление графов»
1.1. Цель работы
Разработка и реализация алгоритмов преобразования различных форм представления графов.
1.2. Машинные способы представления графов
1.2.1. Матрица смежности
М
если вершина
смежна
вершине
;
называется квадратная матрица
,
элементы которой задаются по правилу
1.4.
если вершина
не смежна
вершине
;
Матрицей смежности ориентированного графа G=(X,U), называется квадратная матрица , элементы которой задаются по правилу 1.5.
если вершина
смежна
вершине
;
если вершина
смежна вершине
;
если вершина
не смежна
вершине
;
1.2.2. Матрица инцидентности
Матрицей инцидентности
неориентированного графа G=(X,U),
называется матрица
,
элементы которой задаются по правилу
1.6.
если вершина
инцидентна
ребру
если вершина
не инцидентна
ребру
.
;
Матрицей инцидентности ориентированного графа G=(X,U), называется матрица , элементы которой задаются по правилу 1.7.
если вершина
начало
дуги
;
если вершина
конец
дуги
;
если вершина
не инцидентна
дугe
.
если
-
петля при
вершине
;
1.2.3. Список ребер
Списком ребер
неориентированного графа G=(X,U),
называются два
массива
и
,
элементы которых задаются по правилу
1.8:
(1.8)
вершина, являющаяся
концом ребра с номером i.
С
(1.9)
и
,
элементы которых задаются по правилу
1.9:
вершина, являющаяся началом дуги с номером i.
вершина, являющаяся концом дуги с номером i.
1.2.4. Структура смежности
Структурой смежности графа G=(X,U), называется массив списков
,
,
где
- все вершины, смежные вершине
Пример реализации структуры смежности предложен в следующей программе:
#include <iostream.h>
#include <conio.h>
void main()
{
struct List {
int Number;
List *Next;
};
List *Smegn; // массив вершин
int n; // количество вершин графа
clrscr();
cout << "Введите количество вершин графа: ";
cin >> n;
// Выделение памяти под массив вершин
Smegn = new List [n];
for (int i=0;i<n;i++)
{
Smegn[i].Number = i+1;
Smegn[i].Next = NULL;
}
// Ввод структуры смежности
cout << "Признак окончания ввода - 0" << endl;
for(i = 0;i<n;i++)
{
cout << "Вводите вершины смежные вершине " << i+1 << " : ";
int d = 1;
List* Cur = &Smegn[i];
while (d!=0)
{
cout << "# вершины: ";
cin >> d;
if (d==0) continue;
Cur->Next = new List; // выделение памяти под новый элемент
Cur = Cur->Next;
Cur->Next = NULL;
Cur->Number = d;
}
}
// Печать структуры смежности
for (i=0;i<n;i++)
{
cout << Smegn[i].Number << ": "; // номер вершины
List *Cur = &Smegn[i];
if (Cur->Next == NULL) {cout << endl; continue;}; // Если смежных нет, то
//перейти на следующую
//вершину.
do // пока не пройдены все смежные вершины,
//выводить на экран номера вершин
{
if (Cur->Next->Next == NULL) continue;
Cur = Cur -> Next;
cout << Cur->Number << ",";
}
while (Cur->Next->Next != NULL);
Cur = Cur->Next;
cout << Cur->Number << "." << endl; // вывод последней вершины
}
cout << endl;
// удаление структуры смежности из памяти.
for (i=0;i<n;i++)
{
List *Top;
Top = &Smegn[i];
List* Cur = Top->Next;
delete Top;
Top = Cur;
while (Cur!=NULL)
{
Cur = Top->Next;
delete Top;
Top = Cur;
}
delete [] Smegn;
}
getch();
}
