Дан граф. Составить для данного графа структурную матрицу. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Дан граф. Составить для данного графа структурную матрицу

Дан граф. Составить для данного графа структурную матрицу .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Дан граф. Составить для данного графа структурную матрицу. Найти: а) все простые пути из вершины i в вершину j; б) совокупность всех сечений между вершинами i и j. i=3, j=1

Ответ

а) Простые пути в графе из вершины 3 в 1 3→2→1 3→5→2→1 б) Совокупность сечений: e21 ∨e32e52∨e32e35

Решение

Потяни, чтобы посмотреть

Составим структурную матрицу:
S=1e12000 e121e320e25 001e43e350001 e45 e15e25e35e451
а) найдем все простые пути из вершины 3 в 1:
Вычислим минор , заменяя сложение и вычитание на дизъюнкцию, а умножение на конъюнкцию.˅
M13=e12000 1e320e25 001e45 e25e35e451=e12 e320e3501e45e25e451=
=e12e32∨ e12 e25 e35∨e12 e32e45e45=e12e32∨ e12 e25 e35
Получили все простые пути:
3→2→1
3→5→2→1
б) найдем совокупность сечений между 3 и 1 вершиной:
e21∨e32 e21 ∨e52∨e35=
=e21 ∨e21e52∨e21e35∨e32e21 ∨e32e52∨e32e35=
=e21 ∨e32e52∨e32e35
Получили совокупность сечений.
Ответ: а) Простые пути в графе из вершины 3 в 1
3→2→1
3→5→2→1
б) Совокупность сечений:
e21 ∨e32e52∨e32e35

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу