Отлично. Давайте теперь порассуждаем про классическую задачу об обходе графа, а именно про задачу о кёнигсбергских мостах. Вот такая была замечательная классическая задача, предложенная в XVII веке... Нет, как в XVII? В XVIII, конечно, веке, я уже путаюсь. 1700 — это конечно XVIII век, во времена, когда Эйлер писал свои замечательные работы. Значит, это задача о кёнигсбергских мостах. Сама задача формулировалась очень просто. Давайте я нарисую эту картинку, я, видимо, уже ее рисовал однажды. Рисую я, правда, очень плохо, вот тут надо понимать, что картинка будет, конечно, не такая замечательная, как обычно получается в учебнике, но уж какая получится. Сейчас вот я нарисую условную реку, то есть вот здесь у меня суша, и здесь у меня тоже суша, а здесь есть два острова на реке. И вот эти два острова, во-первых, между собою соединены мостом, а во-вторых, каждый из них соединен двумя мостами с одной частью суши, так, и двумя мостами... Нет, подождите, подождите, нет, этот только одним мостом, этот только одним мостом, и здесь тоже только один, а вот этот двумя. Значит вот такая вот получается картинка. И задача, которая была в те времена, она формулировалась очень просто. Был такой вопрос: можно ли найти какую-нибудь часть суши, то есть вот эту часть суши, эту часть суши или один из островов, таким образом, чтобы, стартуя из этой части суши, пройти по всем мостам, которые у нас имеются в распоряжении, при этом пройти по каждому мосту ровно один раз и вернуться в исходную часть суши. Ну например, стартовать вот с этого острова, пройти как-то там по всем мостам, и при этом ни разу не дублируя свою дорогу, не возвращаясь по тому же мосту, по которому уже проходил, и вернуться на этот остров. Или ну вот если с этим островом так не получается, может быть, получится с этой частью суши: начать отсюда и пройти по всем мостам. Ну, на самом деле, я думаю, что слушатели совершенно хорошо понимают, почему в этой задаче ответ отрицательный. Такой части суши не существует. Очень просто сообразить. Но давайте ее сразу переведем на язык теории графов, дадим формальное определение, которое касается этой задачи для графов, и уже на языке теории графов эту задачу решим, объясним, почему она действительно имеет отрицательный ответ. Такого обхода не существует, ну и так далее, вложим это в общий контекст. Значит, смотрите, давайте каждую часть суши обозначать вершиной графа. То есть у нас получится условно вот такие три вершины, которые отвечают вот этой части суши, этому острову и вот этой части суши, и еще будет одна вершина, которая соответствует вот этому острову. Ну а мосты, естественно будем изображать ребрами нашего графа. У нас получится вот такая вот картинка два моста здесь — два ребра, два моста здесь — тоже два ребра. Так, одно ребро соединяет второй остров, правый остров с нижней частью суши. Тут тоже есть ровно одно ребро. И тут есть ровно одно ребро. То есть мы имеем дело с типичным мультиграфом в нашей терминологии. С мультиграфом, потому что у него присутствует две пары кратных ребер. Вот, ну уже глядя на этот граф, совсем легко сказать, почему такого обхода нет. И какой вообще обход-то мы хотим получить? Мы хотим стартовать с какой-то вершины, и, пройдя по ребрам, обойти все ребра, вернуться в ту же самую вершину и при этом пройти по каждому ребру ровно один раз. Ровно один раз. Почему не существует такого обхода? Ну вот смотрите, вот есть вот эта вершина. Ясно, что если бы такой обход существовал, вы должны были бы войдя в эту вершину по какому-то ребру, по какому-то другому ребру из нее выйти. То есть всякий раз, когда вы появляетесь в этой вершине, зайдя в нее, вы должны выйти по другому ребру, иначе вы нарушите условие непрохождения каждого моста ровно по одному разу. Ну понятно, что тогда степень этой вершины должна быть четным числом, а она, к сожалению, таковым не является. Вот, собственно говоря, и вся недолга. Конечно, Эйлер, который занимался этой задачей, сделал гораздо больше. И вот что сделал Эйлер в этом месте, я сейчас как раз и расскажу. Значит, давайте в общем случае дадим определение эйлерова цикла в графе. То есть пусть дан какой-то граф, мы будем говорить, что этот граф является эйлеровским, или, что то же самое, он содержит эйлеров цикл, если... Ну вот, если ровно то самое и происходит: существует какая-нибудь вершина, стартуя из которой, вы можете пройти по всем ребрам ровно по одному разу по каждому и вернуться в эту вершину. То есть фактически граф представляет собою цикл в нашем стандартном определении маршрута. Ну вот, эйлеровский граф — это и есть граф, который представляет собою цикл.