АиСД-2. 2024-2025. ПЗ-Тест №16. Графы. Часть 2. В1

Какие графы НЕ являются деревьями?

• 
• 
• 
• 

Сколько ребер имеет минимальное остовное дерево?

• Число ребер больше числа вершин на 1

• Число ребер меньше числа вершин на 1

• Число ребер зависит от того, какой алгоритм применяется

Сколько остовных деревьев имеет данный граф?

• 1

• 3

• 4

• 8

Временные затраты операции find(x) в неоптимизированной
реализации UNION-FIND составляют

Применение UNION-FIND в алгоритме Краскала оптимизирует...

• сортировку ребер
  графа по их весу

• проверку того, что добавление ребра образует цикл

• выбор ребра с
  минимальным весом

Сколько различных минимальных остовных деревьев имеется в заданном графе?

• 4

• 5

• 6

• Бесконечно много!