Давайте обсудим, как же можно использовать графы. Графы являются очень универсальной моделью, и позволяют в общем виде изучать ситуации, которые возникают в самых разных задачах. Мы подробно обсудим разные универсальные факты о графах, но оказывается, что иногда бывает полезно просто даже изобразить задачу в виде графа, и это уже сильно помогает. Давайте рассмотрим такой пример. Пусть у нас есть такая задача: у нас есть шахматная доска три на три (как на картинке), и мы хотим переставить коней так, как нарисовано на картинке, — мы хотим, чтобы белые кони оказались сверху, а черные кони оказались снизу. Можно ли так сделать? Напомню правила, как ходит шахматный конь: шахматный конь ходит буквой "г" в любом направлении. Он может сместиться либо на два поля по горизонтали и на одно поле по вертикали после этого (это вот такие возможные ходы), либо на два поля по вертикали и на одно поле по горизонтали (это вот такие возможные ходы); вот все возможные ходы шахматного коня. Итак, давайте вернемся к нашей задаче. Вот наши кони. Сделаем следующее: заведем вершину графа для каждого поля, в которое может попасть конь. Видно, что это все поля, кроме центрального: в центральное поле попасть нельзя, если пользоваться правилами хода коня. Давайте отдельно нарисуем картинку, на которой мы эти вершины немножко переставим: мы вершину "пять" переставим налево, вершину "четыре" — направо, "два" — вниз и "семь" — вверх. Хорошо, зачем же мы это сделали? Соединим некоторые вершины ребрами. Давайте соединим ребрами те вершины, для которых из одной можно попасть в другую за один ход конем: слева видно, что мы так и соединили вершины. Тогда давайте перенесем эти ребра направо, и видно, что справа получается очень такой простой граф, циклический. Теперь поставим на него наших коней, и вот теперь уже более или менее видно, как решать нашу задачу: давайте просто представлять коней по циклу. Для начала мы можем, например, просто сдвинуть всех коней на одно поле, давайте просто последовательно это сделаем: сначала белого, потом другого белого, потом черного и черного. Видно, что теперь все кони сдвинулись на одно поле по циклу, и мы можем продолжить, сделать так еще три раза, и черные кони окажутся внизу, а белые окажутся наверху. Хорошо, раз уж мы это обсуждаем, давайте обсудим еще одну близкую задачу. Можно ли переставить коней следующим образом: так, чтобы кони стояли по диагонали — белые кони стояли по диагонали друг от друга и черные тоже? Давайте сразу перейдем к нашей картинке. Вот наша изначальная картинка нарисована слева, вот так кони стоят вначале, а вот так мы хотим их расставить. Можно ли это сделать? Видно, что слева кони стоят последовательно, в смысле, что белые кони стоят последовательно друг после друга, и черные тоже, а на правой картинке они стоят через один. И видно, что если мы просто сдвигаем коней по циклу (а это наши разрешенные ходы), то это свойство будет сохраняться. То есть если мы в левой картинке начнем сдвигать коней, то, как бы мы их ни сдвигали, они будут по-прежнему стоять последовательно: если мы смотрим на них по циклу, сначала будут белые кони, они будут рядом, и черные кони будут рядом. Так что получить правую картинку невозможно, кони просто не могут поменяться местами на этом цикле.