Используя метод Магу, найти (а) все максимальные внутренне устойчивые множества; (б) все минимальные внешне устойчивые множества вершин орграфа , заданного матрицей смежности ; (в) ядра (или доказать, что их нет).

Добавлена: 07.05.2026
Обновлена: 07.05.2026
Предмет: Теория управления
Автор: Кэмп

#Методы оптимизации и принятия решений
#Теория динамических систем

Условие:

Используя метод Магу, найти (а) все максимальные внутренне устойчивые множества; (б) все минимальные внешне устойчивые множества вершин орграфа $D$ , заданного матрицей смежности $A(D)$ ; (в) ядра (или доказать, что их нет).

A(D)=\left[a_{i j}\right]_{4 \times 4}=\left( \begin{array}{llll} 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right)

Решение:

Мы имеем орграф D с вершинами 1,2,3,4 и матрицей смежности

0 0 1 0
1 0 1 0
0 0 0 1
0 0 1 0

Из матрицы видим, что в графе есть следующие дуги:
• 1 → 3
• 2 → 1
• 2 → 3
• 3 → 4
• 4 → 3

Обозначим конфликтную пару (две вершины, между которыми есть дуга в любом направлении) так:
– Между 1 и 3 (так как есть 1 → 3)
– Между 1 и 2 (так как есть 2 → 1)
– Между 2 и 3 (так как есть 2 → 3)
– Между 3 и 4 (так как есть 3 → 4 и 4 → 3)

Ниже пошагово решим...