|
Вернуться на страницу "Банк студенческих задач"
 Архив разработки (36 Кб, Mathcad-документ)
Содержание
1. Генерация матрицы смежноcти неориентированного графа размерности w
2. Определение наибольшего независимого множества вершин и вершинного числа внутренней устойчивости a0(G) графа G
3. Определение наибольшего независимого множества ребер и числа паросочетаний a1(G) графа G
Генерация матрицы смежноcти неориентированного графа размерности w
Reference: VisualGraph_1.mcd
 -порядок матрицы смежности (размерность графа G)
Определение наибольшего независимого множества вершин и вершинного числа внутренней устойчивости a0(G) графа G
|
 наибольшее независимое множество вершин
 его мощность является числом
внутренней устойчивости графа G.
|
|
Определение наибольшего независимого множества ребер и числа паросочетаний a1(G) графа G
 - Выделяем Все ребра
 - матрица ребер
Строим Матрицу смежности для графа, в котором веришинами являются ребра исходного графа. Две вершины в новом графе будут смежны тогда и только тогда, когда соответствующие им ребра в исходном графе тоже смежны.
|
Новая матрица смежности (для ребер).
|
|
Используем функцию по нахождению наибольшего независимого множества вершин.
|
|
Наибольшее независимое множество
вершин для графа, матрица смежности
которого - M_Inc.
|
|
|
Матрица для ребер, с которыми будем ассоциировать найденное независимое
множество ребер.
|
Ассоциируем найденные вершины нового графа с соответствующими ребрами исходного графа.
 наибольшее независимое множество ребер
Вернуться на страницу "Банк студенческих задач"
|
число паросочетаний
