Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 85

GATE

G — граф на n вершинах и 2n — 2 ребрах. Ребра группы G можно разбить на два непересекающихся по ребрам остовных дерева. Что из следующего НЕ верно для G?
(A) Для каждого подмножества k вершин индуцированный подграф имеет не более 2k-2 ребер
(B) Минимальный разрез в G имеет как минимум два ребра
(C) Между каждой парой к вершинам есть два непересекающихся пути
(D) Есть две вершинно-непересекающиеся пути между каждой парой вершин

Ответ: (D)
Пояснение: Счетчик для варианта D выглядит следующим образом. Возьмите две копии K4 (полный граф на 4 вершинах), G1 и G2. Пусть V (G1) = {1,2,3,4} и V (G2) = {5,6,7,8}. Построим новый граф G3, используя эти два графа G1 и G2, объединившись в вершине, скажем, слияние (4,5). Результирующий граф связан с двумя ребрами минимальной степени 2, но существует отрезанная вершина, объединенная вершина.

Спасибо Renjith P за предоставленное объяснение.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2008 | Вопрос 85

0.00 (0%) 0 votes