Многие свойства фигур, которые изучаются в геометрии, зависят от их параметров: величин углов, расстояний, перпендикулярности прямых, площади фигур, объема тел и так далее. Однако теория графов и топология помогли выявить геометрические закономерности, которые не зависят ни от параметров геометрических фигур, ни от их формы. В этой короткой главе мы расскажем об известной формуле Эйлера и обнаружим множество ее удивительных следствий, которые проявляются в многогранниках и мозаиках.

В формуле Декарта 1640 года и формуле Эйлера 1752 года фигурируют только грани, ребра и вершины, поэтому эти формулы применимы к множеству различных фигур и по-прежнему выполняются даже после определенных преобразований.

Эти формулы дали начало новому разделу математики — топологии, которая бурно развивалась в XIX веке. Август Фердинанд Мёбиус, Бернхард Риман, Анри Пуанкаре, Ян Брауэр, Соломон Лефшец и многие другие математики, которые работали в различных областях, нашли в этой «новой геометрии» фундаментальную основу для изучения кривых, поверхностей, пространств, функций. Топология помогла определить свойства, которые нельзя было формализовать в рамках традиционной геометрии.

Август Фердинанд Мёбиус — один из математиков XIX века, интересовавшихся топологией.

Если говорить кратко, то топология свободна от жестких структур евклидовой и проективной геометрии. С помощью «непрерывных преобразований» стало возможным моделировать новые фигуры и определять новые категории преобразований. Представим себе треугольник, нарисованный на поверхности шара. При сжатии шара (таком, что шар не ломается) треугольник будет принимать различную форму. Будут изменяться углы и длины сторон, но «сущность» треугольника будет оставаться неизменной: это по-прежнему будет фигура, определяемая тремя точками и тремя отрезками, соединяющими эти точки. Чтобы начать мыслить с топологической точки зрения, нужно представить, что все фигуры сделаны из резины и могут деформироваться. Так, деформацией сферы невозможно получить бублик, но зато бублик будет эквивалентен… чайной чашке.

Удивительная формула Эйлера

Рассмотрим выпуклый п-угольник с вершинами V, V 2 ,..., V n и ребрами V 1 V 2 ,..., V 2 V 3 ,...,V n-1 V n , V n V 1 .

Вне зависимости от длин сторон, величин углов, кривизны ребер и прочих параметров, число ребер будет всегда равно числу вершин многоугольника. Это соотношение столь тривиально, что на него можно даже не обратить внимание. Если сохранить число вершин неизменным и заменить одно из прямых ребер любой простой кривой, это соотношение не изменится.

Перейдем в трехмерное пространство и рассмотрим произвольный выпуклый многогранник, который имеет V вершин, А ребер и С граней. Если посмотреть на этот многогранник изнутри и спроецировать его на большую сферу, внутри которой он находится, то на эту сферу окажутся нанесены линии и соответствующие вершины так, что значения V, А и С останутся неизменными.

Многограннику также можно поставить в соответствие плоский граф, который будет иметь то же число ребер А, то же число вершин V и то же число граней С.

Можно заметить, что при С = 2 получится единственный многоугольник и V = А, либо, что аналогично, С + V = А + 2. Если при С — n число вершин равно V, число ребер — А n , и мы предположим (по индукции), что n + V n = А n + 2, то при С = n + 1 нужно заострить внимание на грани под номером n + 1. Когда число граней станет равным n + 1, к графу с n гранями, V n вершинами и А n ребрами добавится некоторое число вершин К и К + 1 ребро. Следовательно,

C + V n+1 = n + 1 + Vn + K = (n + V n ) + (K + 1) = (A n + 2) + (K + 1) = (A n + K + 1) + 2 = A n+1 + 2.

Так доказывается знаменитая формула Эйлера, которая звучит следующим образом: в любом выпуклом многограннике выполняется соотношение

С + V = A + 2.

Этот результат может показаться тривиальным, но если немного подумать, то мы увидим, что это соотношение поистине удивительно: оно выполняется для любого выпуклого многогранника независимо от формы его граней, углов на гранях и углов между гранями, от длин ребер и других параметров. Формула, которая выполняется для бесконечно большого числа разнообразных фигур, не может не привлекать внимание. Здесь что-то не так. Практически не существует формул, которые справедливы для столь непохожих фигур.

* * *

РАЗУМЕЕТСЯ,  А = С + V — 2. МОЖНО ЛИ ВЫБРАТЬ  С И  V ПРОИЗВОЛЬНО?

