Для формирования групп контуров графа первоначально необходимо определить пары некасающихся контуров. Очень часто принято результаты идентификации пар некасающихся контуров представлять в виде матрицы касаний контуров по два F2 [9]. Здесь строками и столбцами являются кодовые номера контуров графа. Если i-й контур графа имеют одну или более общих вершин с j-м контуром, т.е. являются касающимися, то элемент матрицы fij=1. В противном случае - fij=0.
Нужно заметить, что матрица F2 симметричная. Поэтому для получения информации о парах некасающихся контуров достаточно использовать лишь ее верхнюю или нижнюю треугольные части.
Матрица F2 определяется с помощью булева произведения матрицы Z на результат ее транспонирования Zт, то есть
(8.4)
Для нашего примера верхняя треугольная часть имеет вид
Чтобы сформировать формулу i-й группы осуществляется последовательный обход матрицы от i-й до последней строки, в ходе которого путем поиска нулевых элементов матрицы выполняется построение дерева сочетаний некасающихся с i-м контуром контуров графа. Обход последнего дерева позволит сформировать формулы i-й группы Di.
На рис. 8.4 представлены деревья сочетаний некасающихся контуров и формулы всех групп контуров.
При известных формулах всех n-групп контуров определитель графа вычисляется с помощью выражения
(8.5)
Алгоритмизация выражения (8.5) осуществляется последовательным наращиванием формулы на каждом этапе формирования i-й группы.