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

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

• Подсчитаем количество ребер, выходящих из каждой вершины графа:
  
  
  
  • Вершина K: 3 ребра (KC, KD, KB)
  
  
  • Вершина D: 3 ребра (DK, DA, DB)
  
  
  • Вершина B: 3 ребра (BK, BF, BD)
  
  
  • Вершина F: 3 ребра (FB, FA, FN)
  
  
  • Вершина N: 2 ребра (NF, NA)
  
  
  • Вершина A: 4 ребра (AC, AD, AF, AN)
  
  
  • Вершина C: 2 ребра (CK, CA)
  
  
  
  


• Вершины K, D, B и F имеют нечетное количество ребер (3), а вершины N, A и C – четное количество ребер.


• По условию, Алла начинает обводить граф из вершины K. Следовательно, она закончит в одной из вершин с нечетным количеством ребер (D, B, F).


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


• Один из возможных путей обхода:
  
  
  
  • K → C → A → D → B → F → N → A → K → D → B → F
  
  
  
  

Ответ: N