Лабораторная 6-7. Элементы теории графов Лабораторная работа 6 Поиск компонент связности
 Скачать 30.5 Kb.
|
|
Лабораторная работа № 6 Поиск компонент связности Граф задан его матрицей смежности. Требуется определить количество компонент связности этого графа. При этом должны быть конкретно перечислены вершины, входящие в каждую компоненту связности. Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин. При выполнении работы разрешается (даже рекомендуется!) использовать матрицу бинарных отношений из лабораторной работы №2. Вход программы: число вершин графа и матрица смежности. Выход: разбиение множества вершин на подмножества, соответствующие компонентам связности. Дополнительно: Заданный граф – ориентированный. Выполнять поиск компонент сильной связности. Лабораторная работа № 7 Построение остовного дерева графа Граф задан его матрицей смежности. Требуется построить остов этого графа, используя поиск в глубину или в ширину. При этом должны быть конкретно перечислены все ребра, входящие в остов. Пользователю должна быть предоставлена возможность редактировать исходную матрицу, т.е. изменять исходный граф без выхода из программы. Предусмотреть также возможность изменения количества вершин. При выполнении работы разрешается использовать материалы предыдущей лабораторной работы. Вход программы: число вершин графа и матрица смежности. Выход: а) последовательность вершин, соответствующая выбранному варианту обхода графа. б) список ребер, составляющих остов графа. Дополнительно: Выполнить оба варианта обхода вершин графа. |