Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 4

Пусть G — неплоский граф с минимально возможным числом ребер. Тогда G имеет
(A) 9 ребер и 5 вершин
(B) 9 ребер и 6 вершин
(C) 10 ребер и 5 вершин
(D) 10 ребер и 6 вершин

Ответ: (Б)
Пояснение: Согласно теореме Куратовского граф является плоским тогда и только тогда, когда он не содержит каких-либо подразделений графов K 5 или K 3,3 .

Это означает, что K 5 и K 3,3 являются минимальными неплоскими графами. Эти графы имеют 5 вершин с 10 ребрами в K 5 и 6 вершин с 9 ребрами в графе K 3,3 .
Итак, граф K 5 имеет минимум вершин и максимум ребер, чем K 3,3 .

Таким образом, вариант (B) является правильным.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2007 | Вопрос 4

0.00 (0%) 0 votes