В выпуклом многограннике С +  V  = А + 2, следовательно,

А = C + V — 2. (1)

Какие значения могут принимать С и V ? Существуют ли какие-то ограничения? Может ли быть так, что С  = 1000, а  V  = 2? Рассмотрим, каковы же ограничения на  С и  V .

Очевидно, что  V > 4, так как многогранника, у которого меньше четырех вершин, не существует. В каждой вершине сходятся минимум три ребра, следовательно, 3 V =< 2 А , так как каждое ребро связывает две вершины. Следовательно, 3 V =< 2 С + 2 V — 4, откуда следует

4 =< V =< 2 С — 4. (2)

Также С > 4, так как чтобы ограничить часть пространства, требуется минимум четыре грани. Каждая грань должна иметь минимум три ребра, то есть 3 С =< 2 А  = 2 С + 2 V — 4, откуда

4 =< С =< 2V — 4. (3)

Отношения (1), (2) и (3) соответствуют выпуклым многогранникам в пространстве. Простейшие примеры многогранников, у которых число граней С >= 4, — это пирамиды и бипирамиды. Многоугольник, число ребер которого равно 2 К , и точка вне его образуют пирамиду, где С  = 2 К + 1. Для бипирамиды, которая получается, если совместить две такие пирамиды основаниями, С = 4 К .

* * *

С помощью формулы Эйлера для выпуклых многогранников можно вычислить так называемую характеристику Эйлера — Пуанкаре:

Для сферы  = 2. Если мы рассмотрим тор (поверхность вращения, получаемая вращением окружности вокруг оси, лежащей вне этой окружности), то получим  = 0. Следовательно, в тороидальных многогранниках 0 = С + V — А. Родом поверхности

называется число отверстий в ней. Для сферы g = 0, следовательно, в тороидальных многогранниках g = 1. Итак,  и g являются характеристиками поверхности, то есть число 2 в формуле С + V = А + 2 указывает на сферическую природу выпуклых многогранников. Для невыпуклых многогранников формула Эйлера не выполняется. В следующих разделах, где рассматриваются только выпуклые многогранники, мы подробно расскажем о следствиях формулы С + V = А + 2.

Формула  Эйлера для граней и вершин

Теперь мы знаем ограничения на число граней С и число вершин V выпуклого многогранника. Число ребер А полностью зависит от С и V. Попробуем исключить А из формулы Эйлера.

Чтобы полностью исключить А, нужно «более явно» выразить формулу Эйлера через С и V, уточнив, что скрывается за этими числами.

В выпуклом многограннике Р с числом граней С и числом вершин V обозначим за С n число граней, имеющих n ребер, V n — число вершин, в которых сходятся n ребер. Можно записать следующую сумму ряда (конечного!):

С = С 3 + С 4 + С5   + С 6   + … (1)

Также

V = V 3 + V 4 + V 5   + V 6   + … (2)

Так как одно ребро принадлежит двум граням одновременно, то

3С 3 + 4С 4 + 5С 5 + 6С 6   + … = 2A. (3)

Так как каждое ребро соединяет две вершины, получим

3V 3 + 4V 4 + 5V 3 + 6V 6 + … = 2A. (4)

Используя формулу Эйлера, где обе части умножены на 2, то есть 2С + 2V = 4 + 2A, учитывая (1), (2) и (3), получим:

2С 3 + 2С 4   + 2С 5 + 2С 6  + … + 2V 3   + 2V 4 + 2V 5 + 2V 6 + … = 4 + 3С 3   + 4C 4 + 5C 5 + 6C 6 + …

Иными словами,

2V 3 + 2V 4 + 2V 5 + 2V 6 + … = 4 + C 3 + 2C 4 + 3C5 + 4C 6 + … (5)

Аналогично на основе (1), (2) и (4) получим:

2С 3   + 2С 4 + 2С 5 + 2С 6   + … + 2V 3   + 2V4   + 2V 5  + 2V 6 + … = 4 + 3V 3 + 4V 4   + 5V 5 + 6V6   + …

Иными словами,

2C 3   + 2C 4  + 2C5   + 2C 6 + … = 4 + V 3   + 2V 4  + 3V 5 + 4V 6 + … (6)

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

Если прибавить к (5) выражение (6), умножив обе его части на 2, получим:

2V3   + 2V 4  + 2V 5 + 2V 6   + … + 4С 3 + 4С 4 + 4С 5 + 4С 6 + … = 12 + С 3   + 2С4   + 3С 5 + 4С 6 +… + 2V 3 + 4V 4 + 6V 5 + 8V 6   + …

Упростив это выражение, получим удивительный результат:

3C 3   + 2C 4  + C 5 = 12 + 2V 4 + 4V 5   + … + C 7 + 2С 8 + … (*)

В этом выражении не фигурирует число ребер, а также отсутствуют шестиугольные грани и вершины, в которых сходятся три ребра. Запомните выражение (*): оно поможет нам совершить много удивительных открытий. Например, вспомним, какую форму имеет футбольный мяч. Это многогранник, в котором сочетаются пятиугольные и шестиугольные грани, а в каждой вершине сходятся три ребра.

Существуют ли другие многогранники, где вершины и грани обладают теми же особенностями? Заметим, что С 3 = С 4 = С n = 0 при n >= 7, V 4   = V n   = 0 при n >= 5, следовательно, согласно (*) должно выполняться равенство С 5 = 12, но С6 остается неопределенным. Б. Грюнбаум и Т. С. Моцкин доказали, что С 6   может принимать любое значение, отличное от 1. Любопытно, что пятиугольных граней именно 12.

В многограннике, образованном четырехугольниками и шестиугольниками, согласно (*) 2С 4 = 12 + 2V 4   + 4V 5 + …, то есть минимум шесть его граней будут четырехугольниками. Если вершины будут иметь степень 3, то таких граней будет ровно 6. Если гранями многогранника являются треугольники и шестиугольники, то 3С 3 = 12 + 2V 4 + 4V 5 + … и как минимум четыре грани будут иметь форму треугольника. Если вершины будут иметь степень 3, то треугольных граней будет ровно четыре.

Всегда существует треугольная, четырехугольная или пятиугольная грань

Попробуйте представить себе выпуклый многогранник, у которого нет ни одной грани в форме треугольника, четырехугольника или пятиугольника. Очевидно, что такого выпуклого многогранника не существует.

Вспомним формулу (*) из прошлого раздела:

3C 3 + 2C 4 + C 5 = 12 + 2V 4   + 4V 5 + … + С 7 + 2С 8 + … (*)

Заметим, что выражение в правой части больше или равно 12, то есть всегда выполняется соотношение

3С 3 + 2С 4 + С 5 >= 12.

Кроме того, С 3 , С 4 и С 5 не могут быть равны нулю одновременно. Можно сформулировать следующую теорему:

«В любом выпуклом многограннике всегда существует как минимум одна грань в форме треугольника, четырехугольника или пятиугольника».

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

«Единственными правильными многогранниками являются тетраэдр, октаэдр, икосаэдр, куб и додекаэдр».

* * *

ГРАФЫ, СООТВЕТСТВУЮЩИЕ ПРАВИЛЬНЫМ МНОГОГРАННИКАМ

Пять правильных многогранников необязательно изображать в перспективе — можно построить соответствующие им плоские графы. Значения V , А и С для следующих фигур представлены в таблице ниже.

Заметим, что в полученной нами теореме общее соотношение Эйлера сочетается с характеристиками многоугольников, ограничивающих часть пространства, образующего многогранник.

* * *

Исходя из полученного результата (всегда будет существовать грань в форме треугольника, четырехугольника или пятиугольника) и из определения правильного многогранника получим, что единственно возможные правильные многогранники будут полностью образованы либо равносторонними треугольниками, либо квадратами, либо правильными пятиугольниками.

Если все грани многогранника — равносторонние треугольники (их углы равны 60°), формула (*) сводится к 3С 3   = 12 + 2V4   + 4V 5 .  В тетраэдре С 3 = 4 (и, разумеется, V3   = 4, V 4   = V 5   = 0). Для октаэдра V 4 = 6, V 3 = V 5 = 0 и С 3 = 8. В икосаэдре С 3 = 20 и V 5 = 12.

Если все грани многогранника — квадраты, то в его вершинах могут сходиться только три ребра, поэтому V 4  = V 5  = 0 и по формуле (*) 2С 4   = 12, то есть С 4   = 6. Таким образом, этот многогранник — куб.

Если все грани многогранника — правильные пятиугольники, то степень его вершин может равняться только 3. По формуле (*) С 5 = 12 — это додекаэдр.

* * *

ТОЧНЫЙ ПОДСЧЕТ

Пусть Р — выпуклый многогранник с r ( Р ) гранями. Рассмотрим два его параметра:

r ( Р ) — количество натуральных чисел i , таких что в  Р существует грань с i ребрами;

