Расчет числовых характеристик графа
Задан граф G (рисунок 2).
Рисунок 2 - Граф G
Расчет количества вершин n(g) графа g
Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:
n(G)=11
1.2. Расчет количества ребер m(g) графа g
Расчет выполняется методом визуального анализа графа G. В итоге расчета имеем:
1.3. Расчет степеней вершин δi графа g.
Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета сведены в таблицу .2.
Таблица 2 - Результаты расчета
степеней вершин графа G
xi |
δi |
1 |
2 |
2 |
2 |
3 |
2 |
4 |
2 |
5 |
3 |
6 |
3 |
7 |
1 |
8 |
5 |
9 |
2 |
10 |
3 |
11 |
3 |
2. Расчет числа компонент связности æ(g)
Для расчета числа компонент связности графа G вычисляют матрицу достижимости ||Qp|| и определяют полные подграфы графа. Для построения матрицы достижимости удобно воспользоваться матрицей смежности графа G:
где ||1|| - единичная матрица (рисунок 3),
||H(xi)|| - матрица смежности графа G,
||Hp(xi)|| - матрица смежности графа G, возведенная в p-ую степень.
1
1
2
3
4
5
6
7
8
9
1
1
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
0
3
0
0
1
0
0
0
0
0
0
4
0
0
0
1
0
0
0
0
0
5
0
0
0
0
1
0
0
0
0
6
0
0
0
0
0
1
0
0
0
7
0
0
0
0
0
0
1
0
0
8
0
0
0
0
0
0
0
1
0
9
0
0
0
0
0
0
0
0
1
Рисунок 3 - Единичная матрица для графа G
Для возведения в степень матрицы смежности используют правило умножения булевых матриц.
На рисунке 4 правило умножения булевых матриц прокомментировано графически.
Первая строка на первый столбец
Первая строка на второй столбец
Обозначения:
-
дизъюнкция (см. таблицу истинности по
учебному пособию [4] );
-
конъюнкция (см. таблицу истинности по
учебному пособию [4])
Рисунок 4 - Пример умножения булевых матриц 4х4
Если булевы операции заменить обычными алгебраическими операциями, нахождение матрицы достижимости сведётся к обычному пошаговому перемножению матриц.
Так как получившаяся матрица будет состоять не только из 0 и 1, то нужно воспользоваться функцией знака sign(x).
Данный алгоритм удобно реализовать используя математические пакеты, например MathCAD (смотри приложение 1), пакет Excel (смотри приложение 2), или написать программу на любом алгоритмическом языке.
Приведем методику расчета. Матрицы в примере расчета следует заменить на полученные для своего варианта.
Построим матрицы смежности графа G (рисунок 5).
H |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
5 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
7 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
Рисунок 5 - Матрица смежности ||H|| графа G
Получим матрицу достижимости ||Q|| графа G (рисунок 6).
H |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
5 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
7 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
Рисунок 6 - Матрица достижимости ||Q|| графа G
В
H2
1
2
3
4
5
6
7
8
9
1
1
1
1
0
0
0
0
0
0
2
1
1
1
0
0
0
0
0
0
3
1
1
1
0
0
0
0
0
0
4
0
0
0
1
1
1
1
1
1
5
0
0
0
1
1
1
1
1
1
6
0
0
0
1
1
1
1
1
1
7
0
0
0
1
1
1
1
1
1
8
0
0
0
1
1
1
1
1
1
9
0
0
0
1
1
1
1
1
1
Рисунок 7 - Матрица ||H2|| графа G
Возведем матрицу смежности ||H|| в третью степень. Получим ||H3|| (рисунок 8).
H3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
5 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
6 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
8 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
9 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Рисунок 8 - Матрица ||H3|| графа G
Анализ матриц ||H2|| и ||H3|| показывает, что никаких изменений в ||H3|| по сравнению ||H2|| нет. Это значит, что процесс вычислений завершен.
Матрица достижимости ||Q3|| (рисунок .9) рассчитывается следующим образом:
Q3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
5 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
6 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
8 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
9 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
Рисунок 5.9 - Матрица ||Q3|| графа G
Поскольку матрица ||Q3|| содержит два блока: один – 3х3 элемента, другой – 6х6 элементов, то граф G содержит два связных подграфа:
G1=<X1,
H1>,
G2=<X2,
H2>,
где X1={x1,x2,x3}, X2={x4,x5,x6,x7,x8,x9}.
Таким образом, для исходного графа G=<X,H> число компонент связности равно æ(G)=2.