Эксперт по сдаче вступительных испытаний в ВУЗах
Практическое занятие 12 2 семестр
Остовные деревья
1. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
2. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
3. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
4. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
5. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
6. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
7. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
8. Задан граф, вершины которого упорядочены так, как помечены.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
9. Задан граф Петерсена.
а) Найти остовное дерево, удаляя ребро из каждого цикла.
б) Найти остовное дерево поиском в ширину.
в) найти остовное дерево поиском в глубину.
10. Используя алгоритм ПТС поиска точек сочленения, найти точки сочленения и компоненты двусвязности для графа.
11. Используя алгоритм ПТС поиска точек сочленения, найти точки сочленения и компоненты двусвязности для графа.
12. Используя алгоритм ПТС поиска точек сочленения, найти точки сочленения и компоненты двусвязности для графа.
13. Используя алгоритм ПТС поиска точек сочленения, найти точки сочленения и компоненты двусвязности для графа.
14. Используя алгоритм ПТС поиска точек сочленения, найти точки сочленения и компоненты двусвязности для графа.
15. Используя алгоритм преобразования дерева в последовательность, определить соответствующую последовательность для каждого дерева.
16. Используя алгоритм преобразования дерева в последовательность, определить соответствующую последовательность для каждого дерева.
17. Используя алгоритм перевода дерева в последовательность, построить соответствующие деревья для приведенных последовательностей.
а) 1, 2, 3, 3, 2, 3.
б) 1, 3, 3, 5, 5, 4, 4.
в) 9, 8, 10, 10, 1, 8, 9, 1.
18. Используя алгоритм перевода дерева в последовательность, построить соответствующие деревья для приведенных последовательностей.
а) 1, 4, 2, 3, 2, 3.
б) 1, 4, 3, 3, 4, 4, 4.
в) 1, 5, 2, 5, 3, 6, 5, 5.
19. Используя матричную формулу Кирхгофа, определить число остовных деревьев для каждого графа.
20. Используя матричную формулу Кирхгофа, определить число остовных деревьев для каждого графа.
Ссылка на первоисточник:
http://ktek-kostroma.ru
