I

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

В Послесловии А.А. Зыкова к книге К. Бержа [1, с. 303] отмечается, что «термин «граф» стал общепринятым после выхода в свет в 1936 г. монографии Кёнига, где представлен значительный материал и где графы рассматриваются в абстрактной форме как самостоятельные математические объекты». А.А. Зыков также подчеркивает [1, с. 306], что «сам язык теории графов делает изложение ряда дисциплин, могущих развиваться и без нее, более удобным и наглядным». Библиография к книге [1], 1958 г. содержит 179 источников.

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

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

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

II

Известный французский математик Дьедонне сообщает, что в 1-ю Мировую войну немцы своих математиков на фронт не отправляли, а французы – отправляли. Это привело к тому, что французская математика, которая века стояла во главе мировой математики, внезапно оказалась на третьих ролях. Амбициозная группа молодых французских математиков решила исправить это положение. Но для этого была нужна беспрецедентная идея.

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

В течение 30 лет, том за томом, эта группа издавала унифицированную математику под псевдонимом «Никола Бурбаки».

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

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

Хотя изложение проблемы теории шкал множеств выходит за рамки данной статьи, все же следует заметить, что являющаяся в большей степени социальной, чем профессиональной, эта проблема приобрела характер трагедии и для самой группы Н. Бурбаки. Она состоит в том, что ступени множеств, реализованные при унификации современной математики, в основном принадлежат 1-й шкале множеств, частично 2-ой и 3-ей. Между тем, множество шкал счетно, а это значит, что современная математика при всех ее гигантских масштабах является ничтожной частью математики, определяемой множеством шкал множеств. Даже сам автор – Н. Бурбаки – не мог осознать величия того, что создал его интеллект.

III

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

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

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

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

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

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

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

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

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

IV

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

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

При рассмотрении вопроса о разнообразии типов графов, имеющемся в источниках [1 – 16], следует иметь в виду, что «большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою терминологию [7, с. 21]. В источниках [1 – 16] вводятся только типы графов, определенные на одном множестве вершин, что является, возможно, наиболее существенным ограничением существующих вариантов теории графов с точки зрения теории ступеней, иными словами, применяются во внимание только ступени первой шкалы множеств. Так называемые «хроматические» графы определены не на множестве базисных множеств, а на одном множестве вершин, имеющем подмножества (отсюда «разные цвета» вершин разных подмножеств).

Основными различиями типов графов, вводимых в источниках [1 – 16], являются:

-  конечность или бесконечность мощности множества вершин,

-  ориентированность или неориентированность дуг (или часть дуг – ориентированная, а часть дуг – неориентированная),

-  наличие или отсутствие петель у вершин,

-  наличие или отсутствие кратности ребер (дуг) – признак мультиграфа,

-  вершины – это одиночные элементы множества вершин или множества (графы пересечений множеств),

-  степень графа (число дуг одной вершины), диаметр графа (максимальное число дуг в «сечении» графа), охват графа,

-  полные или неполные графы (декартиан или бинарное отношение),

-  наличие или отсутствие у графа автоморфизмов n-го порядка,

-  связность или несвязность,

-  помеченные вершины графа (различимые) или непомеченные,

-  регулярность графа или нерегулярность (регулярный граф – если все вершины имеют одинаковую степень),

-  циклические или ациклические графы, кратные или некратные циклы,

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

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

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

V

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

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

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

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

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

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

1. Разнообразие вершин графа

1.1. Гиперграфы

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

№ п/п	Понятие вершины	Выражение	Название гиперграфа	Иллюстрации
1.	Элемент множества Х	х Î Х	Граф	рис. 1.1. – 1
2.	Подмножество множества Х	х Î В(Х)	Гиперграф-1	рис. 1.1. – 2
3.	Подмножество множества подмножеств множества Х	х Î ВВ(Х)	Гиперграф-2	рис. 1.1. – 3
4.	Подмножество множества подмножеств множества подмножеств множества Х	х Î ВВВ(Х)	Гиперграф-3	рис. 1.1. – 4
…	…..	…..	…..	…..
n	n-1 кратн. подмн. множества Х	х Î В…В(Х) n раз	Гиперграф-n	–

 

Рис. 1.1-1. Фрагмент графа.

 

Рис. 1.1-2. Фрагмент гиперграфа-1.

 

Рис. 1.1-3. Фрагмент гиперграфа-2.

 

Рис. 1.1-4. Фрагмент гиперграфа-3.

1.2. В-хромграфы

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

№ п/п	Понятие вершины	Выражение	Название В-хромграфа	Иллюстрации
1.	Элемент единственного базисного множества	х Î Х	Монохром	рис. 1.2. – 1
2.	Элемент либо одного базисного множества, либо другого	х Î Х y Î Y	Бихром	рис. 1.2. – 2
3.	Элемент либо одного, либо второго, либо третьего базисного множества	х Î Х y Î Y z Î Z	Тернохром	рис. 1.2. – 3
4.	Элемент либо одного, либо второго, либо третьего, либо четвертого базисного множества	х Î Х y Î Y z Î Z c Î C	Тетрахром	рис. 1.2. – 4
…	…..	…..	…..	…..
n	Элементы каждого из n базисных множеств	х1 Î Х1 … хn Î Хn	n-хром	–

 

Рис. 1.2.-1. Монохром

 

Рис. 1.2.-2. Бихром

 

Рис. 1.2.-3. Тернохром

 

Рис. 1.2.-3. Тетрахром

