Теория графов. Поиск циклов длины 3 и 4
Задан граф матрицей смежности. Необходимо найти циклы длины 3 и 4. Матрица смежности возводится в степень 3 или 4... дальнейший алгоритм мне известен. Однако препод в универе задаёт один вопрос: почему мы именно умножаем матрицы (возводим в степень), а не, к примеру, складываем их или умножаем на 3 или 4. Буду признателен, если кто-нибудь объяснит этот момент
Ответы (1 шт):
По индукции можно доказать.
Для самой матрицы смежности единицы стоят в ячейках, соответствующих путям длиной 1. Значит, свойство для степени 1 выполняется.
Пусть ячейки матрица B=A^n содержат количества путей, т.е. Bik - количество путей из вершины i в вершину k длиной n. По определению при умножении матрицы B на A элемент матрицы С=A^(n+1)
Сij = sum[k=1..size] Bik*Akj
а это сумма количеств путей длиной n+1, состоящих из путей длиной nиз i в k, плюс количество путей длиной 1 из k в конечную вершину j. Итак, свойство сохраняется при увеличении степени матрицы.