К ( Р ) — число сторон грани Р  с наибольшим числом вершин или ребер.

Так, в кубе Р r ( Р ) = 1, К ( Р ) = 4. Для пирамиды Р , в основании которой лежит пятиугольник, r ( Р ) = 2, К ( Р ) = 5.

Если многоугольник Р имеет грань, число сторон которой равно К ( Р ), так как каждая из этих сторон является ребром другой грани, то общее число граней будет равно как минимум К ( Р ) + 1, то есть

С ( Р ) >= К ( Р ) + 1.

Так как r ( Р ) не может быть больше, чем число элементов множества {3, 4, 5,  К ( Р )}, то

r ( Р ) = < К ( Р ) — 2.

На основании вышеприведенных неравенств для  С ( Р ) и r ( Р ) имеем:

С ( Р ) — r ( Р ) >= К ( Р ) + 1 — ( К (Р) — 2) = 3.

Если бы все грани многогранника были бы различны, то выполнялось бы равенство С ( Р ) = r ( Р ) + 3, что невозможно.

* * *

Все стороны различаются между собой? Это невозможно!

Если вы не привыкли следовать правилам, то возможно, что вы задавались вопросом, существуют ли фигуры без повторяющихся элементов. Например, существует ли многогранник, все стороны которого являются различными многоугольниками: один треугольник, один четырехугольник, один пятиугольник и так далее. Это был бы образцовый многогранник — он мог бы поворачиваться разными сторонами и демонстрировать разные многоугольники. Живительно, но подобный многоугольник не может существовать. И этому есть очень красивое доказательство, в котором используются методы комбинаторики.

Представим на мгновение все возможные многогранники — правильные или неправильные. Если мы нарисуем все эти многогранники, то заметим, что всегда существует как минимум несколько граней, которые являются выпуклыми многоугольниками с одинаковым числом сторон. Чтобы ограничить многоугольниками какую-то область пространства, необходимо чтобы как минимум несколько из них повторялись.

Графы и мозаики

Рассмотрим три разных мозаики, которые представлены на рисунке. Все они, несомненно, знакомы вам, так как часто встречаются в повседневной жизни.

Это четырехугольная, треугольная и шестиугольная мозаики соответственно. Каждая из них представляет собой геометрический граф (определение геометрического графа приводилось выше). Число граней в этих графах может увеличиваться бесконечно: любым из этих графов можно заполнить всю плоскость. Заметим, что при увеличении мозаики для вершин, находящихся внутри, число ребер остается неизменным, и каждая грань ограничивается одним и тем же числом ребер за исключением бесконечно удаленных граней. Если на каждом шаге увеличения мозаики мы будем подсчитывать число вершин V и число вершин V c , расположенных на краю (во внешнем цикле графа), то увидим, что с ростом V отношение V c /V стремится к нулю.

Это справедливо для всех трех рассмотренных типов мозаики. Далее мы продемонстрируем удивительный результат, основанный на следующем определении.

Правильная мозаика — это геометрический граф, который может покрыть плоскость; при этом число ребер а, сходящихся в каждой вершине, и число ребер Ь >= 3 каждой грани являются постоянными (за исключением внешних граней), причем V c /V стремится к нулю.

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

Пусть дана правильная мозаика М, которая имеет V вершин, А ребер и V c граничных вершин. Тогда 2А < aV, так как aV — это общее число ребер, получаемое, если поставить в соответствие каждой вершине (включая граничные) а ребер.

Если же мы не будем учитывать ребра, которые выходят из граничных вершин, получим аV — aV c < 2А.

Объединив эти два неравенства, имеем aV — aV c < 2А < aV.

Разделим все части неравенства на

Перейдем к пределу. При V, стремящемся к бесконечности, V c /V стремится к нулю:

Подсчитаем число граней С мозаики М. С — 1 грань будет иметь Ь ребер, бесконечно удаленная грань будет иметь V c ребер. Следовательно,

(C — 1)b + V c = 2А.

Разделив на bV, получим:

Перейдя к пределу при V, стремящемся к бесконечности, с учетом выражения (*) получим:

(**)

Так как мозаика М — это геометрический граф, для нее выполняется формула Эйлера, которую можно записать в следующем виде:

При переходе к пределу имеем:

Иными словами, постоянные а и Ь связывает равенство

2а + 2Ь = ab,

что можно записать в таком виде:

(а — 2)(Ь — 2) = 4.

Все возможные натуральные решения этого уравнения представлены в таблице:

