Материал: 2570
Программы визуализации неориентированного графа.
Нумерация вершин графа на рисунке
соответствует направлению движения
часовой стрелки. Если граф связный, то
можно решать задачу.
Определение остова неориентированного графа G
Подпрограмма задания начального значения вектора вершин графа V.
Подпрограмма подсчета эксцентриситета вершины графа G.
Подпрограмма вывода вектора эксцентриситетов вершин графа G.
Подпрограмма нахождения остова и хорд графа G:
Остов
графа G:
Хорды графа G:
Столбец матрицы Hr соответствует вершинам, которые инцидентны хорде.
N - матрица хорд.
Нахождение базисных циклов графа G
Os - матрица смежности остова графа G; Hr - матрица хорд; n - число базисных циклов; d - количество ребер; i - количество вершин в графе G.
Подпрограмма вывода матрицы инцидентности.
Подпрограмма поиска базисных циклов графа G.
Цикломатическая матрица графа G.
2. Задания к лабораторной работе
По заданию преподавателя в системе MATHCAD составить программы для моделирования сложной системы по описанной выше методике.
Вариант 1 Вариант 6
|
1 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
G = |
1 |
1 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
0 |
G = |
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
1 |
1 |
Определение линейно зависимых циклов графа G
n - число базисных (линейно независимых) циклов (см. п.3).
Формула вычисления количества линейно зависимых циклов:
Линейно зависимые циклы получаются путем сложения базисных циклов по модулю 2. Эти циклы здесь не представлены в связи с большим объемом вычислений.
Построение матрицы разрезов графа G
Os - матрица смежности остова графа G; Hr - матрица хорд; n - число базисных циклов.
Подпрограмма вычисления достижимости вершины i остова графа G.
Подпрограмма вычисления матрицы разрезов графа G.
Матрица разрезов графа G:
Вариант 2 Вариант 7
|
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
G = |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
G = |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |