Содержание статьи

ТОПОЛОГИЯ, раздел математики, занимающийся изучением свойств фигур (или пространств), которые сохраняются при непрерывных деформациях, таких, например, как растяжение, сжатие или изгибание. Непрерывная деформация – это деформация фигуры, при которой не происходит разрывов (т.е. нарушения целостности фигуры) или склеиваний (т.е. отождествления ее точек). Такие геометрические свойства связаны с положением, а не с формой или величиной фигуры. В отличие от евклидовой и римановой геометрий, геометрии Лобачевского и других геометрий, занимающихся измерением длин и углов, топология имеет неметрический и качественный характер. Раньше она носила названия «анализ ситус» (анализ положения), а также «теория точечных множеств». В научно-популярной литературе топологию часто называют «геометрией на резиновом листе», поскольку ее наглядно можно представлять себе как геометрию фигур, нарисованных на идеально упругих резиновых листах, которые подвергаются растяжению, сжатию или изгибанию. Топология – один из новейших разделов математики.

История.

В 1640 французский философ и математик Р.Декарт (1596–1650) нашел инвариантное соотношение между числом вершин, ребер и граней простых многогранников. Это соотношение Декарт выразил формулой V – E + F = 2, где V – число вершин, E – число ребер и F – число граней. В 1752 швейцарский математик Л.Эйлер (1707–1783) дал строгое доказательство этой формулы. Еще один вклад Эйлера в развитие топологии – это решение знаменитой задачи о кёнигсбергских мостах. Речь шла об острове на реке Прегель в Кёнигсберге (в том месте, где река разделяется на два рукава – Старый и Новый Прегель) и семи мостах, соединяющих остров с берегами. Задача состояла в том, чтобы выяснить, можно ли обойти все семь мостов по непрерывному маршруту, побывав на каждом только один раз и вернувшись в исходную точку. Эйлер заменил участки суши точками, а мосты – линиями. Полученную конфигурацию Эйлер назвал графом, точки – его вершинами, а линии – ребрами. Вершины он разделил на четные и нечетные в зависимости от того, четное или нечетное число ребер выходит из вершины. Эйлер показал, что все ребра графа можно обойти ровна по одному разу по непрерывному замкнутому маршруту, лишь если граф содержит только четные вершины. Так как граф в задаче о кёнигсбергских мостах содержит только нечетные вершины, мосты невозможно обойти по непрерывному маршруту, побывав на каждом ровно по одному разу и вернувшись к началу маршрута.

Предложенное Эйлером решение задачи о кенигсбергских мостах зависит только от взаимного расположения мостов. Оно положило формальное начало топологии как разделу математики. К.Гаусс (1777–1855) создал теорию узлов, которой позднее занимались И.Листинг (1808–1882), П.Тэйт (1831–1901) и Дж.Александер. В 1840 А.Мёбиус (1790–1868) сформулировал так называемую проблему четырех красок, которую впоследствии исследовали О.де Морган (1806–1871) и А.Кэли (1821–1895). Первым систематическим трудом по топологии были Предварительные исследования по топологии Листинга (1874).

Основателями современной топологии являются Г.Кантор (1845–1918), А.Пуанкаре (1854–1912) и Л.Брауэр (1881–1966).

Разделы топологии.

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

Некоторые основные понятия.

Топологическое пространство состоит из множества точек S и набора S подмножеств множества S , удовлетворяющего следующим аксиомам:

(1) все множество S и пустое множество принадлежат набору S;

(2) объединение любой совокупности множеств из S есть множество из S;

(3) пересечение любого конечного числа множеств из S есть множество из S.

Множества, входящие в набор S, называются открытыми множествами , а сам этот набор – топологией в S . См . МНОЖЕСТВ ТЕОРИЯ.

Топологическое преобразование , или гомеоморфизм , одной геометрической фигуры S на другую, S ў, – это отображение (p ® p ў) точек p из S в точки p ў из S ў, удовлетворяющее следующим условиям: 1) устанавливаемое им соответствие между точками из S и S ў взаимно однозначно, т.е. каждой точке p из S соответствует только одна точка p ў из S ў и в каждую точку p ў отображается только одна точка p ; 2) отображение взаимно непрерывно (непрерывно в обе стороны), т.е. если заданы две точки p , q из S и точка p движется так, что расстояние между ней и точкой q стремится к нулю, то расстояние между соответствующими точками p ў, q ў из S ў также стремится к нулю, и наоборот.

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

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

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

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

Максимальное число замкнутых простых непересекающихся кривых, по которым можно разрезать замкнутую поверхность, не разделяя ее на отдельные части, называется родом поверхности. Род – топологический инвариант поверхности. Можно доказать, что род сферы равен нулю, род тора (поверхности «бублика») – единице, род кренделя (тора с двумя дырками) – двум, род поверхности с p дырами равен p . Отсюда следует, что ни поверхность куба, ни сфера не гомеоморфны тору.

Среди топологических инвариантов поверхности можно также отметить число сторон и число краев. Диск имеет 2 стороны, 1 край и род 0. Тор имеет 2 стороны, не имеет краев, а его род равен 1.

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

Важные проблемы и результаты.

Теорема Жордана о замкнутой кривой.

Если на поверхности проведена простая замкнутая кривая, то существует ли какое-либо свойство кривой, которое сохраняется при деформации поверхности? Существование такого свойства вытекает из следующей теоремы: простая замкнутая кривая на плоскости делит плоскость на две области, внутреннюю и внешнюю . Эта кажущаяся тривиальной теорема очевидна для кривых простого вида, например, для окружности; однако для сложных замкнутых ломаных дело обстоит иначе. Теорема была впервые сформулирована и доказана К.Жорданом (1838–1922); однако доказательство Жордана оказалось ошибочным. Удовлетворительное доказательство было предложено О.Вебленом (1880–1960) в 1905.

Теорема Брауэра о неподвижной точке.

Пусть D – замкнутая область, состоящая из окружности и ее внутренности. Теорема Брауэра утверждает, что для любого непрерывного преобразования, переводящего каждую точку области D в точку этой же области, существует некоторая точка, которая остается неподвижной при этом преобразовании. (Преобразование не предполагается взаимно однозначным.) Теорема Брауэра о неподвижной точке представляет особый интерес потому, что она, по-видимому, является, наиболее часто используемой в других разделах математики топологической теоремой.

Проблема четырех красок.

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

Гипотеза о том, что четырех красок достаточно для соответствующей раскраски любой карты, была впервые высказана в 1852. Опыт показал, что четырех красок действительно достаточно, но строгого математического доказательства не удавалось получить на протяжении более ста лет. И только в 1976 К.Аппель и В.Хакен из Иллинойского университета, затратив более 1000 часов компьютерного времени, добились успеха.

Односторонние поверхности.

Простейшей односторонней поверхностью является лист Мёбиуса , названный так в честь А.Мёбиуса, открывшего его необычайные топологические свойства в 1858. Пусть ABCD (рис. 2,а ) – прямоугольная полоска бумаги. Если склеить точку A с точкой B , а точку C с точкой D (рис. 2,б ), то получится кольцо с внутренней поверхностью, наружной поверхностью и двумя краями. Одну сторону кольца (рис. 2,б ) можно окрасить. Окрашенная поверхность будет ограничена краями кольца. Жук может совершить «кругосветное путешествие» по кольцу, оставаясь либо на окрашенной, либо на неокрашенной поверхности. Но если полоску перед склеиванием концов перекрутить на полоборота и склеить точку A с точкой C , а B с D , то получится лист Мёбиуса (рис. 2,в ). У этой фигуры есть только одна поверхность и один край. Любая попытка окрасить только одну сторону листа Мёбиуса обречена на неудачу, так как у листа Мёбиуса всего одна сторона. Жук, ползущий по середине листа Мёбиуса (не пересекая края), вернется в исходную точку в положении «вверх ногами». При разрезании листа Мёбиуса по средней линии он не распадается на две части.

Узлы.

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

Топология компьютерных сетей

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

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

· топология типа звезда;

· топология типа кольцо;

· топология типа общая шина;

· древовидная топология;

· полносвязная сеть.

Рассмотрим данные топологии сетей.

Топология типа звезда . При использовании топологии типа звезда информация между клиентами сети передается через единый центральный узел (Рис. 11). В качестве центрального узла может выступать сервер или специальное устройство – концентратор (Hub).

Рис. 11. Топология типа звезда

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

Преимущества топологии звезда состоят в следующем:

1. Высокое быстродействие сети, так как общая производительность сети зависит только от производительности центрального узла.

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

Однако помимо достоинств у данной топологии есть и недостатки:

1. Низкая надежность, так как надежность всей сети определяется надежностью центрального узла. Если центральный узел (сервер или концентратор) выйдет из строя, то работа всей сети прекратится.

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

3. Отсутствие возможности выбора различных маршрутов для установления связи между абонентами.

Данная топология в настоящее время является самой распространенной.

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

Рис. 12. Топология типа кольцо

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

Преимущества топологии типа кольцо состоят в следующем:

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

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

3. Отсутствие коллизий (см. тему №3, раздел 2) и столкновения данных, так как передачу в каждый момент времени ведет только один компьютер.

К недостаткам данной топологии относятся:

1. Низкая надежность сети, так как отказ любого компьютера влечет за собой отказ всей системы.

2. Для подключения нового клиента необходимо прервать работу в сети.

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

4. Общая производительность сети определяется производи­тельностью самого медленного компьютера .

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

Топология типа общая шина . При шинной топологии все клиенты подключены к общему каналу передачи данных (рис. 13). При этом они могут непосредственно вступать в контакт с любым компьютером, имеющимся в сети.

Рис.13. Топология типа общая шина

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

Преимущества топологии общая шина:

1. Вся информация находится в сети и доступна каждому компьютеру. Т.е. с любого персонального компьютера можно получить доступ к информации, которая храниться на любом другом компьютере.

2. Рабочие станции можно подключать независимо друг от друга. Т.е. при подключении нового абонента нет необходимости останавливать передачу информации в сети.

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

4. Сеть обладает высокой надежностью, т.к. работоспособность сети не зависит от работоспособности отдельных компьютеров.

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

К недостаткам топологии типа общая шина относятся:

1. Низкая скорость передачи данных, так как вся информация циркулирует по одному каналу (шине).

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

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

Древовидная топология . В сетях с древовидной топологией компьютеры непосредственно связаны с центральными узлами сети – серверами (Рис. 14).

Рис.14. Древовидная топология

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

Полносвязная вычислительная сеть . В полносвязной сети каждый компьютер соединен со всеми другими компьютерами отдельными линиями (рис. 15).

Рис.15. Полносвязная вычислительная сеть

Преимущества полносвязной сети:

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

2. Высокое быстродействие, так как информация между компьютерами передается по отдельным линиям.

Недостатки данной топологии:

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

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

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

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

Модели ЛВС

Существует две модели локальных вычислительных сетей:

· одноранговая сеть;

· сеть типа клиент-сервер.

В одноранговой сети все компьютеры равноправны между собой. При этом вся информация в системе распределена между отдельными компьютерами. Любой пользователь может разрешить или запретить доступ к своим данным. В таких сетях на всех компьютерах устанавливаются однотипные операционные системы (ОС), которые предоставляет всем компьютерам в сети потенциально равные возможности.

Достоинстваданной модели:

1. Простота реализации. Для реализации данной сети достаточно наличия в компьютерах сетевых адаптеров и кабеля, которых их соединит.

2. Низкая стоимость создания сети. Так как отсутствуют затраты, связанные с покупкой дорогостоящего сервера, дорогой сетевой операционной системы и т.д.

Недостатки модели:

1. Низкое быстродействие при сетевых запросах. Рабочая станция всегда обрабатывает сетевые запросы медленнее, чем специализированный компьютер – сервер. Помимо этого на рабочей станции всегда выполняются различные задачи (набор текста, создание рисунков, математические расчеты и др.), которые замедляют ответы на сетевые запросы.

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

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

4. Зависимость наличия в системе информации от состояния компьютера. Если какой-то компьютер будет выключен, то информация, хранимая на нем, будет недоступна другим пользователям.

В сети типа клиент-сервер имеется один или несколько главных компьютеров - серверов. В таких системах всей основной информацией управляют серверы.

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

Достоинствами данной модели являются:

1. Высокое быстродействие сети, так как сервер быстро обрабатывает сетевые запросы и не загружен другими задачами.

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

3. Простота управления все сетью. Так как управление сетью заключается в основном в управлении только сервера.

Недостаткимодели:

1. Высокая стоимость реализации, так как требуется покупать дорогостоящий сервер и сетевую операционную систему для сервера.

2. Зависимость быстродействия сети от сервера. Если сервер будет не достаточно мощным, то работа в сети может сильно замедляться.

3. Для правильной работы сети требуется наличие дополнительного обслуживающего персонала, т.е. в организации должна быть введена должность администратор сети.

Топология, самая юная и самая мощная ветвь геометрии, наглядно демонстрирует плодотворное влияние противоречий между интуицией и логикой

Р. Курант

Топология является одним из самых молодых разделов современной геометрии. Чем занимается топология? Так, например, аналитическая геометрия исследует простейшие геометрические объекты (точки, прямые, плоскости и пр.) средствами элементарной алгебры на основе метода координат. Чтобы получить некоторое представление о топологии, рассмотрим ряд простых и занимательных задач, связанных с ее объектами.

У каждого из нас есть интуитивное представление о том, что такое "поверхность". Поверхность листа бумаги, поверхность стен аудитории, поверхность земного шара известны всем. Возьмите бумажную ленту АВСD, разделенную по ширине пополам пунктирной линией и приложите ее концы АВ и СD друг к другу, склейте их так, чтобы точка А совпала с точкой D, а точка B с точкой С. Перед склейкой перекрутите ленту один раз. Получилось знаменитое в математике бумажное кольцо. Его особое название - "Лист Мёбиуса". У ленты, из которой сделан лист Мёбиуса, две стороны. А у него самого, есть только одна сторона! В качестве опыта, демонстрируемого особенности листа Мебиуса, обычно предлагают «опыт с пауком и мухой». Если на внутреннюю сторону обычного кольца посадить паука, а на наружную - муху и разрешить им ползать как угодно, запретив лишь перелезать через края кольца, то паук никогда не сможет добраться до мухи. А если их обоих посадить на лист Мёбиуса, то бедная муха будет съедена, если, конечно, паук ползает быстрее!

Таинственный и знаменитый лист Мебиуса (иногда говорят: "лента Мёбиуса") придумал в 1858 г. немецкий геометр Август Фердинанд Мёбиус (1790-1868), ученик "короля математиков" Гаусса. Мёбиус был первоначально астрономом, как Гаусс и многие другие из тех, кому математика была обязана своим развитием. В те времена занятия математикой не встречали поддержки, а астрономия давала достаточно денег, чтобы не думать о них, и оставляла время для собственных размышлений. И Мёбиус стал одним из крупнейших геометров XIX в. В возрасте 68 лет ему удалось сделать открытие поразительной красоты. Это открытие односторонних поверхностей, одна из которых - лист Мёбиуса.

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

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

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

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

В Кенигсберге есть остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава, через которые перекинуто семь мостов: а, b, с, d, e, f, g. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?

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

Сначала попытайтесь нарисовать одним росчерком, не отрывая пера от бумаги, не делая никаких лишних штрихов и не проводя дважды ни одной линии, каждую из следующих семи фигур, изображенных на рис. 21. Попытки вычерчивания непрерывной линией фигур 1-7 приводят к неодинаковым результатам. Некоторые фигуры удается вычерчивать, с какой бы точки ни начинать вести первую линию. Другие вычерчиваются одним росчерком в тех лишь случаях, когда начинают с определенных точек. Наконец, третьи вовсе не поддаются вычерчиванию одной непрерывной линией. Существуют ли признаки, позволяющие установить заранее, поддается ли данная фигура вырисовыванию одним росчерком, и если поддается, то с какой точки следует начинать черчение?

Теория графов дает на эти вопросы исчерпывающие ответы, и мы сейчас познакомимся с некоторыми положениями этой теории. Условимся называть «четными» те точки фигуры, в которых сходится четное число линий, в отличие от точек «нечетных», в которых встречается нечетное число линий. Можно доказать, что какова бы ни была фигура, нечетных точек в ней либо нет совсем, либо их имеется две, четыре, шесть-вообще четное число. В теории графов доказывается, что если нечетных точек в фигуре нет, то она всегда поддается вырисовыванию одним росчерком, безразлично, с какого места ни начинать черчение. Таковы фигуры 1 и 5 . Если в фигуре имеется только одна пара нечетных точек, то такую фигуру можно нарисовать одним росчерком, начав черчение в одной из нечетных точек (безразлично в какой). Вычерчивание должно оканчиваться во второй нечетной точке. Таковы фигуры 2, 3, 6; в фигуре 6, например, вычерчивание надо начинать либо из точки А, либо из точки В.

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

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

Впервые эта проблема была сформулирована в 1825 году лондонским студентом Гутри, который обнаружил, что для различия графств на карте Англии достаточно четырех красок, и выдвинул гипотезу о том, что четырех красок достаточно для раскраски любой карты. Спустя сорок лет английский математик Хивуд доказал, что любую карту на плоскости можно раскрасить в пять цветов. В дальнейшем проблема четырех красок приобретала все больший и больший интерес. В 1968 году Оре и Стемпл доказали, что любую карту, имеющую не более 40 стран, можно раскрасить в четыре цвета.

В настоящее время проблема четырех красок решена с помощью компьютерной визуализации. Учеными с помощью компьютера было просмотрено около 2000 типов карт и был получен вывод, что не существует среди них карты, для раскраски которой недостаточно четырех красок. Однако, поскольку нельзя признать, что все типы карт были рассмотрены, то полученное решение окончательным не считается и в настоящее время проблема четырех красок остается открытой.

В топологии существуют и свои объекты, и свои свойства, отличающиеся от свойств фигур в евклидовой геометрии.

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

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

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

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

Так, рассмотренные выше фигуры принадлежат одному топологическому типу; отрезок, дуга, незамкнутая ломаная - другому; «восьмерка» не принадлежит ни одному из этих типов. Сфера, куб, выпуклый многогранник образуют свой топологический тип и т. д.

Возьмем лист бумаги. Согните его, как угодно, сделайте из него самолетик, кораблик, сомнем его в комок. Если в результате этих преобразований он нигде не порвался, то во всех этих состояниях все его виды – кораблик, самолетик, комок, эквивалентны друг другу. Более того, если допустить, что лист бумаги обладает особыми свойствами, позволяющими его растягивать как угодно и сжимать до любой степени, то он будет эквивалентен даже кругу. Если же все- таки случайно он порвался и образовалось отверстие, то это будет другая поверхность, называемая кольцом. Говорят, что она ограничена двумя окружностями

К особым топологическим свойствам относятся: связность, компактность, линейная связность.

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

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

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

Компактные объекты – это объекты, которые одновременно и ограничены (например, вокруг них можно описать окружность или сферу), и замкнуты (то есть граничные точки принадлежат объекту).

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

Следующий объект – это уже известный лист Мебиуса.

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

Лист Мёбиуса был эмблемой известной серии научно-популярных книг «Библиотечка „Квант“». Он также постоянно встречается в научной фантастике, например в рассказе Артура Кларка «Стена Темноты». В рассказе «Лист Мёбиуса» автора А. Дж. Дейча, бостонское метро строит новую линию, маршрут которой становится настолько запутанным, что превращается в ленту Мёбиуса, после чего на этой линии начинают исчезать поезда. По мотивам рассказа был снят фантастический фильм «Мёбиус» режиссёра Густаво Москера. Также идея ленты Мёбиуса используется в рассказе М. Клифтона «На ленте Мёбиуса».

С лентой Мёбиуса сравнивается течение романа современного русского писателя Алексея А. Шепелёва «Echo» (СПб.: Амфора, 2003). Из аннотации к книге: «„Echo“ - литературная аналогия кольца Мёбиуса: две сюжетные линии - „мальчиков“ и „девочек“ - переплетаются, перетекают друг в друга, но не пересекаются».

Еще один объект топологии - бутылка Клейна.

Феликс Клейн - это математик, который первым исследовал эту поверхность, а вот почему "бутылка"? Ведь на бутылку это мало похоже. Вероятно, после какой-то деформации сходство с бутылкой становится ближе?

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

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

Известный специалист по алгебраической геометрии Д. Пидо написал книгу под названием "Прекрасное искусство математики". Это великолепная книга, однако профессор Пидо, следуя установившейся традиции, допускает там неверное утверждение. Он пишет, что изготовить бутылку Клейна под силу лишь искусному стеклодуву, сделать же бутылку Клейна "из бумаги совсем невозможно". Действительно, в то время, когда профессор Пидо писал свою книгу, никто даже не пытался склеить бумажную модель бутылки Клейна. Но так продолжалось лишь до тех пор, пока за дело не взялся Стифен Барр, писатель-фантаст, а на досуге - большой любитель занимательной математики.

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

Бутылка Клейна является замкнутой односторонней поверхностью, если налить в такую бутылку воду, то вылить ее обратно уже будет совершенно невозможно.

Итак, топология – это особый раздел геометрии, в котором нет места понятиям расстояние, форма, угол. Линия не бывает здесь прямой или кривой - это просто линия. Поверхность не может быть вогнутой или выпуклой, или плоской - это бессмысленные для топологии слова. Но, например, отрезок и замкнутую линию - это топологически разные объекты. Объекты топологии бывают односторонние и двусторонние. Например, куб - двусторонняя поверхность, лист Мебиуса –односторонняя.

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

Существуют и технические применения ленты Мёбиуса. Полоса ленточного конвейера выполняется в виде ленты Мёбиуса, что позволяет ему работать дольше, потому что вся поверхность ленты изнашивается равномерно. Также в системах записи на непрерывную плёнку применяются ленты Мёбиуса (чтобы удвоить время записи). Во многих матричных принтерах красящая лента также имеет вид листа Мёбиуса для увеличения её ресурса.

Линии на карте-схеме Московского метрополитена сильно искажены по сравнению с реальными путями. Тем не менее, каждой точке путей
соответствует точка на схеме, и любые две точки, соединенные
на карте, соединены в действительности: схема и лондонская «подземка» топологически эквивалентны.

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

Доступно с лицензией Standard или Advanced.

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

Зачем нужна топология?

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

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

Топология также используется для моделирования интеграции геометрии между несколькими различными классами пространственных объектов. Иногда это называют вертикальной интеграцией классов пространственных объектов.

Каким образом объекты в топологии используют общую геометрию

Пространственные объекты могут совместно использовать геометрию внутри топологии. Ниже приведены примеры смежных пространственных объектов:

• Площадные объекты могут использовать общие границы (полигональная топология).
• Линейные объекты могут использовать общие конечные точки (топология ребер и узлов).

Кроме того, общая геометрия может использоваться между классами пространственных объектов с помощью топологии базы геоданных. Например:

• Линейные пространственные объекты могут иметь общие сегменты.
• Площадные объекты могут совмещаться с другими площадными объектами. Например, земельные участки могут могут складываться в кварталы.
• Линейные пространственные объекты могут иметь вершины, совпадающие с точечными объектами (узловая топология).
• Точечные объекты могут совмещаться с линейными (точечные события).

Примечание:

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

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

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

Два вида: объекты и элементы топологии

Слой полигонов можно описать и использовать:

• Как наборы географических пространственных объектов (точек, линий и полигонов)
• Как граф топологических элементов (узлов, ребер, граней и их взаимоотношений).

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

Эволюция покрытий в топологию базы геоданных

Примечание:

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

Происхождение терминов «Дуга-узел» и «Геореляционный»

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

Модель данных покрытия содержит следующие элементы.

Границы пространственных объектов и точки в покрытии хранились в нескольких основных файлах, управляемых ArcInfo Workstation . Файл «ARC» содержал линейную или полигональную геометрию границ в виде топологических ребер, которые назывались «дугами». Файл «LAB» содержал точечные объекты, которые использовались как отправные точки для построения полигонов или как отдельные точечные объекты, например скважины. Другие файлы использовались для определения и сохранения топологических отношений между ребрами полигонов.

Например, файл «PAL» («Polygon-arc list») содержал порядок и направление дуг каждого полигона. С помощью программной логики в ArcInfo Workstation осуществлялась сборка координат каждого полигона для целей отображения, анализа и запроса данных. Упорядоченный список, содержащийся в файле PAL, использовался для поиска и сборки координат ребер, которые хранились в файле ARC. Сборка полигонов происходила по мере необходимости во время работы.

Модель покрытий имела несколько преимуществ:

• Она использовала простую структуру для хранения топологии.
• Она позволяла один раз оцифровывать и сохранять дуги, которые затем использовались несколькими пространственными объектами.
• Она могла отображать полигоны очень большого размера (с тысячами координатных точек), т.к. они были представлены в виде набора ребер (т.е. «дуг»)
• Структура хранения топологии покрытия была интуитивно понятна. Ее физические топологические файлы были легко понятны пользователям ArcInfo Workstation .

Прежние версии:

Интересный исторический факт: сочетание Arc с менеджером таблиц Info породило название продукта ArcInfo Workstation , из которого развились все последующие Arc-продукты в семействе продуктов Esri – ArcInfo, ArcIMS, ArcGIS и т.д.

Покрытия также имели несколько недостатков:

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

