ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"Калининградский государственный технический университет"
(ФГБОУ ВПО "КГТУ")
Кафедра систем управления и вычислительной техники
Пояснительная записка к курсовой работе
По дисциплине «Дискретная математика»
Задания и методические указания к курсовой работе для
студентов специальности 080801.65 – «Прикладная информатика в экономике»
(очно - заочная форма обучения)
Работа допущена к защите Работу выполнила студентка
учебной группы 11ВИЭ-2
___________ Смертин В.М. ___________ Чухаркина Л.И.
(подпись и Ф.И.О. руководителя работы) (подпись и Ф.И.О студента)
_________ ____________
(дата) (дата)
Калининград, 2012
Курсовая работа (КР) состоит из расчетно-графического задания (РГЗ) и двух теоретических вопросов. Вариант РГЗ выбирается по сумме двух последних цифр зачетной книжки, первый теоретический вопрос по предпоследней, а второй – по последней цифре.
КР оформляются на стандартных листах писчей бумаги с использованием текстового редактора и печатаются на принтере, кегль шрифта Time New Roman – 14. Отчет о РГР подшивается в папку. Отчет о РГР начинается со стандартного титульного листа на котором указывается (сверху - вниз): учебное заведение, кафедра, название и номер РГР, автор, дата выполнения, проверяющий с указанием ученой степени, ученого звания, фамилии и имени, отчества , дата проверки, город, год.
После титульного листа следует содержание с указанием разделов и станиц.
Далее идет текст отчета с рисунками, таблицами, расчетами, разбитый на соответствующие методическим указаниями разделы. За ним следуют ответы на теоретические вопросы.
Затем следует список использованной литературы
Задание 1 на расчетно-графическую работу №1 на тему: «Расчет числовых характеристик графов»
Задание на РГР формулируется следующим образом: «Найти основные числа графа G по данным, приведенным в таблице 5.1 для модели графа, представленной на рисунке 5.1: число вершин, число ребер, степени всех вершин, число компонент связности, цикломатическое число, хроматическое число, плотность и неплотность графа.
Рисунок 1 - Модель графа G
Таблица 1 - Данные для формирования графа G по вариантам
Номер варианта |
Удалить в модели графа вершины {i} |
Удалить в модели графа ребра {(i,j)} |
0 |
{1,2} |
{(4,7),(6,7),(7,8),(7,10),(10,11),(10,13)} |
1 |
{1,2} |
{(6,7),(7,10),(7,12),(10,11),(10,13),(11,12)} |
2 |
{1,2} |
{(6,7),(4,7),(4,8),(7,10),(10,11),(10,13)} |
3 |
{1,2} |
{(6,7),(7,10),(7,12),(8,12),(10,11),(10,13)} |
4 |
{1,2} |
{(4,8),(6,7),(7,8),(7,10),(10,11),(10,13)} |
5 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,10),(7,11)} |
6 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,12),(8,12)} |
7 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,10),(10,11)} |
8 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,12),(11,12)} |
9 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,11),(10,11)} |
10 |
{5,10} |
{(2,7),(3,7),(7,11),(7,12),(8,12),(9,12)} |
11 |
{5,10} |
{(4,7),(4,8),(7,11),(7,12),(8,12),(9,12)} |
12 |
{5,10} |
{(2,3),(2,7),(7,11),(7,12),(8,12),(9,12)} |
13 |
{5,10} |
{(3,4),(4,7),(7,10),(7,12),(8,12),(9,12)} |
14 |
{5,10} |
{(2,3),(3,7),(7,10),(7,12),(8,12),(9,12)} |
15 |
{10,13} |
{(1,2),(2,3),(2,7),(6,7),(7,8),(7,12)} |
16 |
{10,13} |
{(1,2),(2,3),(2,7),(3,4),(4,7),(6,7)} |
17 |
{10,13} |
{(1,2),(2,3),(2,7),(6,7),(7,12),(8,12)} |
18 |
{10,13} |
{(1,2),(2,3),(2,7),(4,7),(4,8),(6,7)} |
Расчет числовых характеристик графов
Пусть задан граф G (рисунок 2).
Рисунок 2 - Граф G
Расчет количества вершин n(G) графа G
Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:
1.2. Расчет количества ребер m(G) графа G
Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:
1.3Расчет степеней вершин δi графа G.
Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета сведены в таблицу .2.
Таблица 2 - Результаты расчета
степеней вершин графа G
xi |
δi |
1 |
2 |
2 |
2 |
3 |
2 |
4 |
1 |
5 |
1 |
6 |
2 |
7 |
2 |
8 |
3 |
9 |
3 |
10 |
3 |
11 |
3 |
2. Расчет числа компонент связности æ(G)
Для расчета числа компонент связности графа G вычисляют матрицу достижимости ||Qp|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:
где ||1|| - единичная матрица (рисунок 5.3),
||H(xi)|| - матрица смежности графа G,
||Hp(xi)|| - матрица смежности графа G, возведенная в p-ую степень.
1
1
2
3
4
5
6
7
8
9
10
11
1
1
0
0
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
0
0
0
3
0
0
1
0
0
0
0
0
0
0
0
4
0
0
0
1
0
0
0
0
0
0
0
5
0
0
0
0
1
0
0
0
0
0
0
6
0
0
0
0
0
1
0
0
0
0
0
7
0
0
0
0
0
0
1
0
0
0
0
8
0
0
0
0
0
0
0
1
0
0
0
9
0
0
0
0
0
0
0
0
1
0
0
10
0
0
0
0
0
0
0
0
0
1
0
11
0
0
0
0
0
0
0
0
0
0
1
Рисунок 3 - Единичная матрица для графа G
Для возведения в степень матрицы смежности используют правило умножения булевых матриц.
На рисунке 4 правило умножения булевых матриц прокомментировано графически.
Первая строка на первый столбец
Первая строка на второй столбец
Обозначения: - дизъюнкция (см. таблицу истинности по учебному пособию [4] );
- конъюнкция (см. таблицу истинности по учебному пособию [4])
Рисунок 4 - Пример умножения булевых матриц 4х4
Если булевы операции заменить обычными алгебраическими операциями, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц.
Так как получившаяся матрица будет состоять не только из 0 и 1, то можно воспользоваться функцией знака sign(x).
Данный алгоритм удобно реализовать используя математические пакеты, например MathCAD (смотри приложение 1) или написать программу на любом алгоритмическом языке.
Построим матрицы смежности графа G (рисунок 5).
H |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
8 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
Рисунок 5 - Матрица смежности ||H|| графа G
Возведем матрицу смежности ||H|| в квадрат, т.е. умножим ее саму на себя. Получим ||H2|| (рисунок 7).
Рисунок 7 - Матрица ||H2|| графа G
Возведем матрицу смежности ||H|| в третью степень. Получим ||H3|| (рисунок 8).
Рисунок 8 - Матрица ||H3|| графа G
Анализ матриц ||H2|| и ||H3|| показывает, что никаких изменений в ||H3|| по сравнению ||H2|| нет. Значит процесс вычислений завершен.
Матрица достижимости ||Q3|| (рисунок .9) рассчитывается следующим образом:
Рисунок 5.9 - Матрица ||Q3|| графа G
Поскольку матрица ||Q3|| содержит два блока: один – 3х3 элемента, другой – 6х6 элементов, то граф G содержит два связных подграфа:
G1=<X1,
H1>,
G2=<X2,
H2>,
где X1={x1,x2,x3}, X2={x4,x5,x6,x7,x8,x9}.
Таким образом, для исходного графа G=<X,H> число компонент связности равно æ(G)=2.
Приложение 1. Построение матрицы
достижимости.
Построим
матрицу смежности и зададим единичную
матрицу
Возводим
в соответствующую степень
Построим
матрицу смежности и зададим
единичную матрицу
Возводим
в соответствующую степень
Построим
матрицу смежности и зададим
единичную матрицу
Возводим
в соответствующую степень
Анализ
матриц показывает, что никаких изменений
нет. Матрица достижимости: