Математик-циклопСтраница 3
Таким образом, заключил Эйлер, какой бы ни была сеть мостов, обойти все мосты, побывав на каждом по одному и только одному разу, можно только в том случае, если все части города соединены с другими четным числом мостов или если ровно две части города соединены с другими частями нечетным числом мостов. В Кенигсберге город подразделяется всего на четыре части, — и все они соединены с другими частями нечетным числом мостов. На схеме Кенигсберга три точки принадлежат трем линиям, а одна — пяти линиям. Тем самым Эйлер не только сумел объяснить, почему все семь кёнигсбергских мостов невозможно обойти, побывав на каждом один и только один раз, но и придумал правило, применимое к любой сети мостов в любом городе мира. Рассуждения Эйлера отличаются замечательной красотой. По-видимому, такого сорта логические задачи Эйлер и любил решать за обедом.
Задача о семи кёнигсбергских мостах принадлежит к числу так называемых задачах о графах в прикладной математике. Именно она побудила Эйлера к рассмотрению более абстрактных графов. В ходе своих исследований Эйлер открыл фундаментальную истину, относящуюся ко всем графам, — так называемую формулу Эйлера для графов, которую ему удалось доказать за несколько логических шагов. Формула Эйлера для графов выражает незыблемое соотношение между тремя элементами любой графа:
V — R + L = 1,
где
V — число вершин (узлов, или пересечений) в графе,
R — число линий (ребер) в графе,
L — число замкнутых областей в графе.
Таким образом, по утверждению Эйлера, если к числу вершин любого графа прибавить число замкнутых областей и вычесть число его ребер — результат всегда окажется равен единице. Например, все графы на рис. 9 удовлетворяют формуле Эйлера.
Вершины = 4
Области = 3
Линии = 6
Вершины = 6
Области = 1
Линии = 6
Вершины = 5
Области = 10
Линии= 6
Рис. 9. Различные графы, удовлетворяющие формуле Эйлера
Рис. 10. Эйлер доказал свою формулу для графов, продемонстрировав, что она выполняется для простейшего графа, а затем показав, что формула остается верной при любых «дополнениях» к единственной вершине
Можно проверить формулу Эйлера на целой серии графов, и всякий раз она оказывается верной; возникает искушение предположить, что формула Эйлера верна для всех графов. И хотя такой проверки было бы достаточно для физической теории, для обоснования математической теории ее совершенно недостаточно. Единственный способ показать, что формула Эйлера остается в силе для любого мыслимого графа, — построить безупречное с точки зрения логики доказательство. Именно так и поступил Эйлер.
Свое доказательство Эйлер начал с простейшего из графов — с графа, состоящего из одной единственной вершины (рис. 10а ). Ясно, что для такого графа формула Эйлера верна: имеется всего одна вершина, линий и областей нет, поэтому
V
+ R — L = 1 + 0–0 = 1
.
Затем Эйлер рассмотрел вопрос о том, что произойдет в том случае, если он что-нибудь добавит к этому простейшему графу. Любое добавление к нему требует добавления линии. Любая линия может соединять существующую вершину либо с самой собой, либо с какой-нибудь новой вершиной.
Во-первых, рассмотрим случай, когда дополнительная линия соединяет существующую вершину с самой собой. Как видно из рис. 10б , при добавлении линии в этом случае добавляется также новая область. Следовательно, формула Эйлера для графов остается в силе, так как добавление одной области (+) компенсируется добавлением одной линии (—). При добавлении новых линий того же типа формула Эйлера для графов также останется в силе, так как каждая новая линия порождает новую область.
Во-вторых, рассмотрим, что произойдет, если дополнительная линия соединит существующую вершину с новой вершиной, как на рис. 10в . И в этом случае формула Эйлера остается в силе, так как новая вершина (+) компенсирует новую линию (—). При добавлении новых линий того же типа формула Эйлера также остается в силе, поскольку каждая дополнительная линия рассматриваемого типа заканчивается в новой вершине.
Вот и все, что требовалось Эйлеру для его доказательства. Он рассуждал так. Формула верна для простейшего из всех графов — одной-единственной вершины. Все остальные графы, сколь бы сложными они ни были, могут быть построены из простейшего путем прибавления линий — по одной линии за один раз. Всякий раз при добавлении к графу новой линии формула остается верной, потому что вместе с линией добавляется либо новая вершина, либо новая область, и тем самым компенсируется добавление линии. Эйлер разработал простую, но мощную стратегию. Он доказал, что его формула верна для простейшего графа, состоящего из одной-единственной вершины, и что любая операция, приводящая к усложнению графа, не нарушает формулу для графов. Следовательно, формула верна для бесконечного множества всех возможных графов.
Другое по теме
Учитель
Этот компонент не является столь универсальным
как задачник, оценка или нейронная сеть, поскольку существует ряд алгоритмов
обучения жестко привязанных к архитектуре нейронной сети. Примерами таких
алгоритмов могут служить обуч ...