Интересно, что это доказательство относится исключительно к теории графов и не зависит от каких-либо геометрических свойств (расстояний, углов, параллельности сторон) фигур, образующих мозаику. Например, следующие мозаики относятся к тем же трем типам, хотя очевидно состоят из других фигур. Единственная разница заключается в изоморфизме соответствующих им графов.

* * *

ФОРМУЛА НА МАРКАХ

На этой марке, выпущенной в ГДР в честь Леонарда Эйлера, изображен икосаэдр и формула  A — C + V  = 2 в немецком варианте. Интересный способ рассказать о формуле всему свету.

* * *

Другие геометрические задачи с графами

Помимо формулы Эйлера и ее удивительных следствий, существует множество других областей геометрии, где теория графов представляет особый интерес. Далее мы приведем несколько примеров.

Гамильтоновы циклы в многогранниках

Мы уже рассказали о том, что Гамильтон впервые представил цепи, которые сегодня носят его имя, в игре, где нужно было обойти по разу все вершины додекаэдра. (Напомним, гамильтоновы цепи — это пути в графе, которые проходят через все его вершины ровно по одному разу.) Именно поэтому позднее были предприняты попытки найти гамильтоновы цепи во всех возможных многогранниках либо показать, что они не существуют. На следующих рисунках представлены так называемый граф Гершеля и граф Петерсена — два примера графов, в которых не существует гамильтоновых цепей. Попробуйте убедиться в этом самостоятельно, проведя карандашом линию, проходящую через все вершины этих графов ровно один раз.

Перейдем в трехмерное пространство. Следуя по пути Гарольда Коксетера, попробуем отыскать гамильтоновы цепи в других многогранниках. Коксетер весьма хитроумным способом решил эту задачу для ромбододекаэдра.

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

Этот любопытный многогранник, представленный на рисунке, в соответствии с названием, имеет 12 равных граней, которые являются параллелограммами, и обладает интересным свойством: в восьми его вершинах сходится по три ребра (такие вершины обозначены кругами белого цвета), в оставшихся шести вершинах сходится по четыре ребра (такие вершины обозначены кругами черного цвета). Заметьте, что вершины, выделенные белым цветом, являются вершинами воображаемого куба. Следовательно, ромбододекаэдр можно считать кубом, дополненным шестью пирамидами, в основаниях которых находятся квадраты. Его объем равен удвоенному объему вписанного куба. Ромбододекаэдрами, так же как и кубами, можно заполнить пространство — получится мозаика в трехмерном пространстве.

Существует ли гамильтонова цепь в ромбододекаэдре? Коксетер отвечает на этот вопрос решительным «нет», приводя гениальное доказательство: если бы в ромбододекаэдре существовала гамильтонова цепь, которая бы начиналась и заканчивалась в одной из его вершин, то она проходила бы через 14 вершин по одному разу, причем каждый раз цвет вершин чередовался (с черного на белый или с белого на черный). Такое чередование цветов невозможно, так как в черный цвет окрашено шесть вершин, а в белый — восемь.

* * *

ГАРОЛЬД КОКСЕТЕР (1907–2003)

Гарольд Скотт Макдональд Коксетер родился в Лондоне, изучал математику в Тринити-колледже Кембриджа, но вся его научная карьера прошла в Канаде, в Торонтском университете, где он проработал 60 лет. Его считают одним из величайших геометров XX века, он является автором 12 важных трудов и множества работ, выполненных в соавторстве с другими блестящими геометрами. Он внес неизмеримый вклад в изучение многогранников, в частности многогранников, расположенных в пространстве, имеющем более трех измерений. Коксетер дружил со знаменитым голландским художником М. Эшером, который отразил в своих картинах множество свойств, открытых Коксетером.

* * *

Графы на неплоских поверхностях

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

Анализ графов на различных поверхностях помог определить множество топологических свойств, которые являются инвариантными относительно непрерывных деформаций и лежат в основе классификации кривых и поверхностей. Представим надутый шарик, на поверхности которого фломастером нарисован граф. Если мы будем сминать шарик (но так, чтобы он не лопнул), то заметим, что свойства графа будут оставаться неизменными (число вершин, ребер; число ребер, инцидентных каждой вершине, и другие свойства).

Еще один любопытный пример — граф, построенный на ленте Мёбиуса. Если даны четыре точки на плоскости и мы хотим построить плоский граф, соединяющий каждую точку с остальными тремя, у нас не возникнет затруднений при решении этой задачи. Для этого нужно расположить четыре точки в вершинах четырехугольника, соединить две противоположные точки диагональю, остальные две — линией, проходящей вне четырехугольника. Однако соединить каждую из пяти точек с остальными четырьмя уже не получится, так как появятся нежелательные пересечения ребер (напомним, граф К 5   не является плоским).