1.3. ГиперВ-хромграфы

Полное разнообразие гиперВ-хромграфов образуется всеми комбинациями видов гиперграфов и В-хромграфов. Например, «гиперВ-хромграф 1-3» представляет комбинацию гиперграфа-1 и тернохрома (рис. 1.3. – 1).

 

Рис. 1.3.-1. ГиперВ-хромграф 1-3

2. Разнообразие дуг

В соответствии с местностью декартиана дуги могут быть:

-  для двухместного декартиана: дуги-2,

-  для трехместного декартиана: дуги-3,

-  для четырехместного декартиана: дуги-4,

………….,

-  для n-местного декартиана: дуги-n.

Рассмотрим разнообразие дуг-2 в гиперграфах и хромграфах.

2.1. Разнообразие дуг-2 в гиперграфах по числу дуг-2 в каждой паре вершин («мультиграфы»)

Гомоаркграфы:

-  две дуги – гомоаркграф-2

-  три дуги – гомоаркграф-3

………

-  n дуг – гомоаркграф-n.

Гетероаркграфы

-  одна или две дуги

-  одна или три дуги

……….

-  две или три дуги

-  две или четыре дуги

….........

-  одна или две или три дуги

-  одна или три или четыре дуги.

2.2. Разнообразие дуг-2 в хромграфе

В бихромграфах:

-  дуги соединяют только разноцветные вершины

-  дуги соединяют и одноцветные вершины, и разноцветные вершины.

В тернохромграфах:

……….

В тетрахромграфах

………..

2.3. Разнообразие дуг в гиперхромграфах

……….

3. Разнообразие метризации

3.1. По средствам метризации

-  метризация одним числом

• не аддитивная
• аддитивная

-  метризация двумя числами

……….

……….

3.2. По предметам метризации

-  метризация вершин

-  метризация дуг

-  метризация элементов топологии графа (ветвлений, циклов и др.)

3.3. По распространению метризации

-  ни один предмет метризации ни одним средством метризации не метризован

-  некоторые предметы метризации метризованы некоторыми средствами метризации

-  все предметы метризации метризованы некоторыми средствами метризации.

_________ _о ________

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

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

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

Для таких графов уместно название «диверсграфов», т.е. разнообразия графов на одном и том же множестве вершин.

Если дуги различаются цветом, а граф предполагается хроматическим, то уместно графы с разноцветными вершинами называть «В-хроматическими», с разноцветными дугами – «Д-хроматическими», а если и вершины, и дуги являются разноцветными, то называть «ВД-хроматическими».

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

Типичным примером диверсграфа является определение на одном множестве отношения порядка и отношения эквивалентности.

 

Литература[2]

1. Берж К. Теория графов и ее применение. Пер. с франц. – М.: Иностранная литература, 1962. – 319 с.
2. Оре О. Графы и их применение. Пер. с англ. – М.: Мир, 1963. – 174 с.
3. Оре О. Теория графов. Пер. с англ. М.: Наука, 1969. – 352 с.
4. Зыков А.А. Теория конечных графов-1. – Новосибирск: Наука, 1969. – 543 с.
5. Гроссман И., Магнус В. Группы и их графы. – М.: Мир, 1971. – 231 с.
6. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – 415 с.
7. Харари Ф. Теория графов. Пер. с англ. – М.: Мир, 1973. – 300 с.
8. Теория графов. Покрытия, укладки, турниры. Сб. переводов. – М.: Мир, 1974. – 223 с.
9. Басакер Р., Саати Т. (R.G. Basacker, T.L. Saaty). Конечные графы и сети. М.: Наука, 1974. – 367 с.

10.  Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. – М.: Наука, 1974. – 304 с.

11.  Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 208 с.

12.  Харари Ф, Палмер Э. Перечисление графов. 1977.

13.  Кристофидес Н. Теория графов: алгоритмический подход. – М.: Мир, 1978. – 429 с.

14.  Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 326 с.

15.  Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. – М.: Наука, 1981. – 344 с.

16.  Донец Г.А., Шор Н.З. Алгебраический подход к проблеме раскраски плоских графов. – Киев: Наукова думка, 1982. – 143 с.

17.  Свами М., Тхуласираман К. Графы, сети и алгоритмы. 1984.

18.  Зыков А. Основы теории графов. – М.: Наука, 1987. – 381 с.

19.  Татт У. Теория графов. – М.: Мир, 1988. – 424 с.

20.  Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. – Новосибирск: Наука (Сибирское отделение), 1990.

21.  Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. и др. Лекции по теории графов. – М.: Наука, 1990.

22.  Евстигнеев В.А., Касьянов В.Н. Теория графов. Алгоритмы обработки деревьев. – Новосибирск: Наука, 1994. – 360 с.

23.  Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. – М.: Мир, 1998.

24.  Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. – М.: Синтег, 2001.

25.  Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. 2001.

26.  Дистель Рейнгард. Теория графов. Пер.с англ. – Новосибирск: Изд-во Института Математики, 2002. – 336 с.

27.  Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – Санкт-Петербург: БХВ-Петербург, 2003. – 1104 с.

28.  Калмыков Г.И. Древесная классификация помеченных графов. ФМЛ, 2003. – 190 с.

29.  Колчин В.Ф. Случайные графы. 2-е изд., ФМЛ, 2004. – 256 с.

30.  Покорный Ю.В. и др. Дифференциальные уравнения на геометрических графах. ФМЛ, 2005. – 269 с.