Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 36

Сколько существует идеальных совпадений в полном графе из 6 вершин?
(А) 15
(Б) 24
(С) 30
(D) 60

Ответ: (А)
Объяснение: Идеальное сопоставление, каждая вершина графа инцидентна ровно одному ребру сопоставления. Таким образом, идеальное совпадение — это сопоставление графа, содержащего n / 2 ребер, максимально возможное, что означает, что идеальное сопоставление возможно только на графах с четным числом вершин. (Источник http://mathworld.wolfram.com/PerfectMatching.html )
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2003 | Вопрос 36

0.00 (0%) 0 votes