Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3. Графы. Вводные замечания

В «Лекциях о развитии математики в XIX столетии» немецкий математик Феликс Клейн (1849–1925) после формулировки четырех условий, определяющих алгебраическую группу, написал следующее: «Таким образом, какая-либо апелляция к воображению здесь отсутствует в принципе. Взамен этого тщательно препарируется логический скелет... Подобного рода абстрактные формулировки превосходны для шлифовки доказательств, но они совершенно не годятся для того, чтобы с их помощью отыскивать новые идеи и методы. Более того, как правило, они являются завершением определенного этапа предшествующего развития. Поэтому внешне они облегчают преподавание, поскольку на их основе можно просто и без каких-либо пробелов доказывать известные уже предложения. Однако они внутренне чрезвычайно затрудняют учащегося, так как он оказывается поставленным перед чем-то совершенно законченным, ничего не зная о том, как автор пришел к этим определениям; к тому же он не может себе абсолютно ничего представить. Этот метод не поощряет к тому, чтобы пользующийся им мыслил; требуется лишь внимательно следить, чтобы не погрешить против данных нам четырех заповедей».

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

На сегодняшний день существует масса учебной литературы по дискретной математике, в которой теория групп, как основа для современной абстрактной алгебры, занимает видное место. В поверхностные курсы «Дискретной математики» группы вошли отдельными главами чаще всего в слишком абстрактном, а значит, и плохо усваиваемом виде (на что в свое время сетовал Феликс Клейн). В этих книгах можно отыскать любую формулировку, относящуюся к той или иной характеристике групп, причем, возможно, самую правильную и идеально отточенную дефиницию. Но там нельзя найти одного – самих групп. Этот изъян можно преодолеть, если отказаться от формально-логического подхода и попытаться встать на конструктивный путь рассмотрения групп, детально изучая их свойства и морфологию. Математика обоснования отличается от математики поиска, причем человек, имеющий склонность к новаторскому творчеству, не слишком будет утруждать себя зубрежкой определений и теорем. Воспроизведение готовых доказательств не учит поиску решений трудных задач; эти два рода занятий различны и редко совместимы в одном человеке. То же самое касается теории графов. Литература по графам весьма разнообразна и неоднородна, так как к графическим схемам и диаграммам прибегают всякий раз, как только возникает желание отобразить скупую математическую символику в каких-то запоминающихся наглядных образах. Однако это визуальное качество помогло нам в одной главе под названием «Графы» объединить самую разноплановую тематику: от автоматов и электротехнических схем до теории оптимального кодирования и порождающих грамматик, поскольку ко всем этим задачам можно применить теорию графов.

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

С графами мы сталкиваемся повсюду, например, когда смотрим на карту Московского метрополитена, карту автомобильных или железных дорог, пытаясь визуально решить проблему нахождения минимального пути – одну из основных задач теории графов. Даже политическая карта послужила толчком к формулировке одной из самых трудных задач математики: о раскраске стран в четыре цвета. Эта задача стимулировала развитие не только теории графов, но и топологии, так как оказалось, что для раскраски политической карты, нанесенной, например, на тор, нужно уже семь цветов. Схемы графов рисовал Г. Кирхгоф (1847) для электротехнических цепей. Занимаясь химией, А. Кэли (1857) с помощью древовидной формы пытался изобразить пространственное расположение атомов в молекулах углеводородов. В. Гамильтон (1859) предлагал обойти вершины додекаэдра по одному разу (отсюда происходит термин гамильтонов маршрут). А. Пуанкаре (1899) в своих топологических исследованиях также опирался на все те же графы. Это эпизодическое использование отвлеченных графических схем закладывало фундамент будущей математической теории, рождение которой традиционно связывают с Д. Кёнигом и О. Вебленом, издавшими в 30-х годах XX в. серьезные монографии по графам. Авторы этих первых исследований сразу же увязали теорию графов с комбинаторикой и топологией, к которым впоследствии присоединилось множество научных направлений, так или иначе обслуживающих компьютерные технологии.

Уже в первой задаче по теории графов Эйлер использовал основные понятия, определяющие граф: вершина, ребро, инцидентность, никак не определяя их. Граф – это наглядный образ, достоинство которого как раз и состоит в том, что он требует минимум слов и символов, но дает максимум пространственных и структурных представлений. Он является, возможно, самым гибким математическим объектом, который способен легко приспособиться под любую конкретную модель. Логические и лингвистические позитивисты думали найти решение онтологических проблем в сфере языка и в формально-логических системах, замкнутых на конвенциальную аксиоматику. Они надеялись, что семантические договоренности помогут им «адаптироваться к принципиально непознаваемой» окружающей среде. Это, по их мнению, должно было положить конец бесконечным спорам между учеными. Такая консолидированная позиция ухода от реальных проблем только усилила бесплодные споры о словах и помешала решать насущные проблемы науки. Разговоры вокруг определения графа красноречиво иллюстрируют это непродуктивное направление в науке.

Фрэнк Харари, известный теоретик в этой области, имея в виду граф в его самых бесхитростных формах, «предпочитает использовать слова point (точка) и line (линия), учитывая сложившуюся традицию употреблять их как неопределяемые понятия». Элементы графа – vertex (вершина) и edge (ребро) – позаимствованы из геометрии многогранников, которая тесно связана с графами. А как быть с решеткой – это граф или не граф? Путаницы здесь, видимо, не избежать. Харари отмечает, что среди самобытных ученых терминологического согласия достичь невозможно и различные определения графа все равно будут непрерывно подвергаться атакам. Он пишет: «Даже само слово граф не является священным. Некоторые авторы действительно определяют граф, как граф, другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф и сеть. Нам кажется, что единообразие в терминологии графов никогда не будет достигнуто, но оно и ни к чему».

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

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

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