Специальные разделы теории графов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ 

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное 

учреждение высшего образования 

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Инженерно-технологическая академия

Л. А. ГЛАДКОВ, Н. В. ГЛАДКОВА, 

В. В. КУРЕЙЧИК, В. М. КУРЕЙЧИК

СПЕЦИАЛЬНЫЕ РАЗДЕЛЫ ТЕОРИИ ГРАФОВ

Учебное пособие

Ростов-на-Дону  Таганрог

Издательство Южного федерального университета

2018

УДК 519.14(075.8)
ББК 22.174.1я73

Г522

Печатается по решению кафедры систем автоматизированного 

проектирования Института компьютерных технологий и 

информационной безопасности Южного федерального университета 

(протокол №5 от 27 января 2017 г.)

Рецензенты:

зав. кафедрой компьютерных образовательных технологий

Санкт-Петербургского государственного университета информационных 

технологий, механики и оптики, доктор технических наук, 

профессор Л. С. Лисицина

кандидат технических наук, доцент кафедры САУ ЮФУ А. Я. Номерчук

Гладков, Л. А.

Г522
Специальные разделы теории графов
:
учебное пособие
/ 

Л. А. Гладков, Н. В. Гладкова, В. В. Курейчик, В. М. Курейчик ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2018. – 111 с.

ISBN 978-5-9275-2779-3
Рассмотрены основные положения специальных разделов теории графов, та
ких как изоморфизм, паросочетания, планарность и минимизация пересечений.
Приведены основные определения и элементы теории, а также рассмотрены 
примеры их практического решения. Для проверки уровня освоения материала 
приведены вопросы и задания для самостоятельной работы учащихся. Учебное 
пособие предназначено для студентов вузов, обучающихся по направлениям 
«Информатика и вычислительная техника» и «Информационные системы». Пособие может быть полезным для специалистов, занятых разработкой интеллектуальных систем, новых информационных технологий в науке, технике, экономике.

УДК 519.14(075.8)

ББК 22.174.1я73

ISBN 978-5-9275-2779-3

© Южный федеральный университет, 2018
© Гладков Л. А., Гладкова Н. В.,

Курейчик В. В., Курейчик В. М., 2018

© Оформление. Макет. Издательство 

Южного федерального университета, 2018

ВВЕДЕНИЕ

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

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

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

Список рекомендуемой для изучения литературы находится в конце 

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

1. ИЗОМОРФИЗМ ГРАФОВ

Многие задачи информатики сводятся к различным тождественным 

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

Большое число комбинаторно-логических и оптимизационных задач 

на требует установления изоморфизма или изоморфного вложения между 
заданными структурами. Эта задача, как и многие другие графовые задачи, 
является NP-полной. Поэтому разрабатываются различные эвристики для 
получения приемлемых практических результатов [14, 1118].

Два графа G1 = (X1, U1) и G2 = (X2, U2) называются изоморфными, ес
ли можно установить взаимно однозначное соответствие отображение 
: X1  X2 такое, что ребро u = (x, y)  U1 тогда и только тогда, когда 
((x), (y))  U2. Соответственно для того, чтобы ответить на вопрос: возможно ли установить такое отображение, необходимо решить задачу распознавания изоморфизма графов (РИГ) [1, 2, 1118].

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

Изоморфные графы могут быть получены один из другого путем пе
ренумерации их вершин. Очевидно, что изоморфизм есть отношение эквивалентности на графах. Графы G и G’, изображенные на рис. 1 и 2, изоморфны. Подстановка


























6
4
2
5
3
1

6
5
4
3
2
1

x
x
x
x
x
x

x
x
x
x
x
x

t







переводит граф G в G'.

Для перехода от графа G' к графу G необходимо применить обратную 

подстановку t-1 к графу G:

.

6
3
5
2
4
1

6
5
4
3
2
1

1


























x
x
x
x
x
x

x
x
x
x
x
x

t







1. Изоморфизм графов

5

1

3
5

6

4

2

1
3

5
6
4

2

а)
б)

Рис. 1. Пример изоморфной подстановки

Если изоморфные преобразования проводятся с графом, заданным 

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

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

Например, матрица смежности графа G (рис. 1 а) имеет вид:

1’ 2’ 3’ 4’ 5’ 6’

1’ 0
1
0
1
0
1

2’ 1
0
1
0
1
0

R’ = 3’
0
1
0
1
0
1

4’ 1
0
1
0
1
0

5’ 0
1
0
1
0
1

6’ 1
0
1
0
1
0

а матрица смежности R' графа G' (рис. 1 б) запишется

1
2
3
4
5
6

1
0
0
0
1
1
1

2
0
0
0
1
1
1

R = 3
0
0
0
1
1
1

4
1
1
1
0
0
0

5
1
1
1
0
0
0

6
1
1
1
0
0
0

1. Изоморфизм графов

6

Если к матрице R применить подстановку t-1, то получим матрицу

1
2
3
4
5
6

1 0
1
0
1
0
1

2 1
0
1
0
1
0

Rt = 3
0
1
0
1
0
1

4 1
0
1
0
1
0

5 0
1
0
1
0
1

6 1
0
1
0
1
0

Особого внимания заслуживают сильнорегулярные графы (СГ). 

Граф G = (X, , n1

11, n0

11), |X| = n называется n  вершинным регулярным 

графом степени , если в нем любая пара смежных вершин имеет n1

11 об
щих соседей, а любая пара несмежных вершин  n0

11. Известно, что СГ об
разуют класс наиболее трудных задач для РИГ.

