«Графы и их обходы». [ЗВУК] [ЗВУК] Когда я был маленький, папа мне задал такую задачу: «Дан кубик. [ЗВУК] Нужно стартовать из какой-нибудь вершины и пройти по каждому ребру ровно один раз, при этом обойдя все рёбра, попав везде, по всем рёбрам пройдя». Вот такая задача. Я был маленький и наивно думал, что раз папа дает задачу, значит, её можно решить. Ходил, ходил, ходил, ходил, всё никак не получалось. Потом я подошел к папе и сказал: «Папа, а это возможно или нет, сделать?» «Ха-ха-ха-ха-ха. Я просто над тобой пошутил. Конечно, это сделать невозможно. Докажи это». «Так я сейчас как раз и собирался тебе объяснить, почему это нельзя». Давайте попробуем вместе с вами понять, что это сделать действительно невозможно. Смотрите. Что произойдет с разными вершинами, когда я буду идти так, как требуется? Я стартовал, куда-то прошел через какую-то одну вершину, я прошел через неё и отправился дальше. В этом случае я обязательно по какому-то ребру вошел, а по кому-то вышел. Правда? Вот теперь смотрите. Если мой путь не заканчивается в этой вершине, то тогда я уже в неё попасть никак не могу, потому что по этим двум рёбрам мне пройти больше нельзя — запрещено. По одному разу надо ходить. А если я пойду по этому ребру, то я уже не смогу из этой вершины больше никуда уйти. Поэтому получается такое утверждение, что: любая вершина, из которой исходит нечётное количество рёбер, (это уже утверждение общее, не про наш куб, а вообще совершенно общее утверждение, про задачу обхода), что если вы делаете обход какой-то такой вот конфигурации точек и отрезочков, то любая вершина, из которой исходит нечётное число отрезочков, она должна быть либо началом вашего пути обхода, либо концом. Но в нашем кубе все вершины, все восемь штук, являются такими нечётными вершинами. То есть из каждой такой вершины исходит ровно три ребра. И поэтому совершенно ясно, что у одного и того же пути никак не может быть больше двух начального и конечного пунктов, то есть больше двух пунктов, в которых входится три ребра, а всего их восемь. Поэтому понятно, что обойти их все не получится заданным условием то есть обойти все рёбра по одному разу не выйдет. Более того, мы можем даже теперь на основании этого примера сказать, какое условие для возможности обхода является необходимым. Необходимым является условие, чтобы количество вершин, в которых сходится нечётное число рёбер, должно быть равно двум. И только так. Двум или одному, или нулю, то есть не больше двух. Если их две, мы можем в одной из них начать, в другой закончить. Если одна, тогда неважно — заканчиваем, начинаем в ней. А если их нет, тогда никаких ограничений вот таких визуальных нет. То есть если вам дается какая-то конфигурация вот таких точечек и отрезочков, и предлагается пройти по всем отрезкам ровно по одному разу, то вам нужно первым делом посчитать количество вершин, в которых сходится нечётное количество отрезков. И если это количество больше чем два, вы сразу говорите: «Так. До свидания. Это сделать невозможно по очевидным причинам». Возникает такой вопрос: «А верно ли обратное утверждение?» То есть верно ли, что препятствий больше никаких нет. Если вы увидели вот такую конфигурацию и в ней не более двух вершин такого вида, то что из этого следует? Можно обойти или нельзя? Оказывается, ответ — «да». Это такое техническое доказательство, что называется доказательство по индукции по количеству рёбер или вершин. Мы не будем его здесь проводить. Я просто вам передаю такой ответ, что если вам дали конфигурацию, в которой не более двух вершин нечётной степени, то есть с нечётным количеством выходящих рёбер, то дерзайте. У вас всегда получится эту конфигурацию обойти. Конечно, если она из одного куска состоит, а не из двух разных. Значит, ещё один интересный факт, который я тоже вам сообщаю и предлагаю всем его доказать, состоит в том, что одной такой вершины быть не может. Если есть одна вершина с нечётным числом выходящих рёбер, то тогда где-то ещё в этой конфигурации обязательно встретится еще одна. То есть их либо ноль, либо две, либо значит, соответственно, больше. Их всегда чётное число. Но факт тот, что если их ноль и две, то обойти можно; если больше, то обойти нельзя. Такие конфигурации носят специальное название. Их называют «графы». То есть графом формально называется просто любая картинка из точек и соединяющих их отрезков в любом сколь угодно хаотическом виде и порядке, то есть нет никаких дополнительных условий. Просто граф — это набор точек и некоторых отрезков, их соединяющих. Понятие графа, судя по всему, восходит к Эйлеру. Он придумал сам вот эту задачу. А именно, он жил в городе Кёнигсберг, нынешний Калининград. И там было некоторое количество мостов. Он всем предлагал попробовать обойти все мосты Кёнигсберга по одному разу. Но и это ни у кого не получалось сделать по совершенно очевидным причинам. Давайте посмотрим на картину, которая представляет из себя город Кёнигсберг с этими мостами. Мы можем острова назвать точками, то есть берега назвать точками, а мосты назвать отрезками. После того, как мы перевели вот этот город в схематический план, у нас получился граф. В этом графе, как мы видим, не выполнено условие, которое необходимо для того, чтобы обход можно было осуществить. Поэтому задача Эйлера решения не имеет.
