В этом задании задан орграф. Имеется два ориентированных ребра (3-2). Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
В этом задании задан орграф. Имеется два ориентированных ребра (3-2)

В этом задании задан орграф. Имеется два ориентированных ребра (3-2) .pdf

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

Условие

В этом задании задан орграф. Имеется два ориентированных ребра (3-2), (5-3); найти все пути и сечения между вершинами i=3, j=5.

Решение

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

Составим структурную матрицу графа.
1 2 3 4 5
1 1 a b 0 0
2 a
1 0 d 0
3 b
c 1 k 0
4 0 d
k
1 g
5 0 0 f g
1
Найдем минор M53:
M63=1 a b 0 0a 1 0 d 0b c 1 k 00 d k 1 g0 0 f g 1=11 a b 0a 1 0 db c 1 k0 d k 1⋁g1 a b 0a 1 0 db c 1 k0 0 f g=
=1 0 dc 1 kd k 1 ⋁aa 0 db 1 k0 k 1⋁ba 1 db c k0 d 1⋁fg1 a 0a 1 db c k⋁gg1 a ba 1 0b c 1==1⋁cdk⋁dd⋁kk⋁aa⋁bdk⋁akk⋁bac⋁bdd⋁b⋁adk⋁
⋁fgk⋁abd⋁cd⋁aak=
=cdk⋁abdk⋁abc⋁fgk⋁abdfg⋁cdfg .
Каждая конъюнкция полученной ДНФ определяет набор ребер графа, образующий простой путь. Знаки отрицаний в результате игнорируются.
В полученном результате можно расположить ребра в порядке прохождения каждого пути между вершинами 5 и 3. Искомые пути, расположенные в порядке прохождения ребер:
P35= cdk⋁badk⋁bac⋁fgk⋁badgf⋁cdgf.
Сечением между вершинами vi и vj в простом связном графе G называют неизбыточную совокупность рёбер графа, после удаления которой из графа не существует маршрута из vi в vj, но при возвращении в граф хотя бы одного из элементов сечения маршрут из vi в vj восстанавливается.
Сечения получаются отрицанием полученных путей:
S35=P35= cdk⋁badk⋁bac⋁fgk⋁badgf⋁cdgf=
=c⋁d⋁kb⋁a⋁d⋁kb⋁a⋁c(f⋁g⋁k)b⋁a⋁d⋁g⋁f(c⋁d⋁g⋁f)=
=c⋁d⋁gk⋁fkb⋁a⋁d⋁gk⋁fk(bf⋁bg⋁bk⋁af⋁ag⋁ak⋁cf⋁cg⋁ck)=
=cbf⋁cbg⋁cbk⋁acg⋁acf⋁ack⋁cdk⋁cgk⋁cfk...
Здесь каждая конъюнкция определяет набор ребер, образующих сечение.

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

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

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