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

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

где ||1|| - единичная матрица (рисунок 5.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) или написать программу на любом алгоритмическом языке.

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

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

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

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

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

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

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

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

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

	.

В качестве примера удалим на графе G четыре ребра (2,3), (4,6), (6,7), (5,8), (8,10), (7,11,). Получим граф на рисунке 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.

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

Анализ матрицы || Q || на рисунке 13 показывает, что поскольку число блоков равно трем, то имеем три полных подграфа G с тремя вершинами в каждом (1-ый блок: 3х3, 2-ой блок: 3х3, 3-ий блок: 3х3, 4-ий блок: 3х3). Иными словами, |Х`<sub>1</sub>|=3, |Х`₂|=3, |Х`<sub>3</sub>|=3, |Х`₄|=3 (рисунок 14).

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

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

.

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

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

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

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

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

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

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

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

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

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

.