Теорема. Для того чтобы найти все пути (простые) из вершины i в вершину j достаточно раскрыть минор M(j,i) структурной матрицы методами булевой алгебры

Для того чтобы найти все пути (простые) из вершины i в вершину j достаточно раскрыть минор M(j, i) структурной матрицы методами булевой алгебры. При этом раскрытие минора производится обычными действиями с определителями, но при этом сложение заменяется дизъюнкцией, умножение – конъюнкцией, знаки умножения на числа не используются.

Подробно доказывать эту теорему не будем, но отметим, что определитель равен сумме (в данном случае дизъюнкции) элементов, взятых по одному из каждой строчки и каждого столбца с определенным знаком. В нашем случае знаки не присутствуют, а значит, любой член раскрытия определителя всей структурной матрицы T соответствует циклу в графе. Если же брать минор M(j, i), то его раскрытие соответствует тем членам определителя, в которых имелся элемент t(j, i), но без самого этого элемента (таким образом, индексы i и j встречаются вместо двух только один раз). Это и означает, что получаем маршрут от вершины с номером i к вершине с номером j.

Понятно, что раскрытие минора методами булевой алгебры предусматривает, что верны следующие соотношения: 1 a = 1, (это свойство нужно, для того чтобы не проходить по одному ребру дважды в противоположных направлениях), а также используется правило простого поглощения (). Видно, что если не использовать правило поглощения, то получим все маршруты (без повторения ребер), связывающие вершины i и j.

Если граф не ориентирован, то миноры M(j, i) и M(i, j) совпадают.

После получения ответа, черточки над обозначениями ребер (т. е. отрицания) можно убрать (на самом деле “черта” над ребром означает, что ребро проходится от вершины с большим номером к вершине с меньшим номером). Затем рекомендуется записать каждый путь по порядку прохождения ребер (в этом случае удобны обозначения ребер с индексами вершин).