Обобщенные графы и грамматики

ОБОБЩЕННЫЕ ГРАФЫ 

И ГРАММАТИКИ

А.И. МИКОВ

Москва

ИНФРА-М

2021

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано Межрегиональным учебно-методическим советом 

профессионального образования в качестве учебного пособия для студентов 

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

направлений подготовки 02.00.00 «Компьютерные и информационные науки», 

09.00.00 «Информатика и вычислительная техника» 

(квалификация (степень) «магистр») (протокол № 12 от 14.12.2020)

УДК 519.179(075.8)
ББК 22.176я73
 
М59

Миков А.И.
М59  
Обобщенные графы и грамматики : учебное пособие / А.И. Миков. — 
Москва : ИНФРА-М, 2021. — 192 с. — (Высшее образование: Магистратура). — DOI 10.12737/1013698.

ISBN 978-5-16-014970-7 (print)
ISBN 978-5-16-107465-7 (online)

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

УДК 519.179(075.8)
ББК 22.176я73

Р е ц е н з е н т ы:
С.В. Русаков, доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики и информатики Пермского государственного национального исследовательского университета;
А.Н. Ткачев, доктор технических наук, профессор, заведующий кафедрой прикладной математики Южно-Российского государственного политехнического университета (НПИ) имени М.И. Платова

ISBN 978-5-16-014970-7 (print)
ISBN 978-5-16-107465-7 (online)
© Миков А.И., 2021

Предисловие

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

Предисловие

кладной точки зрения, этот класс нужно описать, установить 
его свойства (сформулировать теоремы). Для многих классов 
графов эта работа требует высочайшей математической квалификации и настойчивости. Почему изучение бинарных отношений может оказаться таким трудным? Потому что, рассматривая не отдельный граф, а класс графов, приходится оперировать не парами вершин, а большими наборами (цепями, 
циклами, кликами), т.е. погружаться в n-арные отношения. 
К тому же сюда часто добавляется комбинаторика (раскраски 
графов, симметрии в графах).
Второй источник трудностей в том, что многие задачи 
о графах на самом деле затрагивают и другие области математики. Например, задача о планарности — расположении графа 
на плоскости без пересечений ребер. Здесь уже не обойтись 
без топологии. Недаром основная теорема о характеризации 
планарных графов была доказана известными топологами 
К. Куратовским и Л. Понтрягиным.
В настоящее время кроме обыкновенных графов, которым 
посвящено большое количество монографий и учебников, изучаются и более сложные конструкции, порожденные различными прикладными задачами. Они являются обобщениями 
обыкновенных графов, включают дополнительные элементы 
или ослабляют ограничения, принятые для обыкновенных 
графов.
Некоторые из обобщений рассматриваются в этой книге 
после первой главы, в которой напоминаются основные алгебраические понятия.
Содержание книги нацелено на то, чтобы студенты магистратуры приобрели и (или) упрочили ряд компетенций в области фундаментальной информатики и информационных 
технологий.
Во-первых, это способность использовать углубленные 
теоретические и практические знания в области информационных технологий и прикладной математики, фундаментальных концепций и системных методологий, междуна

Предисловие

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

Автор будет благодарен за отзывы и замечания, присланные 
ему по адресу: alexander_mikov@mail.ru.

Благодарности
В книге использованы результаты, полученные при проведении научных исследований, поддержанных грантом РФФИ 
№ 18-01-00359 и грантом РФФИ и администрации Краснодарского края № 19-47-230003.

Глава 1.

ОТНОШЕНИЯ И АЛГЕБРАИЧЕСКИЕ 
СТРУКТУРЫ

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

1.1. МНОЖЕСТВА И ОТНОШЕНИЯ