Шейп-файлы и хранение простой геометрии

В начале 1980-х, покрытия рассматривались как существенное усовершенствование устаревших полигональных и линейных систем, в которых полигоны хранились в виде замкнутых петель. В этих устаревших системах, все координаты пространственных объектов хранились вместе с геометрией этих объектов. До появления покрытий и ArcInfo Workstation , использовались эти простые полигональные и линейные структуры. Эта структура данных была проста, но имела существенный недостаток «дважды оцифрованных границ». Т.е. в геометрии каждого полигона, имеющего общие грани, хранились две копии координат для соседних участков. Основной недостаток состоял в том, что программное обеспечение ГИС того времени не могло управлять целостностью общих ребер. Кроме того, стоимость хранения информации была очень велика, экономить приходилось каждый байт. В начале 80-х годов жесткий диск емкостью 300 МБ был размером со стиральную машину и стоил 30 000 долларов. Хранение двух и более наборов координат было дорогостоящим, а вычисления занимали немало машинного времени. Таким образом, использование топологии покрытия имело реальные преимущества.

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

Пользователи хотели повышения быстродействия при работе с данными (например, не ждать вычисления геометрии полигона, который потребовался в данный момент, а просто получить координаты полигонов как можно быстрее). Доступность полной геометрии пространственных объектов оказалась более эффективной. Тысячи пользователей ГИС создали огромное количество доступных наборов данных.

Примерно в это же время компания Esri разработала и опубликовала формат шейп-файла. Шейп-файлы использовали очень простую модель хранения координат пространственных объектов. Каждый шейп-файл представлял один класс пространственных объектов (точечных, линейных или полигональных) и использовал простую модель хранения координат пространственных объектов. Шейп-файлы легко создавались из покрытий и форматов других ГИС. Они быстро стали форматом «де-факто», широко распространились и используются по сей день.

Несколько лет спустя, ArcSDE предложил простую модель хранения данных в таблицах реляционных баз данных. Таблица пространственных объектов может хранить один объект в виде строки, вместе с информацией о его геометрии, а также атрибуты.

Пример такой таблицы, содержащей полигоны штатов, показан ниже. Каждая строка представляет один штат. Столбец shape содержит полигональную геометрию каждого штата.

Эта простая модель пространственных объектов хорошо подходит для механизма обработки SQL. Благодаря использованию реляционных баз данных, увеличение объема данных и количества пользователей не приводило к снижению производительности. Мы начали использовать РСУБД для управления данными ГИС.

Шейп-файлы получили повсеместное распространение и, благодаря ArcSDE, этот механизм хранения простой геометрии стал основной моделью хранения пространственных объектов в РСУБД. (Стремясь обеспечить совместимость данных, компания Esri сыграла ведущую роль в создании спецификации простой геометрии OGC и ISO).

Хранение простых объектов имело явные преимущества:

• Полная геометрия каждого пространственного объекта содержится в одной строке. Сборка не требуется.
• Структура данных (физическая схема) очень проста, кроме того, она не только быстрая, но и масштабируемая.
• Легкость написания интерфейса.
• Легкость взаимодействия. Позволяет без труда создавать конвертеры для переноса данных в формат простой геометрии из большого количества других форматов, и наоборот. Шейп-файлы широко применялись как формат хранения данных, а также как обменный формат.

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

Пользователи стали применять такой гибридный подход для редактирования и работы с данными. Например, пользователи могли редактировать данные в покрытиях, файлах САПР или в других форматах. Затем, они могли конвертировать данные в шейп-файлы для картографического использования. Таким образом, несмотря на то, что структура простых объектов стала удобным форматом прямого использования, она не поддерживала топологическое редактирование и управление совместно используемой геометрией. Базы данных прямого пользования могли использовать простую структуру, но для редактирования использовалась иная топологическая форма. Это давало преимущества при работе с данными. Но, при этом данные устаревали, их требовалось обновлять. Эта схема работала, но при этом появлялась задержка обновления информации. Нижняя линия – топология отсутствует.

ГИС требовали механизма хранения пространственных объектов, использующего простую геометрию объектов, и позволяющего использовать топологию вместе с этой структурой данных. Это означало, что пользователи, наконец, смогут совместить преимущества обоих подходов – транзакционной модели данных, которая позволяет выполнять запросы к топологии, совместное редактирование и контроль над целостностью данных, и простого, хорошо масштабируемого механизма хранения данных, основанного на использовании геометрии простых объектов.

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

Рабочая среда топологии в ArcGIS

Фактически, топология предполагает нечто большее, чем только модель хранения данных. Топология включает:

