Рубрики

ВОРОТА | GATE CS 2010 | Вопрос 1

Пусть G = (V, E) — граф. Определим ξ (G) = Σd id xd, где id — количество вершин степени d в G. Если S и T — два разных дерева с ξ (S) = ξ (T), то
(A) | S | = 2 | T |
(B) | S | = | T | -1
(C) | S | = | T |
(D) | S | = | T | +1

Ответ: (с)
Пояснение: Выражение ξ (G) — это сумма всех степеней в дереве. Например, в следующем дереве сумма равна 3 + 1 + 1 + 1.

    a 
  / | \
 b  c  d

Теперь возникает вопрос: если сумма степеней в деревьях одинакова, то какова связь между количеством вершин, присутствующих в обоих деревьях?
Ответ таков: ξ (G) и ξ (T) одинаковы для двух деревьев, тогда деревья имеют одинаковое количество вершин. Это можно доказать по индукции. Пусть это будет верно для n вершин. Если мы добавляем вершину, то новая вершина (если это не первый узел) увеличивает степень на 2, не имеет значения, где мы ее добавляем. Например, попробуйте добавить новую вершину, скажем, «e» в разных местах в приведенном выше примере.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2010 | Вопрос 1

0.00 (0%) 0 votes