close

Вход

Забыли?

вход по аккаунту

?

РГР6 Павлов

код для вставкиСкачать
huhu
 Федеральное агентство по образованию
Балтийский федеральный университет им. И. Канта
Институт современных образовательных технологий
Кафедра компьютерного моделирования и информационных систем
Расчетно-графическая работа №6
по дисциплине
"Теоретические основы информатики"
по теме
"Расчет числовых характеристик графов"
(вариант 10)
Выполнил:
студент 3 курса очного отделения направления "физико-математическое образование", профиля "информатика" Павлов Сергей
Проверил:
доктор технических наук,
профессор А.В. Колесников
Калининград 2012
Содержание
1. Расчет числовых характеристик графа
1.1 Расчет количества вершин n (G) графа G.................................. ..3
1.2 Расчет количества ребер m (G) графа G .................................... ..3
1.3 Расчет степеней вершин δi графа G............................................3
1.4 Расчет числа компонент связности æ(G).....................................4
1.5 Расчет цикломатического числа λ(G) графа G..............................8
1.6 Расчет хроматического числа γ(G) графа G..................................8
1.7 Расчет плотности (G) графа G...............................................12
1.8 Расчет неплотности ε(G) графа G................................................13
1.9 Расчет внешней устойчивости ψ(G) графа G...............................15
1.10 Расчет числа внутренней устойчивости (G) графа G..................17
Список использованной литературы.................................................19
Вариант 10.
1. Расчет числовых характеристик графа
Пусть задан граф G.
Рисунок 1.1 Граф G
1.1 Расчет количества вершин n (G) графа G
Расчет выполняется методом визуального анализа графа G. n (G) = 11
1.2 Расчет количества ребер m(G) графа G
Расчет выполняется методом визуального анализа графа G. m (G) = 15
1.3 Расчет степеней вершин δi графа G
Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета представлены в таблице 1.1.
Таблица 1.1 - Результаты расчета степеней вершин графа G
xiδi122232425463728592103113
1.4 Расчет числа компонент связности æ(G)
Для расчета числа компонент связности графа G вычисляют матрицу достижимости ||Qp|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:
где ||1|| - единичная матрица,
||H(xi)|| - матрица смежности графа G,
||Hp(xi)|| - матрица смежности графа G, возведенная в p-ую степень
1123456789101111000000000020100000000030010000000040001000000050000100000060000010000070000001000080000000100090000000010010000000000101100000000001Рисунок 1.2 Единичная матрица для графа G
Построим матрицу смежности для графа G.
H123456789101110110000000021010000000031100000000040000100001050001010101060000101100070000010100080000011010190000000100110000110000011100000001110Рисунок 1.3 - Матрица смежности ||H|| графа G
Получим матрицу достижимости ||Q|| графа G (рисунок 1.4).
Q1234567891011111100000000211100000000311100000000400011000010500011101010600001111000700000111000800000111101900000001101100001100001101100000001111Рисунок 1.4 - Матрица достижимости ||Q|| графа G
Возведем матрицу смежности ||H|| в квадрат, получим ||H2|| (рисунок 1.5)
H2123456789101111110000000021110000000031110000000040001110101150001111111160001011111170000111110180000111111190000011111110000111011101100011111101Рисунок 1.5 - Матрица ||H2|| графа G
Возведем матрицу смежности ||H|| в третью степень. Получим ||H3|| (рисунок 1.6).
H3123456789101111110000000021110000000031110000000040001111111150001111111160001111111170001111111180001111111190001111111110000111111111100011111111Рисунок 1.5 - Матрица ||H3|| графа G
Анализ матриц ||H2|| и ||H3|| показывает, что никаких изменений в ||H3|| по сравнению ||H2|| нет. Значит процесс вычислений завершен.
Матрица достижимости ||Q3|| (рис. 5.9) рассчитывается следующим образом:
Q3123456789101111110000000021110000000031110000000040001111111150001111111160001111111170001111111180001111111190001111111110000111111111100011111111Рисунок 1.8- Матрица ||Q5|| графа G
Поскольку матрица ||Q3|| содержит два блока: один - 3х3 элемента, другой - 6х6 элементов, то граф G содержит два связных подграфа:
где X1={x1,x2,x3}, X2={x4,x5,x6,x7,x8,x9}.
Таким образом, для исходного графа G = <X,H> число компонент связности равно æ(G)=2.
1.5 Расчет цикломатического числа λ(G) графа G
Рассчитаем цикломатическое число графа G, т.е. наименьшее число ребер, удаление которых приведет к графу без циклов и петель.
Расчет выполним по формуле:
В качестве примера удалим на графе G шесть ребер (9,8), (11,9), (10,5), (8,6), (5,8), (5,6) (1,3) . Получим граф на рисунке 1.9.
Рисунок 1.9 - Граф без циклов и петель
1.6 Расчет хроматического числа γ(G) графа G
Для расчета хроматического числа будем использовать два способа: 1) раскраска вручную с применение оценочных соотношений; 2) раскраска с применением алгоритма.
Для раскраски вручную воспользуемся двумя оценочными соотношениями. Одно из них задает левую границу для γ(G), min возможное значение γ(G), т.е. γmin(G). Другое оценочное соотношение задает правую границу для γ(G), max необходимое значение γ(G), т.е. γmax(G): = 6.
Начинаем проверку с вычисления γmin(G). Поскольку в графе G есть цикл нечетной длины, пробуем раскрасить граф тремя красками (рисунок 1.10).
Рисунок 1.10 - Раскраска графа G красной, зелёной и синей красками
Вывод: трех красок, т.е. γmin(G) = 3 оказалось достаточно: .
Для раскраски графа вторым способом используем определенный алгоритм (рисунок 1.11).
Рисунок 1.11 - Исходный граф G для раскраски
Вычислим степени всех вершин (на рис. 1.12 степени вершин указаны рядом с вершинами).
Рисунок 1.12 - Граф G, для которого рассчитаны степени вершин
Просмотрим вершины графа в порядке невозрастания значений их степеней и окрасим в цвет №1 (красный) все неокрашенные вершины, которые не смежны уже окрашенным в желтый цвет вершинам (рис. 1.13).
Рисунок 1.13 - Граф G после первого шага раскраски
Просмотрим вершины графа в порядке невозрастания значений их степеней и окрасим в цвет №2 (зеленый) все неокрашенные вершины, которые не смежны уже окрашенным вершинам в синий цвет (рис. 1.14).
Рисунок 1.14 - Граф G после второго шага раскраски
Просмотрим вершины графа в порядке невозрастания значений их степеней и окрасим в цвет №3 (синий) все неокрашенные вершины, которые не смежны уже окрашенным вершинам в синий цвет (рис. 1.15).
Рисунок 1.15 - Граф G после третьего шага раскраски
Поскольку все вершины графа раскрашены, алгоритм заканчивает работу. Хроматическое число графа равно трем, т.е. γ(G) = 3.
Сравнивая результаты ручного и "алгоритмического" расчетов, приходим к выводу, что они совпадают.
1.7 Расчет плотности (G) графа G
Рассчитаем плотность графа G, т.е. наибольшее число вершин подграфа графа G, между всеми вершинами которого задано отношение смежности. Получим матрицы смежности ||H|| и достижимости ||Q|| графа G (рисунок 1.16)
H456789101140100001051010101060101100070010100080011010190000100110110000011100001110
Q456789101141100001051110101060111100070011100080011110190000110110110000111100001111
Рисунок 1.16 - Матрицы ||H|| и ||Q|| графа G
В матрице || Q|| сформируем блоки, используя метод визуального анализа, перестановок строк (т.е. стоки меняются местами) и перестановок столбцов (т.е. столбцы меняются местами). В итоге получим матрицу ||Q|| на рисунке 1.17.
Q410567891141110000010111000015111101006001111007000111008001111119000001111101000111
Рисунок 1.17 - Матрица || Q || с четыремя выделенными блоками
Анализ матрицы || Q || на рисунке 1.17 показывает, что поскольку число блоков равно четырем, то имеем четыре полных подграфа G (1-ый блок: 3х3, 2-ой блок: 2х2, 3-ий блок: 3х3, 4-ий блок: 3х3). Иными словами, |Х`1|=3, |Х`2|=2, |Х`3|=3, |Х`4|=3 (рисунок 1.18).
Рисунок 1.18 - Четыре подграфов графа G
Обозначения: пунктиром выделены полные подграфы графа G.
Таким образом, имеем: .
1.8 Расчет неплотности ε(G) графа G
Рассмотрим плотность графа G, т.е. наибольшее число вершин пустого подграфа графа G между всеми вершинами которого нет отношений смежности.
Построим обратный граф ┐G для графа G. Для этого получим матрицу || H || и обратную ей матрицу || ┐H || (рисунок 1.19).
H456789101140100001051010101060101100070010100080011010190000100110110000011100001110
┐H456789101141011110050101010161010011171101011181100101091111011010001111101111110001
Рисунок 1.19 - Матрицы смежности (слева-направо) графа G и графа ¬G
Строим матрицу достижимости графа ┐G и выполняем операцию перестановки строк и столбцов. Результаты показаны на рисунке 1.20.
┐Q456789101141011110050101010161010011171101011181100101091111011010001111101111110001 ┐Q759106481171111010151110000191111111010101110106001111014101011108001101101111001001 Рисунок 1.20 - Матрицы достижимости ¬Qp графа ¬G
Примечание: матрица на рисунке справа имеет блочную структуру.
На рисунке 1.21 показан обратный граф ¬G.
Рисунок 1.21 - Обратный граф ¬G
Анализ матрицы ¬Qp с блочной структурой показывает, что поскольку число блоков - четыре, то имеем четыре пустых подграфов графа G (1-ый блок: 3х3, 2-ой блок: 3х3, 3-ий блок: 2х2, 4-ий блок: 2х2). Иными словами, |Х`1|=3, |Х`2|=3, |Х`3|=2, |Х`4|=2 (рисунок 1.22).| Рисунок 1.22 - Четыре пустых подграфов графа G
Таким образом, имеем: .
1.9 Расчет внешней устойчивости ψ(G) графа G
Рассчитаем внешнюю устойчивость графа G, т.е. наименьшее число вершин графа G смежных со всеми остальными вершинами графа.
Составим таблицу 1.2 отображений для графа G и дополним ее столбцом несмежных вершин.
Таблица 1.2 - Таблица отображений графа G
xiHi¬ Hi45,10 6, 7, 8, 9, 1154, 6, 8, 107, 9, 1165, 7, 84, 9,10, 1176, 84, 5, 9, 10, 1185, 6, 7, 9, 114, 10911, 84, 5, 6, 7, 1010 4, 5, 116, 7, 8, 9, 10118, 9, 104, 5, 6, 7 Анализ таблицы 1.2 показывает, что в столбце ¬Hi есть несмежные вершины. В этом случае необходимо построить еще одну таблицу - таблицу 1.3 отображений и несмежных вершин для двухэлементных подмножеств.
Таблица 1.3 - Таблица отображений и несмежных вершин для двухэлементных подмножеств
H¬ H4, 510,8,6,79,114,105, 116, 7, 8, 95, 64, 7, 10, 88, 105, 84, 6, 10, 9, 7116, 75, 84, 9, 10, 116, 8 5, 7, 9, 114, 107, 86, 5, 9, 114, 108, 95, 6, 7, 114, 109, 118, 104, 5, 910, 54, 11, 6, 87, 910, 114, 5, 8, 96, 711,810, 9, 5, 64, 7 Т.к. в таблице 1.3 отсутствует элемент , то переходим к формированию таблицы 1.4 отображений и несмежных вершин для трехэлементных подмножеств.
Таблица 1.4 - Таблица отображений и несмежных вершин для трехэлементных подмножеств
{xi,xj,xk}┐4,5,610, 8, 79,1110, 4, 56, 11, 8, 67,94, 5, 810, 9, 6, 75, 6, 84, 10, 7, 9, 810,5,64, 7, 8, 9, 1110, 11,89, 5, 6, 7, 48, 5, 711, 9, 6, 4, 105, 8, 67, 9, 11, 4, 10.........
Т.к. в таблице присутствует элемент (¬ H , то расчеты завершены, и можно приступить к анализу таблицы 1.2, таблицы 1.3 и таблицы 1.4. По итогам анализа таблицы 1.4 можно сформировать множество T потенциальных ядер графа G, т.е.
и т.д., где Т1= , Т2 ={} , Т3 ={} и т. д.
Тогда ψ(G)={| |}={||}|i=1,2,3=3.
1.10 Расчет числа внутренней устойчивости (G) графа G
Составим таблицу 1.2 отображений и несмежных вершин графа G. Анализ таблицы 1.2 показывает, что в столбце ¬Hi есть несмежные вершины. В этом случае построим таблицу 1.5 двухэлементных множеств из несмежных вершин, найдем им образ и ¬.
Таблица 1.5 - Таблица образов и ¬
{xi,xj}┐4, 65 7 8 109 114, 7 10 5 6 89 114, 810 5 11 9 6 74, 910 5 11 86 74, 105 11 106 7 8 94, 1110 5 9 86 7 5,74 6 8 109 115, 94 6 10 8 975, 114 6 10 8 976, 95 7 8 4 1110 46, 115 7 8 9 1047, 96 8 114 5 107, 106 8 4 115 97, 116 8 9 10 4 58, 109 11 5 6 7 49, 1011 8 45 6 7
Поскольку не во всех строках столбца ¬таблицы 1.5 указаны знаки , сформируем таблицу 1.6 трехэлементных множеств {xi,xj,xk} и найдем им образ и ¬ .
Таблица 1.6 - Таблица образов и ¬ H¬ H5, 7, 1110 4 8 6 9 4 6 910 5 7 8 114 6 10 5 7 8 119
Поскольку УЖЕ не во всех строках столбца ¬таблицы 1.6 указаны знаки , и так как хроматическое число графа = 3 (нельзя найти 4 и более точки на графе которые одновременно не будут смежны друг другу) ,то процесс вычислений закончен и можно перейти к анализу таблицы 1.2, таблицы 1.6.
По итогам анализа можно сформировать множество S ядер графа G, т.е.
, где S1=, S2=, S3=, S4= и т.д.
Тогда (G)={|Si|}={||}|i=1,12=3.
На этом расчеты числовых характеристик графа G закончены.
Список использованной литературы
1. Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.
2
Автор
mannekenpis
Документ
Категория
Другое
Просмотров
479
Размер файла
975 Кб
Теги
павлова, ргр6
1/--страниц
Пожаловаться на содержимое документа