Расчет неплотности ε(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 закончены.

 

 

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

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

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

 

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