Контрольные задания
Вопрос:

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

Фото задания: 4. Саша хочет обвести граф, изображённый на рисунке, не отрывая карандаша от листа бумаги и не проводя ни одно ребро…Фото задания

Ответ:

Краткое пояснение:

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

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

  1. Определяем степень каждой вершины (количество ребер, исходящих из нее):
    • A: 3 (нечетная)
    • B: 3 (нечетная)
    • C: 2 (четная)
    • D: 2 (четная)
  2. В графе две вершины с нечетной степенью: A (3) и B (3).
  3. Так как в графе две вершины с нечетной степенью, то обход можно начать с любой из них и закончить в другой.
  4. Следовательно, Саша может начать обводить граф с вершины А или с вершины В.

Ответ: А или В