Чтобы построить модель ленты Мёбиуса, нужно взять вытянутую прямоугольную полоску бумаги и склеить ее края, предварительно повернув один из них. Если не поворачивать один из краев перед склеиванием, получится обычный цилиндр. Благодаря своей особой форме лента Мёбиуса обладает интересным свойством: она имеет только одну сторону. Цилиндр делит пространство на две части, внутреннюю и внешнюю, но с лентой Мёбиуса этого не происходит: у нее всего одна сторона.

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

Мигель де Гузман всегда считал, что игры и головоломки составляют основу математики.

Обозначим пять точек ABCDE на ленте Мёбиуса так, чтобы получился четырехугольник ABCD, а точка Е располагалась в его центре. Таким образом, ее сразу можно соединить с четырьмя другими точками. На ленте (у которой всего одна сторона!) можно провести линию из точки В в точку D и из точки А в точку С, как показано на рисунке выше. Все пять точек окажутся соединены между собой согласно условию задачи.

Конечные геометрии

Представьте себе плантацию, где в несколько рядов высажены деревья или другие растения. Очевидно, что их можно представить в виде графа, имеющего множество изолированных вершин, не соединенных ребрами. Предположим, что мы хотим составить схему полетов небольшого самолета, который будет опрыскивать посадки, или же возможный маршрут сбора плодов. Такой маршрут укажут ребра графа.

Множество задач подстегнули интерес к конечным геометриям — геометрическим системам, имеющим конечное количество точек и линий, которые представляют собой некие совокупности этих точек.

На предыдущем рисунке с помощью графа представлена конечная геометрия, имеющая пять точек 1, 2, 3, 4, 5 и следующие «линии», образованные точками: {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 5}, {3, 4, 5}. Как можно видеть из этого примера, связь между графами и конечными геометриями очевидна.

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

Рассмотрим пример системы аксиом конечной геометрии.

I. Существует пять точек и две линии.

II. Каждая линия содержит минимум две точки.

III. Каждая линия содержит не более трех точек.

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

Чтобы оценить практическое значение этого примера, представьте, что точки — члены дирекции объединения, линии — комитеты, образованные двумя или тремя членами дирекции. Переформулируем вышеприведенные аксиомы в категориях директоров и комитетов.

I. Существует пять человек и два комитета.

II. Каждый комитет содержит минимум двух членов.

III. Каждый комитет содержит не более трех членов.

Очевидно, что этот пример можно усложнить, добавив новые точки и линии.

* * *

КЛАССИФИКАЦИИ И ИЕРАРХИИ

В классической геометрии особое внимание уделяется классификации фигур (например, по количеству сторон в них). Задачи о классификации становятся все более важными в самых разных областях: можно говорить о классификации фигур с помощью компьютерного зрения, классификации генов, симптомов болезней и так далее. Задачи о классификации появляются в сфере информационной безопасности (цифровые отпечатки пальцев, радужной оболочки глаза, распознавание голоса), на производстве, где при контроле качества бракованные детали автоматически определяются и исключаются из производственной цепочки, и в других областях.

Если речь идет о конечных множествах, то отношение всегда задается множеством пар элементов. Отношения можно изображать в виде диаграмм или графов, вершины которых будут соответствовать элементам множества, ребра — отношениям между ними. Отношения, на основе которых можно сформировать классификацию, называются отношениями эквивалентности. Они обладают следующими свойствами:

— рефлексивностью (каждый элемент эквивалентен сам себе);

— симметричностью (если а связано с b , то b связано с а );

— транзитивностью (если а связано с b и b связано с с , то а связано с с ).

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

Еще один тип отношений — это отношения порядка, которые используются для упорядочивания элементов и обладают свойствами рефлексивности, транзитивности и антисимметричности (если а связано с b и b  связано с а , то а  = Ь ). Графы, соответствующие отношениям порядка на конечных множествах, могут быть ориентированными (дуги будут указывать, какой из двух соединенных ими элементов меньше) или неориентированными (в этом случае элементы будут расположены по порядку снизу вверх). Интерес также представляют иерархические процессы, в которых необходимо определять приоритеты и порядок выполнения определенных работ (инвестиции, строительство, предоставление коммунальных услуг и так далее). Во всех этих областях теория графов помогает понять проблему и упростить ее решение.