Определение 1. Произвольные совокупности объектов 
(элементов) в математике называются классами.
Определение 2. Два класса A и B называются равными, A  B, 
если они имеют одни и те же элементы.
Пусть P(X) — некоторое высказывание о классе X. Для некоторых классов, которые можно подставить в это высказывание на место X, высказывание истинно, для некоторых — 
ложно.
Определение 3. Аксиомой считается следующее утверждение: «Если A  B, то P(A) истинно тогда и только тогда, 
когда истинно P(B)». Отрицание этого утверждения обозначается A  B.
Вторая аксиома теории множеств гласит: «Существует 
класс, обозначаемый {X | P(X)}, членами которого являются те 
и только те множества X, для которых P(X) истинно».
Здесь необходимо пояснить, что множеством называется 
класс, являющийся элементом некоторого класса.
Иначе говоря, между классами определяется бинарное отношение X  Y, читаемое как «X есть член (или элемент) Y» или 
«X принадлежит Y». Если некоторый класс X находится в этом 
отношении с классом Y, то мы вправе называть X множеством. 
При этом Y — класс, а не множество, но может им быть, если Y, 
в свою очередь, принадлежит какому-нибудь классу.

1.1. Множества и отношения

Приведенную математическую терминологию нужно иметь 
в виду, поскольку часто в прикладных работах можно встретить фразу: «Пусть C — множество всех (и далее следует наименование каких-либо объектов)». При этом не имеется 
в виду, что C является членом какого-то класса. Правильно C 
в этом случае именовать классом.
Определение 4. Пустой класс, обозначаемый , определяется равенством   {X | X  X}.
Определение 5. Универсальный класс в теории множеств 
определяется как {X | X  X}.
Определение 6. Класс A называется подклассом класса B, 
(обозначается A  B), если x  B для всех таких x, что x  A.
Определение 7. Класс A называется собственным подклассом класса B, если A  B и A  B.
Определение 8. Класс {x | x  A и x  B}, обозначаемый 
записью A \ B, называется дополнением B в A.
Определение 9. Булеаном (обозначается 2A) класса A называется класс 2A  {X | X  A}. Булеан для множеств — это множество всех подмножеств данного множества.
Определение 10. Декартовым произведением классов A и B 
называется {z | z  (x, y), где x  A и y  B}. Обозначается A × B.
Определение 11. Любое подмножество декартова произведения A × B называется соответствием (чаще используется 
термин «бинарное отношение»).
Декартово произведение можно естественным образом 
определить не только для пар множеств, но и для n множеств. 
Его обозначают A1 × A2 × A3 × … × An. Если все множества, образующие декартово произведение, одинаковы, то оно обозначается An. Соответственно и отношения могут быть не только 
бинарные, но и тернарные и т.д. Для произвольного числа n 
отношение на A1 × … × An называется n-арным или n-местным 
(по-английски — n-tuple).
Факт того, что некоторый набор (x1, …, xn)  A1 × … × An 
принадлежит отношению R, обозначают R(x1, …, xn). Здесь R — 
обозначение (или имя) отношения.

Глава 1. Отношения и алгебраические структуры

Отношения — одно из наиболее важных понятий в теории 
информационных систем.
Унарное отношение (n  1) — это просто некоторое подмножество множества A. Унарное отношение часто связывают 
с некоторым высказыванием о множестве A: на элементах, входящих в подмножество, оно истинно, а на остальных — ложно. 
Это высказывание называют еще свойством или характеристическим свойством подмножества.
Бинарное отношение diag(A)  {(x, x) | x  A} называется 
диагональю множества A. Оно определено на декартовом произведении A × A.
Наиболее изучены бинарные отношения. В классе бинарных отношений вводятся операции над отношениями.
Пусть отношение R определено на декартовом произведении A × B, а отношение Q — на декартовом произведении B × C множеств B и C.
Определение 12. Произведение двух отношений R и Q определяется как

и
для некоторого
{( , ) | ( , )
( , )
}
R Q
x z
x y
R
y z
Q
y
=
∈
∈
.

Отношение R Q
определено на декартовом произведении 
множеств A × C. Произведение R R
двух одинаковых отношений обозначают R2. Обобщая, можно определить k-ю степень отношения 
1
k
k
R
R
R −
=
.
Определение 13. Обращение S отношения R определяется 
формулой

