Контрольные задания > На рисунке изображён граф. Кирилл обвел этот граф, не отрывая бумаги и не проводя ни по одному ребру дважды. С какой вершины Ки обводить граф, если он закончил его обводить в вершине М?
Вопрос:

На рисунке изображён граф. Кирилл обвел этот граф, не отрывая бумаги и не проводя ни по одному ребру дважды. С какой вершины Ки обводить граф, если он закончил его обводить в вершине М?

Смотреть решения всех заданий с листа

Ответ:

Краткое пояснение: Чтобы пройти по графу, не отрывая карандаша и не проходя по ребру дважды, необходимо, чтобы все вершины графа, кроме двух, имели четную степень (четное количество ребер). Если таких вершин две, то начинать нужно с одной из них, а заканчивать в другой.

Пошаговое решение:

  • Посчитаем степени вершин:
    • A: 2
    • B: 4
    • C: 2
    • D: 4
    • K: 3
    • N: 3
    • M: 2
  • Вершины K и N имеют нечетную степень (3). Значит, начинать обход нужно с одной из них, а закончить в другой.
  • По условию, закончили обход в вершине M, значит, начинать нужно в вершине N или K. Но так как требуется только одна вершина, то это может быть K.

Ответ: K

ГДЗ по фото 📸
Подать жалобу Правообладателю

Похожие