Задача изоморфного вложения графа является NP- полной задачей. 

Она имеет много сходства и в то же время существенно (по сложности) отличается от РИГ. Например, для решения задачи изоморфизма подграфа G1
с использованием известных алгоритмов РИГ необходимо разработать 
процедуру выделения в графе G подмножества X1  X равномощного с 
множеством вершин X2 графа G2.

Данная процедура включает k1 действий, где, n = |X|, n2 = |X2|. Следо
вательно, k1 раз надо применять и алгоритм РИГ: 











2

1
n
n
k
.

Поэтому при выделении каждого подграфа G1 в графе G необходимо 

выполнять k2 действий:












2

1

2
m

m
k
,

где m1 - количество ребер в подграфе G1, m2 - в графе G2, m1 > m2.

Следовательно, даже если есть полиномиальный алгоритм РИГ, с его 

помощью невозможно решить задачу изоморфного вложения за полиномиальное время. Она может быть решена за полиномиальное время, если 
G1 – лес, а G2 – дерево.

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

1. Изоморфизм графов

7

различные уровни. При этом ВСА алгоритма снижается с О(n!) до О(k!), 
где n  число элементов в графе, а k  число элементов в наибольшем автоморфном подграфе, т.е. в таком подграфе, где не имеет значения выбор 
вершин для установления соответствия.

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

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

Пример 1. Рассмотрим два графа G и G'. G = (Х, U), G' = (Х', U'), 

|Х| = |Х'| = 6, |U| = |U'| = 9, локальные степени всех вершин графа равны трем
(рис. 1 а, б).

Необходимо установить изоморфизм графов G и G'. Другими слова
ми, необходимо определить, существует ли отношение эквивалентности 
Х  Х', U  U' такое, что, если ребро (xi, xj)  ребру (xi', xj'), тогда xi  xi', 
xj  xj', xi, xj,  X, xi', xj',  X’.

1
2
3
4
5
6

1
0
1
1
1
3

2
1
0
1
1
3

RG =
3
1
0
1
1
3

4
1
1
0
1
3

5
1
1
0
1
3

6
1
1
1
0
3

X1

1
X2

1
X3

1
X4

1
X5

1
X6

1

X1

1
o
1
1
1
3

X2

1
0
1
1
1
3

RG

1 =
X3

1
0
1
1
1
3

X4

1
1
1
1
0
3

X5

1
1
1
1
0
3

X6

1
1
1
1
0
3

Выберем одну вершину в графе G и одну в графе G'. И относительно 

них выполним указанное выше разбиение:

1. Изоморфизм графов

8

{х1}
{х2, х4, х6}1+
{х3, х5}1(G),

{х1'} {х4', х5', х6'}1’+
{х2', х3'}1’(G').

В данном разбиении вершины х2, х4, х6 смежны вершине х1, а верши
ны х3, х5 не смежны вершине х1 графа G. Аналогичное разбиение выполнено для графа G'. Здесь считается, что вершины х1 и х1' предполагаемо изоморфны (П-изоморфны). Далее, выбираются подмножества меньшей мощности и внутри них проверяется смежность вершин. В нашем примере вершины х3, х5 и х2', х3' не смежны. Поэтому процесс разбиения продолжается.

{х1}
{х3}1{{х2, х4, х6}3+}1+
{{х5}3-}1-,

{х1'}
{х2'}1’{{х4', х5', х6'}2’+}1’+
{{х3'}2’-}1’
Продолжая процесс аналогично, получим, что граф G изоморфен 

графу G'. Подстановка вершин запишется
















6
3
5
2
4
1

6
5
4
3
2
1
t

В рассматриваемом примере подмножества вершин {х2, х4, х6} и 

{х4', х5', х6'} являются автоморфными, т.е. каждая вершина в одном подграфе может быть изоморфна любой вершине второго подграфа.

G' преобразовали в G на основе подстановки

1’
2’
3’
4’
5’
6’

1(1’)
0
1
1
1
3

2(4’)
1
0
1
1
3

RGП =
3(2’)
1
0
1
1
3

4(5’)
1
1
0
1
3

5(3’)
1
1
0
1
3

6(6’)
1
1
1
0
3

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

Пример 2. На рис. 2 показаны нетривиальные, неоднородные графы 

G и G'. В этих графах |Х| = |Х'| = 7, |U| = |U'| = 8, 1 = 1, 2 = 3, 3 = 3, 4 = 3, 
5 = 3, 6 = 2, 7 = 1; a = 1, b = 3, c = 3, d = 3, e = 3, f = 2, g = 1. 
Вершина 1 может быть П–изоморфна вершине a или g. В первом случае 

1. Изоморфизм графов

9

нас ждет тупик, а во втором успех. Мы предположили, что вершина 1 
П-изоморфна вершине g. Тогда на основе связности графа и эвристики разбиения следует, что вершина 7 П-изоморфна вершине a. Из этого вытекает, 
что вершина 6 П-изоморфна вершине f.

1
2

3

4

 5
6
7

f
e

d

c

b
a
g

Рис. 2. Нетривиальные графы G и G'

1
2
3
4
5
6
7

1
0
1
1

2
1
0
1
1
3

RG =
3
1
0
1
1
3

4
1
1
0
1
3

5
1
1
0
1
3

6
1
0
1
2

7
1
0
1

a
b
c
d
e
f
g

a
0
1
1

b
1
0
1
1
3

RG’ =
c
1
0
1
1
3

d
1
1
0
1
3

e
1
1
0
1
3

f
1
0
1
2

g
1
0
1