Идти напролом – не всегда самый быстрый путь к успеху. Иногда лучше обойти препятствие, чем идти напролом. Так же обстоит дело и в математике. Иная задача кажется трудной, и даже представляя себе, каким должен быть ответ, никак не удается придумать способ решения. В таком случае может помочь какая-то новая точка зрения, свежая идея.

Но где ее взять?

Первопроходцам всегда было трудно. Если на их пути встречалась гора, то они на нее взбирались, если река, то переплывали через нее. Позднее, когда люди прокладывали дороги, они пользовались картами и уже знали, где река, а где гора.

Решая задачу по математике иногда полезно подумать: нет ли в ближайших областях каких-то общих признаков, особенностей, которые могут пригодиться для выбора правильного направления.

Известна одна старая задача, которая в одном из вариантов формулируется так: «Имеется три дома и три колодца. Можно ли проложить дорожки от каждого из трех домов к каждому из трех колодцев так, чтобы они не пересекались?»

Рис. 1.

Взяв карандаш и бумагу, мы убеждаемся, что сделать это так просто не удается. Однако, если мы попытаемся доказать, что решения не существует, то это будет не так-то просто. Может быть, если одну линию заставить описать несколько петель это и удастся? Но все варианты перебрать невозможно.

Это тот случай, когда следует отступить от данной затеи и попробовать применить что-то иное.

Можно представить, что дома – это элементы одного множества, а колодцы – другого, и нам нужно соединить каждый элемент одного множества с элементом другого так, чтобы линии не пересекались. Такими задачами занимается раздел математики под названием «Теория графов».

Граф состоит из двух главных частей: 1) некоторого множества N, элементы которого называются узлами или вершинами и, как правило, на рисунке изображаются в виде точек; 2) некоторого способа установить, когда две вершины соединены одна с другой. Такие соединения называются ребрами и изображаются линиями.

Рис. 2. Рис. 3.

Фигуры на рис. 2 и рис. 3 служат изображениями одного и того же графа (пересечение без кружка на второй фигуре не считается). Каждая фигура имеет четыре вершины, и каждая пара вершин соединена линией.

Нарисовать граф на плоскости так, чтобы его ребра пересекались только в вершинах, не всегда возможно. Графы, для которых это возможно, называются плоскими.

Теперь задачу о домах и колодцах можно сформулировать так: плоский или нет граф, изображенный на рис. 4?

Рис. 4.

Обратимся к формуле Эйлера, которая имеет место для конечных, связных, плоских графов. «Конечный» означает, что число вершин и ребер конечно. Граф, в котором для любых двух вершин найдется соединяющий их маршрут (последовательность ребер), называется связным.

Любой граф такого вида делит плоскость на конечное число областей, которые называются гранями. Например, граф на рис. 2 имеет 3 грани (Г), 4 вершины (В) и 6 ребер (Р). Эйлер (1707-1783) первым доказал, что грани, вершины и ребра таких графов связаны формулой: В – Р+Г=1.

Итак, возвращаемся к задаче. Доказательство ее идет от противного. Предположим, что граф на рис. 4 является плоским. Тогда для него будет справедлива формула Эйлера, т. е. 6 – 9 + Г = 1. Значит, Г = 4.

Теперь выясним все о гранях. Каждая грань плоского графа окружена замкнутой цепью, или циклом, из его ребер. Циклы графа на рис. 4 состоят либо из 4, либо из 6 ребер. Если допустить, что наружная часть графа – это тоже грань, то каждое ребро принадлежит двум граням. В нашей задаче число граней с учетом внешней теперь равно пяти (Г = 5). Далее, так как каждая грань ограничена, по крайней мере, четырьмя ребрами, а ребро, как уже сказано, принадлежит двум граням, то общее число ребер должно быть больше чем (45)10. Но в нашем случае Р = 9. Таким образом, получено противоречие, и данный граф не является плоским. Значит, задача о трех домах и трех колодцах не имеет решения.

При решении этой задачи, как впрочем, и при решении многих других различных головоломок, математических и логических задач, использование теории графов дает отличный результат.

Используемая литература:

1.Концепции современной математики. Я. Стюарт, Минск, 1980г.

2.Графы и их применение, О. Оре, Москва, 1979г.

3.Физико-математический журнал «Квант», А. Савин, №6, 1994г.