Рубрики

Структуры данных | График | Вопрос 9

Какое из следующих утверждений является ИСТИННЫМ для ненаправленного графа?
P: число вершин нечетной степени четное
Q: сумма степеней всех вершин четна
(A) P Только
(B) Q Только
(C) и P и Q
(D) Ни P, ни Q

Ответ: (с)
Объяснение: P верно для ненаправленного графа, так как добавление ребра всегда увеличивает степень двух вершин на 1.

Q верно: если мы рассмотрим сумму степеней и вычтем все четные степени, мы получим четное число, потому что каждое ребро увеличивает сумму степеней на 2. Таким образом, общее число вершин нечетных степеней должно быть четным.
Тест на этот вопрос

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

Структуры данных | График | Вопрос 9

0.00 (0%) 0 votes