Том 11. Карты метро и нейронные сети. Теория графов - Клауди Альсина

Еще один любопытный пример — граф, построенный на ленте Мёбиуса. Если даны четыре точки на плоскости и мы хотим построить плоский граф, соединяющий каждую точку с остальными тремя, у нас не возникнет затруднений при решении этой задачи. Для этого нужно расположить четыре точки в вершинах четырехугольника, соединить две противоположные точки диагональю, остальные две — линией, проходящей вне четырехугольника. Однако соединить каждую из пяти точек с остальными четырьмя уже не получится, так как появятся нежелательные пересечения ребер (напомним, граф К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 связано с а, то а = Ь). Графы, соответствующие отношениям порядка на конечных множествах, могут быть ориентированными (дуги будут указывать, какой из двух соединенных ими элементов меньше) или неориентированными (в этом случае элементы будут расположены по порядку снизу вверх). Интерес также представляют иерархические процессы, в которых необходимо определять приоритеты и порядок выполнения определенных работ (инвестиции, строительство, предоставление коммунальных услуг и так далее). Во всех этих областях теория графов помогает понять проблему и упростить ее решение.

Глава 5

Живительные способы применения графов

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

Джон фон Нейман

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

Графы и интернет

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

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

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

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

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