• Полная модель данных (объекты, правила целостности, инструменты редактирования и проверки, топологически-геометрический механизм, позволяющий обрабатывать наборы данных любого размера и сложности, а также набор топологических операторов, способов отображения и инструментов построения запросов).
• Открытый формат хранения использует набор типовых записей для обозначения простых объектов и топологический интерфейс для построения запросов, поиска элементов топологии и обработки пространственных отношений между ними (т.е., поиск смежных областей и их общих ребер, перемещение вдоль соединенных линий).
• Возможность взаимодействия пространственных объектов (точки, линии и полигоны), топологических элементов (узлы, ребра, грани) и их отношений.
• Механизм, который может поддерживать:
  • Очень большие наборы данных, содержащие миллионы пространственных объектов.
  • Одновременное редактирование и обработку несколькими пользователями.
  • Готовую к использованию, всегда доступную геометрию пространственных объектов.
  • Поддержку топологической целостности и поведения.
  • Быстродействующую систему, масштабируемую в зависимости от числа пользователей и редакторов.
  • Гибкую и простую систему.
  • Систему, использующую преимущества механизма SQL реляционной СУБД и среду транзакций.
  • Систему, поддерживающую многопользовательское редактирование, длинные транзакции, историческое архивирование и репликацию.

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

Это обеспечивает быстрый и масштабируемый поиск топологических элементов (узлов, ребер и граней). Дополнительным преимуществом является работа с механизмом SQL РСУБД и управление транзакциями.

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

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

• Для хранения пространственных объектов используется простая геометрия. Модель хранения является открытой, эффективной, и масштабируется под большие объемы и многочисленных пользователей.
• Модель данных простых объектов является транзакционной и многопользовательской. Предыдущие топологические модели данных не масштабировались и имели серьезные ограничения при многопользовательской работе.
• Топология базы геоданных полностью поддерживает все возможности длинных транзакций и версионных данных базы геоданных. Топологию базы геоданных не нужно разбивать для многопользовательской работы, пользователи могут одновременно редактировать базу топологических данных – даже свои собственные версии одних и тех же пространственных объектов.
• Классы пространственных объектов могут содержать очень большое количество объектов (сотни миллионов), при этом их производительность не снижается.
• Такое решение топологии является аддитивным. Как правило, вы можете добавить топологию к существующей схеме пространственно связанных классов объектов. Или, вам придется заново создать схему, имеющею возможность использования топологических примитивов, и загрузить в нее имеющиеся пространственные данные.
• Для редактирования геометрии и работы с данными, как правило, достаточно одной модели.
• Это стало возможным благодаря использованию спецификаций Открытого геопространственного консорциума и ISO для хранения геометрии всех пространственных объектов.
• Моделирование данных более естественно, т.к. оно основано на пользовательских пространственных объектах (таких как земельные участки, улицы, типы почв и водоразделы) вместо топологических примитивов (узлов, ребер и граней). Пользователи начинают оперировать категориями целостности данных относительно реальных объектов, а не следить за целостностью топологических примитивов. Например, как должны себя вести эти земельные участки? Такой подход упрощает моделирование всех типов географических объектов. Он упрощает представление о реальных объектах: улицах, типах почв, районах переписи, железнодорожных путях, лесах, ландшафтах и т.д.
• Топология базы геоданных обеспечивает то же информационное наполнение, что и предыдущие версии топологии – вне зависимости от того, храните ли вы топологический линейный граф и рассчитываете геометрию пространственных объектов (как в покрытиях) или храните геометрию объектов и вычисляете элементы топологии и связи (как в базах геоданных).

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

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

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

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

Теория точечных множеств в евклидовом пространстве послужила исходным пунктом в развитии общей идеи топологического пространства. Это началось с работ Фреше (1878-1973) 1907 года, посвященных -пространствам. Фреше, занимаясь исследованиями в области функционального анализа, определил пространство при помощи понятия сходимости, которое составляет ядро всей топологии. Заслуга Фреше в том, что он выдвинул основные положения абстрактного пространства. Это был отход от привычных рассмотрений в евклидовом пространстве. Точка абстрактного пространства - это уже не точка в том смысле, как это понимают в евклидовой геометрии. Если речь идет о множестве, в котором определено понятие сходимости, то это уже топологическое пространство. Абстрактная теория пространства постепенно слилась с тем, что определяется сейчас как теория топологических пространств. Абстрактизация идеи пространства открыла путь формированию многих важных понятий в различных разделах математики.

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

В 1909 году Рис (1880-1956) исследовал предельные точки множества. В 1914 году Хаусдорф (1868-1942) пришел к понятию

системы окрестностей. В 1922 году Куратовский (р. 1896) ввел аксиоматику замыкания, в 1925 году Александров (р. 1896) построил теорию открытых множеств, а в 1927 году Серпиньский (1882-1969) - теорию замкнутых множеств.

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

2. Комбинаторная топология. При исследовании геометрических свойств мнргообразий Пуанкаре пользовался разбиением многообразия на элементарные симплексы и, обратно, создавал из симплексов сложные комбинаторные структуры. При этом Пуанкаре применял аппарат введенных им групп гомологий. Дальнейший прогресс комбинаторной топологии связан с такими значительными результатами, как результаты Хопфа (1895-1971), теоремы о неподвижных точках отображения Лефшеца (1884-1972), теоремы двойственности Пуанкаре и Александера. Эти геометрические теории, представляя собой часть комбинаторной топологии, являются ветвью алгебраической топологии. Примерно с 1940 года она получила значительное развитие в связи с исследованиями линейных образов комбинаторных структур, где Уайтхедом (1904-1960) были получены замечательные результаты. Эта дисциплина стала называться -топологией.

