Формирование групп и определителя графа

Для формирования групп контуров графа первоначально необходимо определить пары некасающихся контуров. Очень часто принято результаты идентификации пар некасающихся контуров представлять в виде матрицы касаний контуров по два F₂ [9]. Здесь строками и столбцами являются кодовые номера контуров графа. Если i-й контур графа имеют одну или более общих вершин с j-м контуром, т.е. являются касающимися, то элемент матрицы f_ij=1. В противном случае - f_ij=0.

Нужно заметить, что матрица F₂ симметричная. Поэтому для получения информации о парах некасающихся контуров достаточно использовать лишь ее верхнюю или нижнюю треугольные части.

Матрица F₂ определяется с помощью булева произведения матрицы Z на результат ее транспонирования Z^т, то есть

(8.4)

Для нашего примера верхняя треугольная часть имеет вид

Чтобы сформировать формулу i-й группы осуществляется последовательный обход матрицы от i-й до последней строки, в ходе которого путем поиска нулевых элементов матрицы выполняется построение дерева сочетаний некасающихся с i-м контуром контуров графа. Обход последнего дерева позволит сформировать формулы i-й группы D_i.

На рис. 8.4 представлены деревья сочетаний некасающихся контуров и формулы всех групп контуров.

При известных формулах всех n-групп контуров определитель графа вычисляется с помощью выражения

(8.5)

Алгоритмизация выражения (8.5) осуществляется последовательным наращиванием формулы на каждом этапе формирования i-й группы.