Расчет степеней вершин δi графа G.
Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета сведены в таблицу.2.
Таблица 2 - Результаты расчета степеней вершин графа G
2. Расчет числа компонент связности æ(G)
Для расчета числа компонент связности графа G вычисляют матрицу достижимости ||Qp|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:
где ||1|| - единичная матрица (рисунок 3), ||H(xi)|| - матрица смежности графа G, ||Hp(xi)|| - матрица смежности графа G, возведенная в p -ую степень.
Рисунок 3 - Единичная матрица для графа G
Для возведения в степень матрицы смежности используют правило умножения булевых матриц. На рисунке 4 правило умножения булевых матриц прокомментировано графически.
Первая строка на первый столбец
Первая строка на второй столбец
Обозначения:
Рисунок 4 - Пример умножения булевых матриц 4х4
|
- дизъюнкция (см. таблицу истинности по учебному пособию [4]);
- конъюнкция (см. таблицу истинности по учебному пособию [4])
