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

Для расчета числа компонент связности графа G вычисляют матрицу достижимости ||Q^p|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:

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

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

||H^p(x_i)|| - матрица смежности графа G, возведенная в p-ую степень.

Рисунок 3 - Единичная матрица для графа G

Для возведения в степень матрицы смежности используют правило умножения булевых матриц.

На рисунке 4 правило умножения булевых матриц прокомментировано графически.

Первая строка на первый столбец

Первая строка на второй столбец

Обозначения: - дизъюнкция (см. таблицу истинности по учебному пособию [4] );

- конъюнкция (см. таблицу истинности по учебному пособию [4])

Рисунок 4 - Пример умножения булевых матриц 4х4

Если булевы операции заменить обычными алгебраическими операциями, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц.

Так как получившаяся матрица будет состоять не только из 0 и 1, то нужно воспользоваться функцией знака sign(x).

Данный алгоритм удобно реализовать используя математические пакеты, например MathCAD (смотри приложение 1) или написать программу на любом алгоритмическом языке. Программа на MathCAD приведена в файле «mat11new.xmcd». Рассмотренный в данных методических указаниях ниже следующий пример нужно заменить своим расчетом. Далее идет пример расчета:

Построим матрицы смежности графа G (рисунок 5).

Рисунок 5 - Матрица смежности ||H|| графа G

Получим матрицу достижимости ||Q|| графа G (рисунок 6).

Рисунок 6 - Матрица достижимости ||Q|| графа G

Рисунок 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 содержит два связных подграфа:

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

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

1. Расчет цикломатического числа λ(G) графа G

Рассчитаем цикломатическое число графа G, т.е. наименьшее число ребер, удаление которых приведет к графу без циклов и петель.

Расчет выполним по формуле:

	.

В качестве примера удалим на графе G четыре ребра (1,3), (4,5), (5,6), (8,9). Получим граф на рисунке 10.

Рисунок 10 - Граф без циклов и петель

1. Расчет хроматического числа γ(G) графа G

Рассчитаем хроматическое число графа G, т.е. наименьшее число красок при применении которых для раскраски вершин графа две любые смежные вершины графа G, не будут окрашены в один цвет.

Для выполнения расчета воспользуемся двумя оценочными соотношениями. Одно из них задает левую границу для γ(G), min возможное значение γ(G), т.е. γ_min(G):

1) полный n-вершинный граф имеет γ_min(G)=n;

2) пустой граф имеет γ_min(G)=1;

3) граф с циклом (т.е. хотя бы одним) четной длины имеет γ_min(G)=2;

4) граф с циклом нечетной длины имеет γ_min(G)=3;

5) граф-дерево имеет γ_min(G)=2.

Другое оценочное соотношение задает правую границу для γ(G), max необходимое значение γ(G), т.е. γ_max(G):

.

Начинаем проверку с вычисления γ_min(G). Поскольку в графе G есть цикл нечетной длины пробуем раскрасить граф тремя красками (рисунок 11).

Рисунок 11 - Раскраска графа G синей, желтой и красной красками

Вывод: трех красок, т.е. γ_min(G)=3 оказалось достаточно:

.

Если бы трех красок оказалось недостаточно, следовало бы γ_min(G) увеличить на единицу и повторить раскраску заново. И так далее, до получения желаемого результата. Однако таких красок не должно быть больше чем γ_max(G).

1. Расчет плотности (G) графа G

Рассчитаем плотность графа G, т.е. наибольшее число вершин подграфа графа G, между всеми вершинами которого задано отношение смежности.

Получим матрицы смежности ||H|| и достижимости ||Q|| графа G (рисунок 12).

Рисунок 12 - Матрицы ||H|| и ||Q|| графа G

В матрице || Q|| сформируем блоки, используя метод визуального анализа и перестановок строк (т.е. стоки меняются местами) и перестановок столбцов (т.е. столбцы меняются местами). В итоге получим матрицу ||Q|| на рисунке 13.

Q
8

Рисунок 13 - Матрица || Q || с тремя выделенными блоками

Рисунок 14 - Три подграфа графа G

Обозначения: пунктиром выделены полные подграфы графа G.

Таким образом, имеем:

.

Другой алгоритм определения плотности графа приведен в монографии В.А. Горбатова «Фундаментальные основы дискретной математики» на странице 188. Алгоритм приведен в приложении 2.

6. Расчет неплотности ε(G) графа G

(выполнять только на повышенную оценку)

Рассмотрим плотность графа G, т.е. наибольшее число вершин пустого подграфа графа G между всеми вершинами которого нет отношений смежности.

Построим обратный граф ┐G для графа G. Для этого получим матрицу || H || и обратную ей матрицу || ┐H || (рисунок 15).

 

 

		┐H
	H

 

Рисунок 15 - Матрицы смежности (слева-направо) графа G и графа ┐G

 

Строим матрицу достижимости графа ┐G и выполняем операцию перестановки строк и столбцов. Результаты показаны на рисунке 16.

 

 

┐Qp

	┐Qp

 

 

Рисунок 16 - Матрицы достижимости ┐Q^p графа ┐G

Примечание: матрица на рисунке справа имеет блочную структуру.

 

На рисунке 17 показан обратный граф ┐G.

 

Рисунок 17 - Обратный граф ┐G

 

Анализ матрицы ┐Q^p с блочной структурой на рисунке 16 показывает, что поскольку число блоков – три, то имеем три пустых подграфа графа G с тремя вершинами в каждом (рисунок 17):

|Х`<sub>1</sub>|=3, |Х`₂|=3, |Х`₃|=3.

 

Рисунок 18 - Три пустых подграфа графа G

 

 

Таким образом имеем:

 

.

 

На этом расчеты числовых характеристик графа G закончены.

Задание 2. Теоретические вопросы

Письменно ответить на вопросы:

Выбираются по предпоследней цифре зачетной книжки.

0. Основные характеристики графа.

1. Матричные способы задания графов.
2. Маршруты, циклы в неориентированном графе.
3. Пути, контуры в ориентированном графе.
4. Связность графа.
5. Экстремальные пути в нагруженных ориентированных графах.
6. Алгоритм Форда-Беллмана нахождения минимального пути.
7. Алгоритм нахождения максимального пути.
8. Деревья. Основные определения.
9. Минимальные остовные деревья нагруженных графов.

Выбираются по последней цифре зачетной книжки.

1. Определение булевой функции.
2. Формулы логики булевых функций.
3. Равносильные преобразования формул.
4. Двойственность. Принцип двойственности.
5. Булева алгебра. Полные системы булевых функций.
6. Нормальные формы.
7. Разложение булевой функции по переменным.
8. Минимизация формул булевых функций в классе дизъюнктивных нормальных форм.
9. Минимизация формул булевых функций в классе конъюнктивных нормальных форм.
10. Применение алгебры булевых функций к техническим устройствам.

Ответ на вопросы включает основные понятия и определения и объемом 2-3 страницы машинописного текста.