Система является полной так как целиком она не содержится во всех классах
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Система является полной, так как целиком она не содержится во всех классах. Базис (f2)
Дан граф. Составить для данного графа структурную матрицу. Найти: а) все простые пути из вершины i в вершину j; б) совокупность всех сечений между вершинами i и j.
Ответ
Простые пути в графе из вершины 1 в 4
1→5→3→2→4
1→5→3→4
1→2→4
Совокупность сечений:
e15e24;e53e24;e24e34;e15e12;e53e12;e32e34e12
Решение
Составим структурную матрицу:
а) найдем все простые пути из вершины 1 в 4:
Вычислим минорM41, заменяя сложение и вычитание на дизъюнкцию, а умножение на конъюнкцию.
M41=e121e320 001e53 0e24e340 e15001=e15 10e24e321e340e530+1 e120010e24e321e34=
=e15e32e53e24∨ e15 e53e34∨e24 e12=
Получили все простые пути:
1→5→3→2→4
1→5→3→4
1→2→4
б) найдем совокупность сечений между 1 и 4 вершиной:
e15∨e32∨e53∨e24 e15∨ e53∨e34 e24 ∨e12=
=(e15∨e32e15∨e53e15∨e24e15∨e15e53∨e32e53∨e53∨e24e53∨
∨e15e34∨e32e34∨e53e34∨e24e34) e24 ∨e12=
=(e15∨e53∨e32e34∨e24e34) e24 ∨e12=
=e15e24∨e53e24∨e32e34e24∨e24e34∨e15e12∨e53e12∨e32e34e12∨e24e34e12=
=e15e24∨e53e24∨e24e34∨e15e12∨e53e12∨e32e34e12
Получили совокупность сечений.
Ответ: Простые пути в графе из вершины 1 в 4
1→5→3→2→4
1→5→3→4
1→2→4
Совокупность сечений:
e15e24;e53e24;e24e34;e15e12;e53e12;e32e34e12