О положительном решении общего предположения Пуанкаре уже говорилось выше. Затрагивая вопрос определения комбинаторных многообразий, мы не говорили об известном основном предположении комбинаторной топологии, которое в 1961 году Мазуром и Милнором (р. 1931) было опровергнуто.

Основное предположение комбинаторной топологии (Hauptvermutung). В начале XX века комбинаторная топология особенно сильное развитие получила в Германии, и подавляющее большинство работ публиковалось на немецком языке. Упоминаемая здесь основная гипотеза также впервые была сформулирована на немецком языке. И по сей день в различных трудах ее часто называют по-немецки Hauptvermutung. Формулировка этого предположения такова: если полиэдры двух комплексов К к К гомеоморфны, то можно подразделить их таким образом, что полученные в результате этого комплексы являются равными комплексами.

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

3. Алгебраическая топология. Алгебраическая топология представляет собой область геометрии, цель которой состоит в установлении топологических инвариантов на основе

применения теории групп. Алгебраическая топология считается ведущей областью топологии. Упоминавшаяся выше теория гомологий также относится к этой области геометрии. К числу других достижений алгебраической топологии относятся введенные в работах Александера и Колмогорова (р. 1903) группы когомологий.

В более позднее время алгебраическая топология сделала резкий скачок вперед благодаря работам Стинрода (1910-1971) по теории когомологий, опубликованным в 1947 году, и исследованию Серром (р. 1926) в 1951 году спектральных последовательностей.

4. Дифференциальная топология. Есть область топологии, объектом исследований которой являются дифференцируемые многообразия. Суть дифференцируемого многообразия состоит в возможности рассмотрения дифференцируемых функций, заданных на этом многообразии. Если о дифференцируемых многообразиях говорить конкретнее, то нужно прежде всего вспомнить, что каждая точка многообразия обладает окрестностью гомеоморфной открытому диску (или, что все равно, всему евклидову пространству). Координаты, заданные в евклидовом пространстве, посредством гомеоморфизмов переносятся в окрестность каждой точки многообразия. Это так называемые локальные координаты. Так как точка многообразия принадлежит одновременно многим окрестностям то ей соответствует столько же различных систем локальных координат. Многообразие дифференцируемоу если функции преобразования от одной локальной системы координат к другой являются дифференцируемыми.

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

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

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

Другими словами, гладкие структуры диффеоморфных между собой дифференцируемых

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

Фундаментальные исследования в дифференциальной топологии были проведены Уитни (р. 1907) в 1930 году. Затем активность исследований в этой области несколько снизилась.

В 1952 году Том (р. 1923), лауреат филдсовской премии 1958 года, опираясь на теорию кбгомологий и гомотопических групп, построил теорию кобордизмов. Недавно он разработал ставшую широко известной теорию катастроф.

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

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

областей всей математики. Ряд достижений дифференциальной топологии связан с комбинаторной топологией. Подтверждением этого является, например, теорема о том, что любое дифференцируемое многообразие есть комбинаторное многообразие.

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

Инструмент исследования в данном случае не представляет собой методически разработанную теорию. Изучение тех или иных геометрических фигур состоит в непосредственном

наглядном восприятии с последующим проведением цепочки строго обоснованных рассуждений. Поэтому здесь необходимы острота восприятия и правильность логического вывода. Из последних достижений в изучении патологических (диких) геометрических фигур можно, например, отметить исследования трехмерных многообразий. Проблема топологической классификации трехмерных многообразий, как это явствует уже из рассуждений относительно гипотезы Пуанкаре, далека от своего решения и представляется крайне сложной. Именно со стороны гипотезы Пуанкаре к задаче классификации подошли вплотную многие исследователи, получив значительные результаты. Хорошо известны исследования Папакирвякопулоса (1914-1976), в результате которых этот «уважаемый Пап» решил в 1957 году проблему Дэна (1878-1952) о сфере. Теорема о сфере формулируется следующим образом: если трехмерное ориентируемое многообразие с (двумерная гомотопическая группа), то существует вложенная в нестягиваемая двумерная сфера Эта сфера 52 как раз и обеспечивает нетривиальность двумерной гомотопической группы Эта теорема вскрывает еще одну связь между комбинаторной и алгебраической топологией. Надо сказать, что многие результаты одной области могут быть в определенной степени взаимно использованы в смежной области, хотя в каждом конкретном случае существо вопроса подлежит непосредственной проверке.

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

в 1910 году, когда он занимался изучением геометрии трехмерных многообразий. Однако вскоре Кнезер (р. 1898) и другие указали на пробелы в приведенном доказательстве. И только гораздо позже, в 1957 году, было получено окончательное доказательство.

В вопросах построения трехмерных многообразий из более простых многообразий Кнезером была предложена важная теорема, которая в 1962 году была улучшена Милнором. Упоминая об этих теоремах, мы, однако, из-за их сложности не приводим здесь даже формулировок.

Из работ, посвященных изучению «диких» многообразий, следует также отметить последовавшую за работами Антуана 1921 года работу Александера 1924 года, в которой он предложил конструкцию так называемой рогатой сферы. Рогатая сфера Александера, которая изображена на рис. 107, непривычная, сложная для восприятия дикая фигура. В дальнейшем исследования в этом направлении продолжены Столлингсом, Бингом (р. 1914) и другими.

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

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

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