Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 25

Какое наибольшее целое число m такое, что каждый простой связный граф с n вершинами и n ребрами содержит не менее m различных остовных деревьев?
(А) 1
(Б) 2
(С) 3
(D) n

Ответ: (с)
Объяснение: Граф связан, если все узлы могут быть пройдены от каждого узла. Для графа с n узлами будет n-1 минимальное количество ребер.
Учитывая, что существует n ребер, это означает, что в графе есть цикл.
Симплекс-граф с этими условиями может быть:

Теперь мы можем создать другое связующее дерево, удалив одно ребро из цикла, по одному за раз.
Минимальная длина цикла может быть 3, поэтому в любом таком графе должно быть как минимум 3 остовных дерева.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2007 | Вопрос 25

0.00 (0%) 0 votes