На рис. изображен граф. В паре вершин Маша завершит обводить граф, если начнет обводить его из вершины K2.

Решение:

Граф представляет собой прямоугольник ABCD с диагоналями AC и BD, а также двумя дополнительными рёбрами, соединяющими вершины K2 и D, и K2 и A. В задании сказано, что Маша начнёт обводить граф из вершины K2.

• Вариант 1: Начинаем из K2, идём в D.
  K2 → D → B → A → C → K2. Все вершины посещены, и это замкнутый путь.
• Вариант 2: Начинаем из K2, идём в A.
  K2 → A → C → B → D → K2. Все вершины посещены, и это замкнутый путь.

Для того чтобы граф был «обведён», нужно пройти по всем его рёбрам ровно один раз. Такой путь называется Эйлеровым или Гамильтоновым, в зависимости от того, ставится ли условие возвращения в начальную вершину.

Если задача подразумевает посещение всех вершин, то из вершины K2 можно начать обход, как показано в вариантах 1 и 2.

Если же задача подразумевает прохождение по всем рёбрам графа ровно один раз, то это граф с вершинами K2, A, B, C, D и рёбрами: (K2, D), (D, B), (B, A), (A, C), (C, K2), (A, D), (B, C), (A, B), (C, D). Это более сложный граф, чем просто прямоугольник с диагоналями.

Однако, исходя из рисунка, вершины K2, D, B, A, C образуют пятиугольник с одним пересечением (или двумя вложенными треугольниками). Если K2, D, B, A, C — это вершины, и линии — это рёбра, то граф имеет 5 вершин.

Смотрим на рёбра:

1. K2-D
2. D-B
3. B-A
4. A-C
5. C-K2
6. K2-A
7. D-A
8. B-C

Степень каждой вершины:

• K2: 3 (рёбра K2-D, K2-C, K2-A)
• D: 3 (рёбра D-B, D-A, K2-D)
• B: 3 (рёбра B-A, B-C, D-B)
• A: 4 (рёбра A-C, A-B, D-A, K2-A)
• C: 3 (рёбра C-K2, C-A, B-C)

Для существования Эйлерова пути (все рёбра посещены ровно один раз) граф должен иметь 0 или 2 вершины с нечётной степенью. В данном графе 4 вершины с нечётной степенью (K2, D, B, C). Следовательно, Эйлерова пути нет.

Если же имеется в виду посещение всех вершин (Гамильтонов путь), то из K2 можно начать путь:

K2 → D → B → A → C (все вершины посещены).

Или K2 → C → A → D → B (все вершины посещены).

Ответ: Да, из вершины K2 можно начать обводку графа, чтобы посетить все его вершины (например, K2 → D → B → A → C).