Задача о Кенигсбергском мосте и пути Эйлера: можно ли нарисовать график, не отрывая ручки от бумаги? скачать в хорошем качестве

Задача о Кенигсбергском мосте и пути Эйлера: можно ли нарисовать график, не отрывая ручки от бумаги?

Что такое задача о Кёнигсбергских мостах? Задача о Кёнигсбергских мостах — известная топологическая головоломка, в которой нужно решить, как пересечь семь мостов в Кёнигсберге, не возвращаясь назад. Кёнигсберг был немецким городом в XVIII веке, расположенным по обоим берегам реки Преголя. На реке есть два острова, соединённые с берегами семью мостами. У жителей города есть традиция: они всегда пытаются найти способ пересечь каждый мост ровно один раз. Очевидно, что это сложная задача, если мы ничего не знаем о топологии. Леонард Эйлер, швейцарский математик, услышал об этой задаче. В конце концов, он предложил решение, которое успешно доказало, что способа пересечь каждый мост только по одному мосту не существует. Как Эйлер решает эту задачу? На карте мы видим четыре области, соединенные мостами, которые находятся на северном берегу реки, на южном берегу реки и на двух островах. Для простоты Эйлер преобразовал карту в граф. Этот граф состоит из точек, которые также называются вершинами, и линий, которые также называются ребрами. Таким образом, четыре области A, B, C и D представлены как вершины, а 7 мостов упрощенно представлены как ребра. Итак, теперь возникает вопрос: можете ли вы нарисовать каждую линию только один раз, чтобы создать граф, не отрывая ручки от бумаги? Конечно, вы можете начать и закончить в любой точке, но вам нужно быть достаточно умным, чтобы знать, с какой точки начать и в какой закончить. Если вершина имеет нечетное количество соединенных с ней ребер, она будет называться нечетной вершиной. И наоборот, если вершина имеет четное количество соединенных с ней ребер, она будет называться четной вершиной. Из этого графа мы видим, что все вершины A, B, C и D являются нечетными вершинами, потому что все они имеют нечетное количество ребер, соединенных с ними. После нескольких дней исследований Эйлер пришел к следующим выводам. Для графа, который может быть завершен, если каждое ребро нарисовать только один раз и не отрывать ручку от бумаги, он должен удовлетворять одному из следующих условий. Он должен иметь ноль нечетных вершин или 2 нечетные вершины. Если граф имеет ноль нечетных вершин, мы можем использовать любую вершину в качестве начальной точки, и эта точка будет также конечной точкой. Путь, который использует каждое ребро графа ровно один раз, также называется эйлеровым путем. Давайте проверим этот пример, чтобы увидеть, может ли он образовать эйлеров путь. В этом графе нет нечетных вершин, мы можем начать с любой точки, и в конечном итоге он вернется в эту точку, чтобы завершить граф. С другой стороны, если граф имеет две нечетные вершины, для успешного завершения эйлерова пути одну вершину можно использовать как начальную точку, а другую — как конечную. Давайте рассмотрим этот пример. В этом графе две нечетные точки. Мы можем использовать точку один как начальную точку, а конечной точкой будет точка два. В любых других случаях нет способа завершить граф, не отрывая ручку от бумаги. Давайте вернемся к задаче о Кенигсбергском мосте и посмотрим, сможем ли мы ее решить. Из упрощенного графа мы видим, что в графе четыре нечетные вершины. Таким образом, нет способа пройти по каждому мосту только один раз. Прежде чем мы закончим сегодняшнюю тему, вы можете проверить свои знания, выбрав те, которые могут генерировать эйлеров путь.