{( , ) | ( , )
}
S
x y
y x
R
=
∈
.

Отношение S при этом называется обратным к R и обозначается S  R–1. Оно определено на декартовом произведении B × A.
Некоторые важные свойства бинарных отношений 
для случая A  B  C получили специальные названия. Так, 
отношение R называется: симметричным, если R–1  R; антисимметричным, если R  R–1  diag(A); рефлексивным, если 
diag(A)  R; транзитивным, если R ° R  R.

1.2. Универсальные алгебры,  структуры и модели

Объединение R и всех его степеней Rk (k  2, 3, …) называется транзитивным замыканием отношения и обозначается R*.
Транзитивное рефлексивное отношение называется предпорядком в (на) множестве A.
Асимметричный предпорядок называется частичным порядком в (на) множестве A.
Частичный порядок, удовлетворяющий равенству отношений R  R–1  A2, называется линейным или полным порядком.

Пример 1. Множество T моментов времени вместе с отношением «меньше или равно» () является линейно упорядоченным 
множеством.

Эти свойства отношений на таких множествах A, как множество чисел, множество графов и других объектов классической математики, порождают множество следствий и являются 
в значительной мере содержанием этих областей математики.
К сожалению, лишь немногие отношения в организационных предметных областях можно сформулировать как отношения на одном множестве A. Чаще это отношения на A × B 
или даже отношения на A1 × … × An при несовпадающих множествах Ai. В данном случае о перечисленных свойствах говорить 
не приходится и математические модели организационных 
предметных областей сразу «беднеют». Аналитики организационных предметных областей, правда, стараются обходиться 
бинарными отношениями (n  2), но это не спасает положения.

1.2. УНИВЕРСАЛЬНЫЕ АЛГЕБРЫ, 
СТРУКТУРЫ И МОДЕЛИ

На основе (n + 1)-арного отношения R  A1 × … × An × An+1 
можно определить n-арное отображение. При этом в наборе 
(x1, …, xn, xn+1), где xi  Ai, последний элемент xn+1 выделяется 
как образ набора (x1, …, xn) из n элементов. Соответственно 
набор (x1, …, xn) называется прообразом элемента xn+1. Получается новое бинарное отношение R2 «прообраз — образ» между 

Глава 1. Отношения и алгебраические структуры

n-ками (x1, …, xn) из A1 × … × An и элементами xn+1 из множества An+1. Условно это можно записать так: R2  (A1 × … ×
× An) × An+1.

Если любой набор (x1, …, xn) имеет единственный образ 

xn+1, то получившаяся конструкция называется отображением и обозначается f: A1 × … × An  An+1. Соотношение между 
образом и прообразом записывается так: xn+1  f(x1, …, xn), хотя 
в математике (особенно в комплексном анализе) рассматривают и многозначные отображения.

Определение 14. Если любое возможное сочетание x1, …, xn

входит в какой-нибудь набор (x1, …, xn, xn+1) из R, то говорят, 
что соответствующее отображение f всюду определено.

Во всюду определенном отображении f каждому набору (x1, 

…, xn)  A1×…×An соответствует какой-нибудь элемент xn+1  An+1. 
Если это не так, то отображение называется частично определенным, или частичным. В частичном отображении некоторые 
наборы (x1, …, xn)  A1 × … × An не имеют образов.

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

Интересен вариант совпадения множеств: A1  …  An  A. 

В этом случае A1 × … × An  An . Тогда n-арная операция отображает набор из n элементов, принадлежащих множеству A, 
в элемент, принадлежащий также множеству A.

Теперь предположим, что выделено некоторое подмноже
ство B  A и элементы, формирующие набор (x1, …, xn), берутся 
из этого подмножества, т.е. xi  B. Тогда результат операции 
над набором необязательно принадлежит подмножеству B.

Пример 2. Пусть A — множество рациональных чисел, а B — 

множество целых чисел. Операция деления числа на два (x/2) пе