ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

"Калининградский государственный технический университет"

(ФГБОУ ВПО "КГТУ")

Кафедра систем управления и вычислительной техники

Пояснительная записка к курсовой работе

По дисциплине «Дискретная математика»

Задания и методические указания к курсовой работе для

студентов специальности 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)}

1. Расчет числовых характеристик графов

Пусть задан граф G (рисунок 2).

Рисунок 2 - Граф G

0. Расчет количества вершин n(G) графа G

Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:

1.2. Расчет количества ребер m(G) графа G

Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:

1.3Расчет степеней вершин δ_i графа G.

Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине x_i. Результаты расчета сведены в таблицу .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 вычисляют матрицу достижимости ||Q^p|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:

где ||1|| - единичная матрица (рисунок 5.3),

||H(x_i)|| - матрица смежности графа G,

||H^p(x_i)|| - матрица смежности графа 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|| в квадрат, т.е. умножим ее саму на себя. Получим ||H²|| (рисунок 7).

Рисунок 7 - Матрица ||H²|| графа G

Возведем матрицу смежности ||H|| в третью степень. Получим ||H³|| (рисунок 8).

Рисунок 8 - Матрица ||H³|| графа G

Анализ матриц ||H²|| и ||H³|| показывает, что никаких изменений в ||H³|| по сравнению ||H²|| нет. Значит процесс вычислений завершен.

Матрица достижимости ||Q³|| (рисунок .9) рассчитывается следующим образом:

Рисунок 5.9 - Матрица ||Q³|| графа G

Поскольку матрица ||Q³|| содержит два блока: один – 3х3 элемента, другой – 6х6 элементов, то граф G содержит два связных подграфа:

G₁=<X₁, H₁>, G₂=<X₂, H₂>,

где X₁={x₁,x₂,x₃}, X₂={x₄,x₅,x₆,x₇,x₈,x₉}.

Таким образом, для исходного графа G=<X,H> число компонент связности равно æ(G)=2.

Приложение 1. Построение матрицы достижимости.

Построим матрицу смежности и зададим единичную матрицу

Возводим в соответствующую степень

Построим матрицу смежности и

зададим единичную матрицу

Возводим в соответствующую

степень

Построим матрицу смежности и

зададим единичную матрицу

Возводим в соответствующую

степень

Анализ матриц показывает, что никаких изменений нет. Матрица достижимости: