===== №113 =====

Результат Задачи ММ113 учитывается дважды: в тематическом конкурсе и в основном Марафоне. 

**Конкурсная задача ММ113 (Ш-3)[/color]** (10 баллов)

На множестве полей шахматной доски определим структуру графа G<sub>N</sub> следующим образом:
две вершины (два поля) будем считать смежными, если конь может за один ход переместиться из одной вершины в другую.
Аналогично определим граф слона G<sub>B</sub>, граф ладьи G<sub>R</sub>, граф ферзя G<sub>Q</sub> и граф короля G<sub>K</sub>.
Для каждого из этих графов:\\
1. Найти\\
а) количество ребер;\\
б) количество компонент связности;\\
в) радиус и диаметр каждой компоненты;\\
г) наибольшую клику.\\
2. Выяснить является ли граф:\\
а) двудольным;\\
б) эйлеровым;\\
в) гамильтоновым;\\
г) планарным?

**Решение**

Ответы на большинство пунктов задачи находятся легко. Поэтому приведу лишь краткие пояснения к решению и 
ответ в виде таблицы.

**1.а.** Количество ребер большинства графов легче всего найти как полусумму степеней всех вершин. 
Разумеется, при этом следует использовать симметричность доски.
Например, для графа коня искомое число ребер равно (4*2 + 8*3 + 20*4 + 16*6 + 16*8)/2 = 168.
Для графа ферзя проще просто просуммировать количества ребер в графах ладьи и слона.

**1.б.** У графа слона две компоненты связности (черные и белые поля). Остальные графы, очевидно, связны.

**1.в.** Диаметр и радиус графов ладьи и ферзя, а также каждой компоненты связности графа слона, очевидно, равны 2.
Тривиально проверяется, что из каждого из полей d4, d5, e4, e5 король может добраться до любого поля не более чем за 4 хода. Поэтому радиус графа короля - 4.
В то же время, на маршрут от любого края до противоположного края доски королю понадобится 7 ходов. Поэтому диаметр графа короля - 7.
Наиболее содержательная задача - нахождение диаметра и радиуса графа коня. Ее можно решить, найдя поиском в ширину эксцентриситеты всех вершин графа коня.
Поиск в ширину можно провести в табличке 8х8 клеток вручную: помещаем 0 в начальную клетку; ставим 1 во все клетки, смежные начальной; ставим 2 во все свободные клетки, смежные клеткам. помеченным 1; и т.д.
В последней заполненной клетке будет записан эксцентриситет начальной вершины.
Разумеется, нет никакой необходимости применять данный алгоритм ко всем 64-м вершинам графа коня. По соображениям симметрии достаточно обследовать поля a1, b1, b2, c1, c2, c3, d1, d2, d3, d4.  

**1.г.** Наибольшие клики в графах слона (большая диагональ) ладьи (любая горизонталь или вертикаль) и ферзя содержат по 8 вершин. 
Наибольшая клика в графе короля (любой квадрат 2х2) содержит 4 вершины. 
Поскольку среди любых трех полей найдутся, по крайней мере, два одноцветных, в графе коня не может быть клики, содержащей более двух вершин.  

**2.а.** Граф коня (в котором смежными могут быть только разноцветные поля) двудолен.  
Наличие клик, содержащих более двух вершин, гарантирует отсутствие двудольности в остальных графах.

**2.б.** Граф ладьи, степень каждой вершины которого равна 14, эйлеров. В остальных графах есть вершины нечетных степеней.

**2.в.** Граф слона не связен и потому не гамильтонов. Гамильтонов цикл в графе коня и в остальных графах (один для всех) приведены на рисунках, заимствованных у Николая Дерюгина.

{{:marathon:113_1.jpg|:pic_113_1}} {{:marathon:113_3.jpg|:pic_115_2}}

**2.г.** Ни один из графов не планарен. В графах слона, ладьи и ферзя есть пятивершинные клики, а в графах короля и коня легко отыскать подграфы, стягиваемые, например, к K<sub>3,3</sub>.

Ответ:

^ Graph ^ Edges ^ Components ^ Diameter ^ Radius ^ Clique ^ Bichrom ^ Euler ^ Hamilton ^ Planar ^ 
| G<sub>N</sub> |  168  |  1  |  6  |  4  |  2  |  +  |  -  |  +  |  -  | 
| G<sub>B</sub> |  280  |  2  |  2  |  2  |  8  |  -  |  -  |  -  |  -  | 
| G<sub>R</sub> |  448  |  1  |  2  |  2  |  8  |  -  |  +  |  +  |  -  | 
| G<sub>Q</sub> |  728  |  1  |  2  |  2  |  8  |  -  |  -  |  +  |  -  | 
| G<sub>K</sub> |  210  |  1  |  7  |  4  |  4  |  -  |  -  |  +  |  -  | 

**Обсуждение**

Большинство пунктов задачи тривиальны. цена в 10 баллов отражает не сложность, а количество задачек, объединенных под общей шапкой ММ113. Правильность такого подхода косвенно подтвердили и сами участники, большинство из которых не обошлось без ошибок. Значительная часть этих ошибок была устранена марафонцами еще до публикации разбора задачи, а остальные нашли отражение в призовых баллах за задачу.  
Наиболее содержательный пункт задачи (о гамильтоновости графа коня) является, к сожалению, и наиболее известным. Поэтому я вполне согласен (что бывает со мной редко :)) с теми участниками, которые не слишком высоко оценили эстетическую сторону задачи, (хотя и с теми, кому задачка понравилась, тоже спорить не буду :)).

**Награды**

За решение задачи ММ113 Алексей Волошин получает 11 призовых баллов (1 балл добавлен за доскональное обоснование каждого пункта), Сергей Половинкин, Анатолий Казмерчук и Виктор Филимоненков получают по 10 призовых баллов, Николай Дерюгин и Кирилл Веденский получают по 9 призовых балла, а Эдвард Туркевич - 8 призовых баллов. 

**Эстетическая оценка задачи - 3.8 балла**
----