close

Вход

Забыли?

вход по аккаунту

?

704.Элементы теории графов Изоморфизм планарность маршруты в графах Рублев В С

код для вставкиСкачать
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Министерство образования и науки оссийской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. . Демидова
Каедра теоретической инорматики
В. С. ублев
Элементы теории граов.
Изоморизм, планарность,
маршруты в граах
(индивидуальные
работы ќ 6 и 7 по дисциплине
ѕОсновы дискретной математикиї)
Методические указания
екомендовано
Научно-методическим советом университета
для студентов, обучающихся по
специальности Инормационные технологии
Ярославль 2010
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
УДК 519.2
ББК В174я73
82
екомендовано
едакционно-издательским советом университета
в качестве учебного издания. План 2009/10 года
ецензент
каедра теоретической инорматики Ярославского государственного
университета им. П. . Демидова
ублев, В. С.
Элементы теории граов. Изоморизм,
планарность, маршруты в граах: метод. указания
82
/ В. С. ублев; Яросл. гос. ун-т им. П. . Демидова. Ярославль: ЯрУ, 2010. 84 с.
Методические указания содержат варианты индивидуальных заданий по темам Изоморизм и планарность граов,
Маршруты в граах дисциплины Основы дискретной математики, а также необходимый материал для ее самостоятельного изучения и выполнения индивидуальных заданий.
Для качественного усвоения курса в издании даны подробные определения, примеры, иллюстрации и обоснования.
Предназначены для студентов, обучающихся по специальности 010400.62 Инормационные технологии (дисциплина
Основы дискретной математики, блок ЕН), очной ормы
обучения.
УДК 519.2
ББК В174я73
Ярославский
государственный
университет
им. П. . Демидова,
2010
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
1
Определения граов
Функциональное соответствие и его частный случай взаимно-
однозначное соответствие наиболее простые бинарные отношения
множеств. В общем случае, когда соответствие не является ункциональным и элемент может иметь много образов, наглядное его представление гра. Представление отношений в виде граов использовал еще Леонард Эйлер, но как наука теория граов возникла в
30-е годы прошлого века с выходом монограии Кенига Теория граов. В оссии первой книгой, посвященной этой теории, является
книга Клода Бержа Теория граов и ее приложения в переводе проессора А.А. Зыкова (патриарха граистов на пространстве бывшего
ССС), изданная в начале 1960-х годов. Она проста для чтения, достаточное количество экземпляров этой книги имеется в библиотеке
ЯрУ. С тех пор было издано очень много учебников и монограий
по теории граов как зарубежных, так и отечественных авторов.
Конечный гра (в последующем термин конечный всегда будет
подразумеваться)
G определяется как пара конечных множеств, одно
из которых называется множеством вершин граа (каждый элемент
вершина граа), а другое определяется как множество пар вершин
(первого множества) и называется множеством ребер (каждый элемент ребро, соединяющее 2 вершины граа). Таким образом, в обозначении
G(X; U ) X множество вершин, а U
множество ребер (пар
вершин). Например,
G(fx1; x2; x3; x4g; ffx1; x2g; fx1; x3g; fx3; x4gg)
гра, содержащий 4 вершины
x1; x2; x3; x4 и 3 ребра.
еометрически вершины граа изображаются точками, а ребра линиями, соединяющими эти вершины-точки. При этом неважно, где
располагаются вершины и пересекаются или не пересекаются ребра.
На рис. 1 приведены 3 изображения вышеприведенного граа
xe 1
xe 3
xe 1
xe 3
e
e
e
e
x2
x4
x4
xe 2
x2
ис. 1
3
xe 1
xe 3
G.
xe 4
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Если в определении множества ребер
U
допустить пары одинако-
вых элементов (вершин), то каждая такая пара изображается линией,
идущей из вершины в ту же самую вершину, а потому называется петлей, а соответствующий гра граом с петлями. Примером служит
следующий гра
G(fx1; x2; x3g; ffx1; x2g; fx2; x2gg);
содержащий 3 вершины и 2 ребра, одно из которых петля (см. рис. 2).
xe 1 x2e
xe 3
ис. 2
Если в определении множества
U
ребер допустить повторяющиеся
элементы (ребра), то получим мультигра. Например, гра
G(fy1; y2; y3g; ffy1; y2g; fy2; y3g; fy3; y2g; fy2; y3gg)
содержит 3 ребра, соединяющих вершины
ye 1
y2e
y2
и
y3
(см. рис. 3).
ye 3
ис. 3
Чаще всего мы будем рассматривать граы без петель и повторяющихся ребер, которые называют обыкновенными граами.
Если элементы множества
U
являются упорядоченными парами
вершин, то гра называется ориентированным граом, или орграом,
а элементы множества
U
называются дугами. Например, оргра
G(fy1; y2; y3g; f(y1; y2); (y2; y1); (y2; y3)g)
содержит 3 вершины и 3 дуги, 2 из которых соединяют вершины
y1,
y2 и идут в разных направлениях. В наглядном изображении орграа
дуга это стрелка, указывающая направление от вершины начала
дуги к вершине конца дуги (см. рис. 4).
ye 1
ye 2 - ye 3
I
ис. 4
4
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
xиy
Вершины
шина
x
ребра
fx; yg называются
является концом ребра
(вершина
Вершины
x
x
инцидентна ребру
и
y
концами ребра. Если вер-
u, то говорят, что x и u инцидентны
u, а ребро u инцидентно вершине x).
определяются как смежные, если существует ребро
fx; yg, связывающее эти вершины (инцидентное этим вершинам). Два
ребра
u
и
v
являются смежными, если они инцидентны одной и той
же вершине.
x определяется как число d(x) ребер, инцидентn(G) jX j число вершин граа G(X; U ), а
Степень вершины
ных
x.
Обозначим
m(G) jU j число ребер этого граа.
Занумеруем все вершины граа X = fx1 ; x2 ; : : : ; xn g. Число ребер
и степени вершин связаны следующим соотношением
m=
1
2
n
X
i=1
d(xi);
которое обосновывается следующим образом: если мы просуммируем
степени всех вершин, то мы пересчитаем дважды каждое ребро (один
раз, когда мы учитываем ребро в степени одной из вершин, которой
оно инцидентно, а второй раз, когда мы учитываем ребро в степени
другой вершины, которой оно инцидентно).
В орграе дуга имеет начало (вершина, из которой она выходит) и
конец (вершина, в которую она входит). В соответствии с этим могут
быть дуги, выходящие из вершины, и дуги, входящие в вершину. Поэтому вместо степени вершины в орграе для вершины определяют
полустепень исхода
полустепень захода
d (x) как число дуг, исходящих из вершины, и
d+(x) как число дуг, входящих в вершину. Под-
считать все дуги можно, если просуммировать все полустепени исхода
или же просуммировать все полустепени захода. Из этого следует соотношение:
m=
n
X
i=1
d (xi) =
n
X
i=1
d+(xi):
Еще несколько определений:
Вершина граа, имеющая степень 0, называется изолированной.
Вершина граа, имеющая степень 1, называется висячей.
ра называется полным, если любые 2 его вершины соединены
ребром, и пустым, если все его вершины изолированы (множество ре5
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
бер пусто). Полный гра, имеющий
n
вершин, обозначается как
На рис. 5 приведено изображение граа
x2 e
x3 e
K5.
Kn.
ex4
x1 e
ex5
ис. 5
ра
G(X; U ) называется двудольным, если множество X
его вер-
шин может быть разбито на 2 таких непересекающихся подмножества
X1 [ X2; X1 \ X2 = ;) доли граа, что смежными могут быть
только вершины разных долей: fxi ; xj g 2 U ^ xi 2 X1 ! xj 2 X2 .
На рис. 6 приведен пример такого граа с долями: X1 = fx1 ; x2 ; x3g,
X2 = fx4; x5g.
x1 e
ex4
x2 e
ex5
x3 e
X
(
=
ис. 6
Полный двудольный гра это двудольный гра, у которого лю-
бые 2 вершины, принадлежащие разным долям, смежны. Полный дву-
n вершин в первой доле и m вершин во второй доле (и потому n m ребер), обозначается как Kn;m . Например,
если в гра, изображенный на рис. 6, добавить ребро fx3 ; x4g, то мы
получим полный двудольный гра K3;2 .
Обобщением двудольного граа является n-дольный гра. Он определяется разбиением множества вершин на n подмножеств-долей:
дольный гра, имеющий
X
=
n
[
i=1
Xi; Xk \ Xj
=
; k6
(
=
j );
а также смежностью только вершин, принадлежащих соседним долям:
fx; yg 2 U; x 2 Xi
(1
< i < n)
6
! y 2 Xi+1 _ y 2 Xi
1:
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
На рис. 7 изображен 3-дольный гра.
x1 e
xe4
x2 e
ex6
ex7
xe5
ex8
x3 e
ис. 7
2
Изоморизм граов и алгоритмические способы задания граа
Структура граа не изменится, если переименовать его вершины
и ребра: характеристики граа, такие как количество вершин, количество ребер, набор степеней вершин, количество элементарных циклов с заданным числом вершин и другие не зависят от наименования
вершин и ребер. Поэтому граы, отличающиеся только наименованием вершин и ребер, будем называть изоморными. В теории граы
изучаются с точностью до изоморизма. Дадим точное определение
изоморизма граов.
G1(X; U ) и G2(Y; V ) называются изоморными, если между множествами их вершин X и Y можно установить взаимнооднозначное соответствие ', сохраняющее смежность, т. е. такое,
раы
что
8xi; xj 2 X fxi; xj g 2 U $ f' xi ; ' xj g 2 V:
(
)
(
)
Таким образом при изоморизме смежным вершинам граа
ветствуют смежные вершины граа
G1
несмежные вершины из
G2.
G2,
G1 соот-
а несмежным вершинам из
G(X; U ). В силу изоморизма мы можем считать,
что множество вершин X = f1; 2; : : : ; ng. Таким образом, для задания множества вершин достаточно указать их число n. Множество
ребер можно задать списком ребер как списком m пар номеров верПусть дан гра
шин. При этом безразлично, какой из номеров в паре будет первым,
а какой вторым. Но в некоторых случаях удобно, когда номера вершин в паре (ребра) упорядочены и когда сами ребра упорядочены по
7
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
d(k) вершины k необходимо подсчитать количество пар, в которых k находится
на первом или втором месте. Трудоемкость такого алгоритма O (m).
номеру первой в паре вершины. Для определения степени
Например, список
f ; g; f ; g; f ; g; f ; g; f ; g
1 2
1 3
1 4
2 4
3 4
определяет гра с 5 ребрами, где степень вершины 3 равна 2. Если
же каждое ребро определить в списке дважды (один раз, когда одна
из вершин стоит на первом месте, а второй раз, когда другая вершина
стоит на первом месте) и этот список упорядочить по первой вершине,
то тогда для определения степени вершины необходимо подсчитать
количество пар, где эта вершина стоит на первом месте. Трудоемкость
такого алгоритма
O(log m
+ maxi
d(i)).
Для примера, написанного
выше, этот список выглядит следующим образом:
f ; g; f ; g; f ; g; f ; g; f ; g; f ; g; f ; g; f ; g; f ; g; f ; g:
1 2
1 3
1 4
2 1
2 4
3 1
3 4
4 1
4 2
4 3
Для орграа порядок вершин в дуге ориентирует ее и потому определяет порядок в паре. Например, список дуг
; ; ; ; ; ; ; ; ;
(1 2) (1 4) (2 4) (3 1) (4 3)
определяет оргра с пятью дугами, которые получены ориентацией
ребер предыдущего граа.
d+4 = 2; d4
= 1.
В случае неориентированного граа иногда удобно задавать каждое ребро дважды. Например, это упрощает и ускоряет алгоритм определения степени вершины.
G(X; U ) матрица смежности вершин. Она представляет собой матрицу A размерности n n,
элемент aij которой равен 1, если вершины i и j смежны (есть ребро
fi; j g), или 0, если не смежны (нет такого ребра).
Другой удобный способ задания граа
aij
=
; fi; j g 2 U
0; fi; j g 2
= U:
1
Матрица смежности обыкновенного граа без петель имеет нулевую
главную диагональ и является симметрической:
8
aij
=
aji.
В качестве
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
примера приведем матрицу смежности для обыкновенного граа, заданного выше списком ребер:
2
66
4
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
0
3
77
5
Изображение этого граа приведено на рис. 8.
2
e
1
e
e
4
3
e
ис. 8
ра с петлями имеет на диагонали единицы.
Элементы матрицы смежности орграа определяются следующим
образом:
aij
=
8
<
:
; (i; j ) 2 U
1; (j; i) 2 U
0; (i; j ) 2
= U; (j; i) 2= U:
1
Матрица смежности орграа является кососимметрической:
aji = aij :
В качестве примера приведем матрицу смежности орграа, заданного
выше списком дуг:
2
66
4
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
0
3
77
5
На рис. 9 приведено изображение этого граа.
9
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
e
1
R- e
e
I
e
4
3
ис. 9
В случае мультиграа элемент матрицы смежности вершин обыкновенного граа может иметь значение
k, если k
дуг связывают вер-
шины, соответствующие индексам элемента матрицы.
Еще один способ задания граа матрица инцидентности. Элемент
bij (i 2 1; n; j
2
; m)
1
матрицы инцидентности
B
определяется
следующим образом:
bij
=
;
0;
1
i инцидентна ребру j;
вершина i не инцидентна ребру j:
вершина
В каждом столбце матрицы инцидентности имеются ровно 2 единицы,
соответствующие вершинам, которые являются концами ребра. Число
единиц в каждой строке определяет степень соответствующей вершины. В качестве примера приведем матрицу инцидентности для граа,
заданного выше списком ребер:
2
66
4
1
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
1
1
3
77
5
Матрица инцидентности орграа определяется подобным образом.
bij
=
8
<
:
;
1;
0;
1
i исходит дуга j;
в вершину i входит дуга j;
вершина i не инцидентна дуге j:
из вершины
В каждом столбце матрицы инцидентности орграа имеются ровно 1
единица и 1 минус единица, соответствующие вершинам, которые являются выходящим и входящим концами дуги. Число единиц в каждой строке определяет полустепень захода соответствующей вершины,
10
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а число минус единиц в каждой строке полустепень исхода соответствующей вершины. В качестве примера приведем матрицу инцидентности для граа, заданного выше списком дуг:
2
66
4
1
1
0
1
0
1
0
1
0
0
0
0
0
1
1
0
1
1
0
1
3
77
5
Выбор алгоритмического способа задания граа зависит от удобства конкретных алгоритмов работы с граом. Матрица смежности
вершин может являться неэкономным способом, если каждый элемент
задается в памяти компьютера как целое число. Но если такую матрицу определить как массив строк из нулей и единиц (строка бит в
памяти компьютера), то можно не только сэкономить на памяти, но и
получить эективный способ для некоторых операций работы с граом. Так если нужно найти все вершины, каждая из которых смежна
с каждой из вершин заданного множества, то достаточно взять логическое произведение строк соответствующих вершинам множества. В
вышеописанном примере матрицы смежности обыкновенного граа
для получения вершин, смежных с вершинами 1 и 4, после логического умножения первой и четвертой строки матрицы получим строку:
0 1 1 0
;
которая определяет такими вершины 2 и 3.
3
Операции над граами
ассмотрим операции, выделяющие части граа и образующие но-
вые граы по заданным.
ра
G1(X1; U1) называется подграом граа G(X; U ), если
X1 X; U1 U:
Если
G1
6
=
G,
то подгра собственный. Если подгра
G1
граа
является полным (любые 2 его вершины смежны), содержащим
шин, то он называется кликой из
n вершин.
11
G
n вер-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Подгра
G1
граа
G называется остовным, если X1 = X , т. е. он
содержит все вершины граа. Таким образом, остовный подгра образуется из граа удалением некоторых ребер, а любой подгра из
граа, возможно, удалением некоторых вершин (не всех) и инцидентных им ребер, а также иногда удалением еще некоторых ребер. Напри-
G(f1; 2; 3; 4g; ff1; 3g; f1; 4g; f2; 3gg) следующий подгра G1 (f1; 2; 3; 4g; ff1; 3g; f1; 4gg) является остовным подграом, а
подгра G2 (f2; 3; 4g; ff2; 3gg) не является остовным подграом.
ра G(X; U ) называется дополнением граа G(X; U ) (дополнительным граом), если u 2 U $ u 2
= U . Таким образом, в дополнении
мер, для граа
граа смежные вершины не смежны, а несмежные вершины смежны.
Например, для граа пятиугольника
G(f1; 2; 3; 4; 5g; ff1; 2g; f2; 3g; f3; 4g; f4; 5g; f5; 1gg)
дополнением является звезда
G(f1; 2; 3; 4; 5g; ff1; 4g; f4; 2g; f2; 5g; f5; 3g; f3; 1gg);
которая изоморна грау
G, а для граа
P (f1; 2; 3; 4g; ff1; 2g; f2; 3g; f2; 4g; f3; 4gg)
дополнением является гра
P (f1; 2; 3; 4g; ff1; 3g; f1; 4gg);
P.
смежности A
не изоморный грау
Матрица
дополнительного граа получается инвер-
тированием не принадлежащих главной диагонали элементов матри-
цы
A
основного граа, т. е. заменой нулей на единицы и единиц на
нули для всех элементов матрицы кроме диагонали. Так, для граа
пятиугольника матрица смежности вершин:
A=
2
66
66
4
0
1
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
1
0
12
3
77
77 ;
5
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а матрица смежности вершин дополнительного граа звезды:
A=
2
66
66
4
0
0
1
1
0
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
3
77
77 :
5
В тех случаях, когда уже определена матрица смежности граа, для
задания подграа, содержащего все ребра граа, которые инцидентны вершинам подграа, не обязательно задавать его матрицу смежности достаточно задать булев вектор из нулей и единиц, где единицы
определяют вершины подграа. Логическое произведение этой строки
на строки матрицы, соответствующие вершинам подграа, определяют все ребра, инцидентные вершинам подграа.
В некоторых случаях полезными операциями над граами являются объединение граов и прямое произведение граов. Под объеди-
H (Y; V ) понимают гра E (X [ Y; U [ V ).
Прямое произведение граов G(X; U ) H (Y; V ) = E (X Y; W ), где
W = f f(xgi ; ykh); (xgj ; ylh)g j
g g
g
g
h
h
h h
(fx ; x g 2 U ^ y = y ) _ (fy ; y g 2 V ^ x = x )g:
i j
k
l
k l
i
j
нением граов
4
G(X; U )
и
Методика установления изоморизма граов
Следующая лемма просто обосновывается.
Лемма.
раы
G1(X; U )
и
G2(Y; V )
тогда, когда изоморны их дополнения
изоморны тогда и только
G1(X; U ) и G2(Y; V ).
Этой леммой имеет смысл пользоваться в тех случаях, когда количество ребер дополнительного граа меньше количества ребер основного граа.
Из определения изоморизма следует, что для изоморных граов
должно совпадать количество вершин, количество ребер, количество
вершин с одинаковой степенью, количество элементарных циклов с
заданным числом вершин и другие характеристики граов, не зависящие от наименования (или нумерации) вершин. Поэтому если при
попытке установить изоморность граов оказывается, что одна из
таких характеристик различна, то граы не изоморны. Если же од13
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
на или несколько таких характеристик совпадают, то из этого вовсе не
следует изоморность граов: для обоснования изоморности необходимо установить 1-1с, сохраняющее смежность.
В общем случае нет хорошего алгоритма для установления изоморности двух граов, существенно отличного (по сложности) от
перебора
n!
вариантов проверки 1-1с, где
n
число вершин каждо-
го из граов. Однако для граов с небольшим количеством вершин
можно указать некоторую последовательность действий, приводящую
либо к выводу о неизоморности граов, либо ведущую к построению
ункции изоморизма. Мы будем считать, что граы, для которых
исследуется вопрос их изоморности, связны, так как в противном
случае можно исследовать вопрос для каждой пары компонент связности граов.
1. Найти количество вершин
2.
n(Gi) (i
;
= 1 2) и количество ребер
m(Gi) (i = 1; 2) каждого из граов. Если они не совпадают:
n(G1) 6= n(G2) или m(G1) 6= m(G2), то граы не изоморны.
1 1
Найти наборы степеней вершин каждого из граов (n1 ; n2 ; : : : )
i
2 2
и (n1 ; n2 ; : : : ), где nk означает количество вершин степени k i-го
граа. Если эти наборы не совпадают, то граы не изоморны.
3. Если наборы степеней вершин граов совпадают и есть вершины
разных степеней, то делаем попытку построения изоморизма
'
следующим образом:
o
i0, для которой число вершин в наборе минимально: ni0 = mini fni g.
Делаем попытку установления соответствия ' между вершинами множества Xi = fx 2 X j d(x) = i0 g и вершинами
Yi = fy 2 Y j d(y) = i0g. Для этого для каждой вершины
x 2 Xi находим набор степеней вершин, смежных с ней. То же
делаем для каждой вершины y 2 Yi . Если эти наборы мож-
1 . Находим степень
o
2 .
но сопоставить несколькими вариантами, то выбрать один из
них (и положить соответствие между сопоставленными вершинами), а остальные запомнить для последующих выборов,
если принятый выбор окажется неприемлемым. Если наборы нельзя сопоставить, то выбор предыдущего варианта со14
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
поставления (если он есть) оказался неудачным, следует отступить к нему (ликвидировав все варианты выборов после
него) и взять следующий вариант сопоставления. Если такого нет, то снова отступать к предыдущему варианту выбора
сопоставления. Если такого нет, то граы неизоморны.
o
3 . Для каждого из наборов уже сопоставленных вершин найти
вершины, смежные с ними, но не входящие в сопоставление,
установить их относительную смежность и выбрать для сопоставления в каждом наборе те вершины, которые имеют наименьшую относительную смежность. Если таких вариантов
несколько, то выбрать один из них, запомнив остальные для
последующих выборов. Этот пункт выполнять до тех пор,
пока все вершины обоих граов не окажутся сопоставленными (и это сопоставление дает изоморизм граов), либо
пока не будет установлено, что нет вариантов сопоставления.
В последнем случае надо отступить к предыдущему варианту сопоставления (ликвидировав все варианты выборов после
него) и взять следующий вариант сопоставления. Если такого нет, то снова отступать к предыдущему варианту выбора
сопоставления. Если такого нет, то граы неизоморны.
4. Если все вершины имеют одинаковую степень, то можно применить прием попытки установления соответствия между вершинами, входящими в элементарные циклы (цикл, не содержащий
повторяющихся вершин и ребер) одинаковой длины. При этом,
если для одного граа некоторая вершина входит в несколько
циклов, то для другого граа соответствующая в изоморизме
вершина также должна входить в такое же количество циклов
такой же длины. Поэтому вместо степеней вершины выбирается
в качестве показателя набор количеств циклов с определенной
длиной, содержащих эту вершину, и используется алгоритм, подобный алгоритму предыдущего пункта, но также с учетом смежности сопоставляемых вершин.
Этот прием хорошо работает, когда граы не являются изоморными. Например, в одном грае есть цикл определенной длины,
которого нет в другом грае. Если же это не так, то требуется
15
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
очень большое внимание при подсчете циклов. Неаккуратность
приводит к ошибочному заключению.
В случае предполагаемой изоморности при одинаковости степеней всех вершин каждого граа можно применить следующий прием. Определим для каждого ребра набор степеней вершин, смежных с обоими вершинами ребра, и будем сопоставлять
те ребра обоих граов, для которых такие наборы одинаковы.
При невозможности такого сопоставления для каких-либо ребер
граы не изоморны. При неоднозначности сопоставления выбираем один из вариантов, запоминая остальные для последующих выборов. В сопоставляемых ребрах также выбирается один
из двух вариантов сопоставления вершин, инцидентных ребрам
(второй вариант запоминается). Прием повторяется, но при этом
определяются наборы степеней вершин, смежных с обоими концами ребер, не вошедших уже в сопоставление. Либо такое повторение приводит к установлению изоморизма, либо при неудаче
в сопоставлении следует отступить к предыдущему выбору (ликвидировав все варианты выборов после него) и взять следующий
вариант сопоставления. Если такого нет, то снова отступать к
предыдущему варианту выбора сопоставления. Если такого нет,
то граы неизоморны.
5
Примеры задач на изоморизм граов с их решениями
Пример 1. ра
G1(X; U ) задан матрицей смежности вершин
2
66
66
66
66
66
64
010
001
10
101
001
00
010
110
00
001
001
01
001
000
11
110
100
00
100
010
01
000
110
10
16
3
77
77
77
77 ;
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а гра
G2(Y; V ) задан списком ребер: ({1,2}, {1,4}, {1,5}, {2,3}, {2,6},
{3,4}, {3,7}, {4,8}, {5,6}, {5,8}, {6,7}, {7,8}).
еализации (изображения) граов приведены на рис. 10 и 11.
7
8
e
e
HHH
1
e
2
e
3
e
HHH
e6
e4
HH e
5
ис. 10 (гра
G1)
ис. 11 (гра
G2)
Оба граа имеют по 8 вершин и все вершины степени 3. Поэтому
число ребер у них одинаковое, и алгоритм сопоставления по степеням
может иметь полный перебор сопоставления вершин, если граы не
изоморны. Попробуем использовать прием сопоставления по длине
элементарных циклов этих граов. Наглядно видно на рисунках, что
G1 имеет 2 элементарных цикла длины 3, а G2 не имеет таких циклов.
Поэтому граы G1 и G2 не изоморны.
Пример 2. ра G1 (X; U ) задан следующей матрицей смежности
17
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
64
вершин
а гра
010
001
10
101
001
00
010
110
00
001
001
01
001
001
11
110
110
00
100
010
01
000
110
10
3
77
77
77
77 ;
77
75
G2(Y; V ) задан списком ребер:
({1,4}, {1,5}, {1,7} {1,8}, {2,4}, {2,5}, {2,8}, {3,5}, {3,6}, {3,8}, {4,7},
{6,7}, {6,8}).
Оба граа имеют по 8 вершин, 2 из которых имеют степень 4,
а остальные 6 степень 3. При попытке установить изоморность
граов есть 2 варианта отождествления вершин степени 4 граов
и
G1
G2: {51, 68} и {58, 61}. Выберем первый вариант ' ={51, 68},
а второй {58, 61} оставим в памяти для последующего выбора,
если первый вариант будет отвергнут.
Вершина 5 граа
G1 кроме уже выбранной в соответствие вершины
6 смежна с вершинами 3, 7, 8, из которых 7 и 8 смежны между собой,
а соответствующая ей вершина 1 граа
G2
кроме уже выбранной в
соответствие вершины 8 смежна с вершинами 4, 5, 7, из которых 4 и
7 смежны между собой. Поэтому продолжением является включение
в строящийся изоморизм
' соответствия 35, как единственных вер-
шин соответствующих граов, которые смежны с уже включенной в
' парой вершин 51 и не смежны с другими вершинами, смежными с
этой парой: '={51, 68, 35}.
Вершина 6 граа G1 кроме уже выбранной в соответствие вершины
5 смежна с вершинами 1, 2, 4, из которых 1 и 2 смежны между собой,
а соответствующая ей вершина 8 граа
G2
кроме уже выбранной в
соответствие вершины 1 смежна с вершинами 2, 3, 6, из которых 3 и
6 смежны между собой. Поэтому продолжением является включение
в строящийся изоморизм
' соответствия 42, как единственных вер-
шин соответствующих граов, которые смежны с уже включенной в
' парой вершин 68 и не смежны с другими вершинами, смежными с
этой парой: '={51, 68, 35, 42}.
18
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Среди еще не рассмотренных вершин, смежных с вершиной 5 гра-
G1,
а
вершины 7 и 8, а среди еще не рассмотренных вершин граа
G2, смежных с соответствующей вершиной 1, вершины 4 и 7, которые
также смежны между собой. Поэтому для дальнейшего есть два варианта выбора соответствия вершин: {74, 87} и {77, 84}. Выберем
первый вариант
'={51, 68, 35, 42, 74, 87}, а второй {51, 68,
35, 42, 77, 84} оставим в памяти для последующего выбора, если
первый вариант этого выбора будет отвергнут.
Среди еще не рассмотренных вершин граа
G1
вершины 1 и 2,
смежные с вершиной 6 и смежные между собой. Им соответствуют
в грае
G2
вершины 3 и 6, смежные соответствующей вершине 8 и
смежные между собой. Есть два варианта выбора соответствия вершин граов: {13, 26} и {16, 23}. Но выбор первого варианта ведет
G1 смежна с вершиной 7 этого граа, а соответствующая ей вершина 3 граа G2 не смежна с вершиной
к противоречию: вершина 1 граа
4 этого граа, которая выбрана как соответствующая вершине 7 граа
G1. Поэтому этот вариант выбора не подходит, перейдем к выбору
следующего второго варианта {16, 23}. Но и в этом варианте выбора
есть противоречие: вершина 1 граа
G1
смежна с вершиной 7 этого
граа, а соответствующая ей вершина 6 граа
G2
не смежна с вер-
шиной 4 этого граа, которая выбрана как соответствующая вершине
7 граа
G1. Так как вариантов выбора в данной точке рассмотрения
больше нет, то следует отступить к предыдущей точке рассмотрения
и вместо варианта {74, 87} выбрать следующий вариант {77, 84}.
При этом
'={51, 68, 35, 42, 77, 84}.
Теперь снова нужно рассмотреть 2 варианта соответствия оставшихся вершин граов: {13, 26} и {16, 23}. При выборе первого
варианта опять возникает противоречие: вершина 1 граа
G1 смежна
с вершиной 7 этого граа, а соответствующая ей вершина 3 граа
G2
не смежна с вершиной 7 этого граа, которая выбрана как соот-
ветствующая вершине 7 граа
G1.
Поэтому перейдем к следующему
варианту выбора соответствия вершин: {16, 23}.
На этот раз противоречия не возникает: вершина 1 граа
G1 смеж-
на с вершиной 7 этого граа, а соответствующая ей вершина 6 граа
G2
также смежна с вершиной 7 этого граа, которая выбрана как
соответствующая вершине 7 граа
19
G1. Аналогично вершина 2 граа
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
G1
смежна с вершинами 1, 3, 6 этого граа, а соответствующая ей
вершина 3 граа
G2
также смежна с вершинами 5, 6, 8 этого граа,
которые выбраны как соответствующие вершинам 3, 1, 6 граа
G1.
Таким образом, мы получаем окончательный вариант соответствия:
'={51, 68, 35, 42, 77, 84, 16, 23}. Взаимно-однозначное соответствие ' = y (x), где x вершина граа G1 , а y соответствующая
ей вершина граа G2 , определяется следующей таблицей:
x
y
1
2
3
4
5
6
7
8
6
3
5
2
1
8
7
4
' является изоморизмом дается следующей таблицей
соответствия ребер граов G1 и G2 :
Проверка, что
xi; xj
yk ; yl
;
6; 3
1 2
;
6; 8
1 6
;
6; 7
1 7
;
3; 5
2 3
;
3; 8
2 6
;
5; 2
3 4
;
5; 1
;
2; 8
3 5
4 6
;
2; 4
4 8
;
1; 8
5 6
;
1; 7
5 7
;
1; 4
5 8
;
7; 4
7 8
Отметим, что мы не использовали при построении изоморизма
второй вариант соответствия в первой точке рассмотрения. Можно
проверить, что в этом случае получается другой вариант изоморизма граов.
Пример 3. ра
G1(X; U )
возьмем из примера 1, а гра
G2(Y; V )
зададим списком ребер:
({1,3}, {1,4}, {1,6}, {2,3}, {2,5}, {2,7}, {3,8}, {4,6}, {4,7}, {5.7}, {5,8},
{6,8}).
ис. 12 (гра
G2)
Оба граа имеют по 8 вершин и все вершины степени 3. Поэтому
число ребер у них одинаковое, и алгоритм сопоставления по степеням
20
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
будет иметь полный перебор сопоставления вершин. Попробуем использовать прием сопоставления по длине элементарных циклов этих
G1 изображен на рис. 10, а изображение граа G2 приведено на рис. 12. ра G1 содержит элементарные циклы
граов. ра
2 цикла длины 3: (1, 2, 6, 1) и (5, 7, 8, 5);
2 цикла длины 4: (2, 3, 4, 6, 2) и (3, 4, 8, 5, 3);
4 цикла длины 5: (1, 2, 3, 5, 7, 1), (1, 2, 3, 4, 6, 1), (3, 4, 8, 7, 5, 3) и
(1, 6, 4, 8, 7, 1);
а также циклы длины большей 5.
ра
G2
содержит элементарные циклы
2 цикла длины 3: (1, 4, 6, 1) и (2, 5, 7, 2);
2 цикла длины 4: (1, 3, 8, 6, 1) и (2, 3, 8, 5, 2);
4 цикла длины 5: (4, 6, 8, 5, 7, 4), (1, 3, 8, 6, 4, 1), (2, 3, 8, 5, 7, 2) и
(1, 3, 2, 7, 4, 1);
а также циклы длины большей 5.
Так как число элементарных циклов с одной длиной, похоже, одинаково, попробуем установить изоморизм граов. Для этого определим
для каждой вершины длину элементарных циклов (до 5), в которые
входит эта вершина.
Для граа
G1
1 3, 5, 5, 5 (вершина 1 входит в 1 цикл длины 3 и 3 цикла длины
5);
2 3, 4, 5, 5;
3 4, 4, 5, 5, 5;
4 4, 4, 5, 5, 5;
5 3, 4, 5, 5;
6 3, 4, 5, 5, 5;
7 3, 5, 5, 5;
8 3, 4, 5, 5.
Для граа
G2
1 3, 4, 5, 5, 5;
2 3, 4, 5, 5;
3 4, 4, 5, 5, 5;
4 3, 5, 5, 5;
5 3, 4, 5, 5;
6 3, 4, 5, 5;
21
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
7 3, 5, 5, 5;
8 4, 4, 5, 5, 5.
Набор длин элементарных циклов (3, 4, 5, 5, 5) имеет только вер-
G1 и вершина 1 граа G2. Поэтому устанавливаем единственно возможное соответствие этих вершин граа: '={(61)}.
Смежными для вершины 6 в G1 являются вершины (с набором
шина 6 граа
циклов, в которые входят): 1 (3, 5, 5, 5), 2 (3, 4, 5, 5) и 4 (4, 4, 5, 5, 5).
Смежными для соответствующей вершины 1 в
G2
вершины: 3 (4, 4,
5, 5, 5), 4 (3, 5, 5, 5) и 6 (3, 4, 5, 5). Одинаковые наборы циклов имеют
а также 4 из
G1
Смежными для вошедших в соответствие вершины 2 и 4 из
G1
пары вершин: 1 из
и 3 из
G1
и 4 из
G2,
2 из
G1
и 6 из
G2,
G2,. Добавляем эти пары в строящееся соответствие: '={(61),
(14), (26), (43)}.
является вершина 3, еще не вошедшая в соответствие, а смежными
для соответствующих им вершинам 6 и 3 из
G2
является вершина 8.
Поэтому добавляем пару (38) в строящееся соответствие:
'={(61),
(14), (26), (43), (38)}.
Далее, вершина 1 из
G1, уже вошедшая в соответствие, среди вер-
шин, не вошедших в соответствие, смежна только с вершиной 7, а
соответствующая ей вершина 4 из
G2
среди вершин, не вошедших в
соответствие, смежна только с вершиной 7. Поэтому добавляем пару
'={(61), (14), (26), (43), (38), (77)}.
Затем смежной вершине 3 из G1 , уже вошедшей
(77):
в соответствие,
среди вершин, не вошедших в соответствие, является только вершина 5, а для соответствующей ей вершины 8 из
G2
среди вершин, не
вошедших в соответствие, смежной является только вершина 5. Поэтому добавляем пару (55):
'={(61), (14), (26), (43), (38), (77),
(55)}.
Остается еще не вошедшая в соответствие вершина 8 из
ная с вершинами 4, 5 и 7, а в
G2
G1, смеж-
вершина 2, которая смежна с соот-
ветствующими вершинами 3, 5 и 7. Добавляем эту пару (82) в соот-
'={(61), (14), (26), (43), (38), (77), (55), (82)}.
Взаимно-однозначное соответствие ' = y (x), где x вершина граа G1 , а y соответствующая ей вершина граа G2 , определяется
ветствие:
следующей таблицей:
22
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
x
y
1
2
3
4
5
6
7
8
4
6
8
3
5
1
7
2
' является изоморизмом, дается следующей таблицей
соответствия ребер граов G1 и G2 :
Проверка, что
fxi; xj g
fyk ; ylg
6
;
4; 6
1 2
;
4; 1
1 6
;
4; 7
1 7
;
6; 8
2 3
;
6; 1
2 6
;
8; 3
3 4
;
8; 5
3 5
;
3; 1
;
3; 2
4 6
4 8
;
5; 7
5 7
;
5; 2
5 8
;
7; 2
7 8
Планарность граа
ра называется планарным (плоским), если он допускает реализацию на плоскости без пересечения ребер. Например, полные (содер-
K3 из 3 вершин и K4 из 4 вершин
являются плоскими (см. рис. 13), а K5 плоским не является.
жащие все возможные ребра) граы
ис. 13
ис. 14
Последнее обосновывается тем, что его клика 4 вершин
x1; x2; x3; x4
(полный подгра, содержащий эти вершины) при реализации на плоскости без пересечения ребер разбивает плоскость на 4 области (см.
рис. 14):
x1; x2; x3; x1)
(вне ее лежит вер-
x1; x3; x4; x1)
(вне ее лежит вер-
1) ограниченную ребрами цикла (
шина
x4);
2) ограниченную ребрами цикла (
шина
x2);
23
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
x1; x2; x4; x1)
3) ограниченную ребрами цикла (
шина
x3);
(вне ее лежит вер-
x2; x3; x4; x2) (внутри цикла лежит вершина
4) лежащую вне цикла (
x1).
Теперь в какую бы из областей мы не поместили вершину
то из первых 4 вершин
а потому ребро
xi ( i
2
;
x5, какая-
1 4) будет лежать вне этой области,
fx5; xig пересечет какое-либо из ребер, лежащих на
границе области. Таким образом гра
K5
не является планарным.
Другим важным примером непланарного подграа является полный двудольный гра
K3;3 каждая доля граа имеет по 3 вершины
и между любыми вершинами разных долей есть ребро (см. рис. 15).
Обоснование этого акта проводится подобным образом его подгра, содержащий все 3 вершины
x4; x5
x1; x2; x3
первой доли и 2 вершины
второй доли, а также все ребра, соединяющие любые вершины
разных долей, разбивает плоскость на 3 области (см. рис. 16):
x1; x5; x2; x4; x1) (вне ее лежит вер-
1) ограниченную ребрами цикла (
шина
x3);
x2; x5; x3; x4; x2) (вне ее лежит вер-
2) ограниченную ребрами цикла (
шина
x1);
x1; x5; x3; x4; x1)
3) лежащую вне цикла (
шина
x2).
ис. 15
(внутри цикла лежит вер-
ис. 16
24
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Теперь в какую бы из областей мы не поместили вершину
то из первых 3 вершин
а потому ребро
xi (i
2
;
x6, какая-
1 3) будет лежать вне этой области,
fx6; xig пересечет какое-либо из ребер, лежащих на
границе области. Таким образом гра
K3;3
не является планарным.
Если гра содержит в качестве своей части непланарный подгра,
то он также является непланарным.
Введем операцию подразбиения ребра
fxi; xj g 2 U
произвольного
GfX; U g: к n = jX j вершинам граа добавляется (n + 1)-я вершина xn+1 , и это ребро заменяется на 2 ребра: fxi ; xn+1g и fxn+1; xj g.
граа
Совершенно ясно, что операция подразбиения ребра не меняет свойство планарности (непланарности) граа.
Два граа называются гомеоморными, если при помощи операций подразбиения ребра их можно сделать изоморными. Поэтому
если гра содержит в качестве своей части подгра, гомеоморный
K5 или K3;3, то он не является планарным. Оказывается, это условие
является не только необходимым, но и достаточным, что устанавливает теорема Понтрягина-Куратовского.
Теорема ПонтрягинаКуратовского. Для того чтобы гра был
планарен, необходимо и достаточно, чтобы он в качестве своих частей не содержал бы подграов, гомеоморных
K5
и
K3;3.
На этой теореме основан алгоритм проверки планарности граа.
Ввиду его сложности мы приведем методику проверки планарности
для небольших граов.
1. Попытаться реализовать гра на плоскости без пересечения ребер. Если это не удается сразу, то после некоторого числа попыток
перенесения расположения вершин с целью уменьшить число пересечения ребер это, возможно, удастся (если гра планарный).
2. Найти число вершин, степень которых не меньше 4. Если таких
вершин меньше 5, то подграа, гомеоморного
K5, нет.
3. Если число вершин со степенью не меньше 4 больше 4, то попытаться найти подгра, гомеоморный
K5:
(a) Если среди вершин со степенью не меньше 4 есть 5 вершин,
попарно связных между собой, то подгра, изоморный
найден и гра непланарен.
25
K5,
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
(b) Если этого нет, то следует удалить висячие вершины (степени
1), а также вершины степени 2 операцией, обратной операции
подразбиения ребра (замена двух ребер, инцидентных такой
вершине, на одно ребро, связывающее смежные с ней вершины).
() Если после этого шага нет 5 вершин степени 4 попарно связных между собой, то следует рассмотреть вершины степени
3. Удалением одного из ребер каждой такой вершины (здесь
возможен перебор удаляемых ребер, при котором порядок перебора зависит от граа) следует добиться получения подграа, гомеоморного
K5, что устанавливает непланарность
граа.
(d) Если выполнение предыдущего пункта не дало результата, то
следует перейти к следующему пункту поиску подграа,
гомеоморного
K3;3.
4. Найти число вершин со степенью не меньше 3. Если таких вершин
меньше 6, то подграа, гомеоморного
гомеоморный
K3;3, нет. Если подгра,
K5, также не найден, то необходимо снова попы-
таться реализовать гра на плоскости без пересечения ребер.
5. Если число вершин со степенью не меньше 3 больше 5, то следует
попытаться найти подгра, гомеоморный
K3;3:
(a) Если среди вершин со степенью не меньше 3 есть 2 набора
по 3 вершины таких, что каждая вершина из первого набора
смежна 3 вершинам из второго набора, то подгра, изоморный
K3;3, найден и гра непланарен.
(b) Если этого нет, то следует удалить висячие вершины (степени
1), а также вершины степени 2 операцией, обратной операции
подразбиения ребра (замена двух ребер инцидентных такой
вершине на одно ребро, связывающее смежные с ней вершины).
() Если после этого подгра, изоморный
K3;3,
не находится,
то следует по очереди удалять (здесь возможен перебор удаляемых ребер, при котором порядок перебора зависит от гра-
26
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а) только одно из ребер вершин степени 3 до тех пор, пока
подгра, изоморный
K3;3, не будет найден.
(d) Если последние действия не дали результата, то следует снова попытаться реализовать гра на плоскости без пересечения ребер.
7
Примеры задач на планарность граа с их решениями
В примерах мы будем вершины отмечать только их номером (без
буквы), а ребра парой номеров в игурных скобках.
2
66
66
66
66
66
64
Пример 4.
010
001
10
101
001
00
010
110
00
001
001
01
001
000
11
110
100
00
100
010
01
000
110
10
3
77
77
77
77
77
75
Анализ матрицы смежности вершин устанавливает, что все вершины
имеют степень 3. Попытка реализации граа на плоскости без пересечения ребер (см. рис. 17) удачна гра планарен.
ис. 17
ис. 18
27
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Пример 5.
2
66
66
66
66
66
64
010
001
10
101
001
00
010
110
00
001
001
01
001
001
11
110
110
00
100
010
01
000
110
10
3
77
77
77
77
77
75
Этот гра отличается от предыдущего добавлением ребра {5, 6} (на
рис. 17 обозначено пунктиром). Однако теперь получается пересечение ребер {3, 4} и {5, 6}. От пересечения ребер не удается избавиться
перемещением вершин 6 и 4 в область цикла (1, 2, 3, 7, 5, 1), так как
тогда ребро {8, 4} начинает пересекаться с ребром {1, 7} или {5, 7}.
Попытаемся установить непланарность граа.
Имеется 2 вершины степени 4 (5 и 6) и 6 вершин степени 3. Так как
;
после добавления ребра (5 6) не удается реализовать гра на плоскости, то следует искать подгра, гомеоморный
K3;3, и добавленное
ребро должно быть между вершинами разных долей.
Вершина 5 смежна с вершинами 3, 6, 7, 8, причем из этих 4 вершин
только вершины 7 и 8 смежны между собой. Поэтому, по-видимому, 2
из вершин 3, 7, 8 принадлежат одной доле вместе с вершиной 6, и так
как 7 и 8 смежны между собой, то это либо 3 и 7, либо 3 и 8.
Исследуем теперь связь остальных вершин 1, 2, 4, 5 с вершинами
3, 6, 7, 8. Вершина 4 смежна вершинам 3, 6, 8. Вершина 1 смежна
вершинам 2, 6, 7. Вершина 2 смежна вершинам 1, 3, 6. Вершина 5
смежна вершинам 3, 6, 7, 8.
Анализ этих связей показывает, что вершинам 3, 6, 8 смежны вершины 4 и 5. Вершина 1, смежная вершине 6, связана с вершиной 8
через вершину 7 и с вершиной 3 через вершину 2. Поэтому если удалить ребра (5, 7) и (2, 6), то мы получим подгра, гомеоморный
(см. рис. 18), что и доказывает непланарность граа.
28
K3;3
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
8
Индивидуальное задание 6
8.1 Общее задание
1. Определить, является ли гра, заданный матрицей смежности
вершин, планарным. В случае планарности построить реализацию граа на плоскости без пересечения ребер. В случае непланарности найти
часть граа (указав удаляемые при этом вершины или ребра), которая является гомеоморной
K5
или
K3;3.
2. Определить, являются ли изомоными 2 граа, один из которых
взят из задачи 1, а второй задан списком ребер. В случае изоморности граов построить изоморизм взаимно-однозначное соответствие вершин первого и второго граов, сохраняющее смежность вершин.
8.2 Варианты индивидуального задания 6
Задача 1
1.
2
66
66
66
66
66
66
64
011
001
010
101
100
001
110
001
101
010
010
011
000
101
010
101
010
100
001
001
001
100
110
000
011
100
100
29
3
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2.
3.
4.
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
66
64
010
011
000
100
000
111
000
101
001
001
000
111
100
000
100
101
000
010
010
110
010
010
101
100
011
100
000
3
77
77
77
77
77
77
75
000
001
1100
000
001
1100
000
101
0011
001
000
0011
000
000
0111
111
000
0000
110
000
0100
110
010
1000
001
110
0000
001
110
0000
2
66
66
66
66
66
64
010
011
01
101
001
11
010
100
11
001
011
10
100
101
11
110
110
00
011
110
00
111
010
00
30
3
77
77
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
5.
6.
7.
8.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
010
011
01
101
000
11
010
100
11
001
011
10
100
101
10
100
110
01
011
110
00
111
001
00
000
011
10
000
001
11
000
010
11
000
001
11
101
001
00
110
110
00
111
100
00
011
100
00
010
001
11
100
101
01
000
011
10
010
010
10
001
100
01
111
000
01
101
100
00
110
011
00
001
110
01
000
110
11
100
001
11
110
010
10
110
101
00
001
010
11
011
101
00
111
001
00
31
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
9.
10.
11.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
000
111
00
001
001
11
010
110
11
101
001
01
101
001
10
110
110
01
011
010
00
011
101
00
000
001
11
000
001
11
000
011
01
000
011
01
001
100
10
111
100
00
110
010
00
111
100
00
000
111
01
000
100
11
000
101
01
111
000
10
100
001
10
101
010
10
010
111
00
111
000
00
32
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
12.
13.
14.
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
011
011
000
100
101
010
100
000
110
010
010
001
100
100
011
110
000
101
001
001
010
011
010
100
000
111
000
010
000
111
101
000
001
010
110
001
001
010
101
001
101
010
000
010
110
100
101
001
100
011
000
111
100
100
011
101
000
100
010
001
100
101
100
101
000
011
010
001
100
101
010
010
001
010
000
000
101
001
010
100
010
33
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
15.
16.
17.
2
66
66
66
66
66
66
66
64
000
100
1011
001
011
0100
010
001
0001
100
010
0010
010
100
1000
011
000
0100
100
010
0010
010
001
0001
100
100
1000
101
000
0100
2
66
66
66
66
66
64
2
66
66
66
66
66
64
001
111
01
000
110
11
100
011
10
110
001
10
111
000
01
101
100
10
011
101
01
110
010
10
001
011
10
001
110
01
110
001
01
010
010
11
110
100
10
101
000
11
100
111
00
011
101
00
34
3
77
77
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
18.
19.
20.
21.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
011
001
10
100
010
01
100
010
01
000
001
11
011
000
10
100
100
01
100
110
00
011
101
00
001
100
01
001
101
10
110
010
00
110
001
10
001
000
11
010
100
11
010
111
00
100
011
00
000
111
10
001
011
01
010
111
00
101
000
11
111
000
10
111
000
01
100
110
01
010
101
10
001
101
11
000
110
10
100
011
01
110
010
01
011
101
10
101
010
10
110
011
00
101
100
00
35
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
22.
23.
24.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
66
64
001
100
01
000
100
11
100
010
10
110
011
00
001
100
01
000
100
11
011
001
00
110
011
00
010
111
00
101
001
10
010
000
11
100
001
11
100
000
11
110
100
00
011
110
00
001
110
00
000
011
100
001
101
100
010
000
011
010
010
110
100
101
000
110
010
001
110
100
001
001
100
001
001
001
110
36
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
25.
26.
27.
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
66
64
001
001
110
000
101
100
100
110
100
011
000
101
001
000
011
110
000
110
111
101
000
100
011
001
000
110
010
010
000
111
100
010
011
000
011
010
000
010
101
011
100
000
001
000
011
100
100
000
111
001
000
110
101
000
001
010
0010
000
100
0101
100
011
0010
010
001
0001
101
000
1000
001
100
0100
000
010
0011
010
001
0001
101
000
1000
010
100
1100
37
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
28.
29.
30.
31.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
001
111
00
000
011
11
100
110
10
101
001
01
111
000
11
110
100
11
011
011
00
010
111
00
000
111
10
001
101
01
010
010
11
110
011
00
101
100
10
110
100
01
101
010
01
011
001
10
001
011
10
000
110
01
100
110
00
011
001
10
111
000
00
100
100
01
100
100
01
010
001
10
001
001
11
000
110
10
100
011
10
010
001
01
011
000
01
101
100
10
111
001
00
100
110
00
38
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
32.
33.
34.
35.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
001
110
01
000
111
10
100
001
11
110
000
11
110
001
10
011
010
01
011
110
00
101
101
00
001
100
11
000
111
01
100
001
01
110
011
10
010
100
11
011
100
01
100
110
00
111
011
00
001
000
11
000
101
10
100
111
00
011
000
01
001
000
11
011
000
01
110
010
00
100
111
00
010
010
11
101
100
01
010
011
00
010
011
10
101
100
10
001
100
01
100
110
00
110
001
00
39
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
36.
37.
38.
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
001
011
010
000
001
011
100
000
111
000
011
110
100
100
100
110
100
001
001
110
000
111
100
000
011
001
000
001
100
100
000
100
111
100
001
101
110
010
100
000
101
010
001
010
011
111
100
001
010
011
000
011
001
100
001
100
010
001
001
101
110
001
010
100
011
000
000
100
101
011
100
001
010
010
000
101
000
001
010
011
010
40
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
39.
40.
41.
2
66
66
66
66
66
66
66
64
010
001
0010
101
000
0101
010
010
0100
000
001
1010
001
000
1001
100
100
1000
000
111
0010
011
000
0001
100
100
1000
010
010
0100
2
66
66
66
66
66
64
2
66
66
66
66
66
64
001
111
10
000
111
11
100
010
11
110
001
10
111
000
01
110
100
01
111
100
00
011
011
00
001
011
01
000
110
11
100
011
10
010
001
11
111
000
10
101
100
01
011
110
00
110
101
00
41
3
77
77
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
42.
43.
44.
45.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
64
001
000
11
000
101
10
100
111
00
011
000
10
001
000
11
011
000
01
110
110
00
100
011
00
001
001
01
000
110
11
100
010
10
010
011
01
011
100
01
100
100
10
011
001
00
110
110
00
001
010
11
000
101
11
100
011
10
010
011
10
101
100
01
011
100
01
111
100
00
110
011
00
001
111
00
000
011
11
100
011
10
100
011
01
111
100
10
111
100
01
011
010
00
010
101
00
42
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
46.
47.
48.
2
66
66
66
66
66
64
2
66
66
66
66
66
64
2
66
66
66
66
66
66
64
001
111
00
001
001
01
110
000
10
100
000
11
100
000
11
110
000
10
001
111
00
010
110
00
000
011
01
001
111
00
010
001
10
010
000
11
110
000
11
111
000
01
001
110
00
100
111
00
001
100
100
000
110
011
100
001
011
110
001
100
010
001
010
001
110
001
100
100
001
011
010
000
011
001
100
43
3
77
77
77
77
77
75
3
77
77
77
77
77
75
3
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
49.
50.
51.
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
64
2
66
66
66
66
66
66
66
64
000
101
101
001
000
011
010
110
010
101
000
100
001
001
110
100
010
011
100
110
000
011
011
001
110
001
010
000
111
100
000
000
111
000
110
000
101
001
001
101
000
010
100
100
011
110
000
001
010
011
000
010
101
100
010
100
1100
100
110
0000
000
011
0011
110
000
0100
011
000
0100
001
000
0011
100
000
0011
100
110
0000
001
001
1000
001
001
1000
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
75
3
77
77
77
77
77
77
77
75
Задача 2
1. {1,2}, {1,7}, {1,8}, {1,9}, {2,3}, {2,9}, {3,4}, {3,5}, {3,9}, {4,5},
{4,7}, {4,9}, {5,6}, {5,8}, {6,7}, {6,8}, {7,9}
44
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2. {1,2}, {1,3}, {1,4}, {1,6}, {2,5}, {2,9}, {3,4}, {3,6}, {3,7}, {4,8},
{4,9}, {5,6}, {5,7}, {6,8}, {8,9}
3. {1,4}, {1,7}, {1,9}, {1,10}, {2,3}, {2,5}, {2,6}, {2,8}, {3,6}, {3,10},
{4,5}, {4,9}, {5,7}, {6,8}, {7,9}, {8,10}
4. {1,3}, {1,4}, {1,5}, {1,6}, {1,8}, {2,4}, {2,5}, {2,7}, {2,8}, {3,5},
{3,6}, {3,7}, {4,6}, {4,7}, {5,8}, {6,7}, {7,8}
5. {1,4}, {1,5}, {1,6}, {1,7}, {2,3}, {2,5}, {2,6}, {2,8}, {3,4}, {3,5},
{3,6}, {4,7}, {4,8}, {5,7}, {6,8}, {7,8}
6. {1,3}, {1,4}, {1,8}, {2,4}, {2,7}, {2,8}, {3,5}, {3,7}, {4,5}, {4,6},
{5,8}, {6,7}, {6,8}
7. {1,3}, {1,4}, {1,8}, {2,3}, {2,4}, {2,6}, {2,7}, {3,5}, {4,6}, {4,7},
{5,7}, {5,8}, {6,7}, {6,8}
8. {1,3}, {1,4}, {1,5}, {1,8}, {2,4}, {2,5}, {2,6}, {2,7}, {3,6}, {3,7},
{3,8}, {4,7}, {4,8}, {5,6}, {5,7}, {6,8}
9. {1,3}, {1,4}, {1,6}, {1,7}, {1,8}, {2,4}, {2,5}, {2,7}, {3,5}, {3,6},
{3,8}, {4,5}, {4,8}, {5,6}, {5,7}, {6,7}
10. {1,3}, {1,7}, {1,8}, {2,4}, {2,6}, {2,7}, {3,4}, {3,5}, {3,6}, {4,8},
{5,7}, {5,8}, {6,8}
11. {1,2}, {1,4}, {1,5}, {1,6}, {2,3}, {2,6}, {2,7}, {3,7}, {3,8}, {4,6},
{4,7}, {4,8}, {5,7}, {5,8}
12. {1,5}, {1,6}, {1,7}, {2,3}, {2,4}, {2,6}, {2,7}, {3,8}, {3,9}, {4,5},
{4,7}, {4,8}, {5,6}, {6,9}, {7,9}, {8,9}
13. {1,3}, {1,6}, {1,7}, {1,8}, {2,4}, {2,6}, {2,7}, {3,4}, {3,5}, {3,7},
{4,7}, {4,9}, {5,8}, {5,9}, {6,7}, {6,8}, {8,9}
14. {1,2}, {1,7}, {1,8}, {1,9}, {2,5}, {2,8}, {2,9}, {3,5}, {3,6}, {3,8},
{4,5}, {4,7}, {4,9}, {6,8}, {6,9}
15. {1,3}, {1,5}, {1,9}, {2,4}, {2,8}, {2,10}, {3,5}, {3,6}, {3,9}, {4,6},
{4,10}, {5,7}, {6,8}, {7,9}, {7,10}, {8,10}
45
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
16. {1,3}, {1,4}, {1,5}, {1,6}, {2,5}, {2,6}, {2,7}, {2,8}, {3,4}, {3,5},
{3,7}, {4,6}, {4,8}, {5,7}, {5,8}, {6,7}, {6,8}
17. {1,4}, {1,5}, {1,6}, {1,7}, {2,3}, {2,4}, {2,6}, {2,8}, {3,5}, {3,7},
{3,8}, {4,5}, {4,6}, {5,7}, {6,8}, {7,8}
18. {1,3}, {1,5}, {1,6}, {1,7}, {2,4}, {2,5}, {2,8}, {3,4}, {3,5}, {4,6},
{4,7}, {6,8}, {7,8}
19. {1,3}, {1,6}, {1,7}, {1,8}, {2,4}, {2,5}, {2,7}, {3,5}, {3,6}, {3,7},
{4,6}, {4,8}, {5,8}, {6,7}
20. {1,1,3}, {1,5}, {1,7}, {1,8}, {2,4}, {2,6}, {2,7}, {2,8}, {3,5}, {3,6},
{3,7}, {4,5}, {4,6}, {4,7}, {5,8}, {6,8}
21. {1,3}, {1,4}, {1,7}, {1,8}, {2,4}, {2,5}, {2,6}, {2,8}, {3,6}, {3,8},
{4,5}, {4,6}, {4,7}, {5,7}, {5,8}, {6,8}
22. {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,6}, {2,8}, {3,7}, {4,7}, {4,8},
{5,7}, {5,8}, {6,7}
23. {1,2}, {1,5}, {1,7}, {1,8}, {2,3}, {2,4}, {2,8}, {3,5}, {3,6}, {4,5},
{4,6}, {4,7}, {5,7}, {6,8}
24. {1,3}, {1,5}, {1,6}, {1,8}, {2,6}, {2,8}, {2,9}, {3,7}, {3,8}, {3,9},
{4,5}, {4,6}, {4,7}, {4,8}, {5,7}, {6,9}
25. {1,3}, {1,4}, {1,7}, {2,4}, {2,7}, {2,8}, {2,9}, {3,6}, {3,7}, {3,9},
{4,5}, {4,7}, {5,6}, {5,8}, {6,8}, {6,9}, {7,9}
26. {1,3}, {1,4}, {1,8}, {2,3}, {2,6}, {2,7}, {2,9}, {3,6}, {3,8}, {4,5},
{4,6}, {5,7}, {5,9}, {6,9}, {8,9}
27. {1,2}, {1,6}, {1,9}, {2,3}, {2,8}, {2,10}, {3,5}, {3,8}, {4,6}, {4,7},
{4,9}, {5,7}, {5,10}, {6,7}, {7,9}, {8,10}
28. {1,3}, {1,4}, {1,5}, {1,6}, {1,7}, {2,4}, {2,5}, {2,6}, {2,7}, {2,8},
{3,5}, {3,7}, {3,8}, {4,6}, {4,7}, {5,8}, {6,8}
29. {1,3}, {1,5}, {1,6}, {1,8}, {2,4}, {2,5}, {2,7}, {2,8}, {3,5}, {3,6},
{3,7}, {4,6}, {4,7}, {4,8}, {5,7}, {6,8}
46
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
30. {1,3}, {1,7}, {1,8}, {2,4}, {2,6}, {2,7}, {3,4}, {3,5}, {3,6}, {4,7},
{5,7}, {5,8}, {6,8}
31. {1,3}, {1,6}, {1,8}, {2,4}, {2,5}, {2,7}, {2,8}, {3,5}, {3,7}, {4,5},
{4,6}, {4,8}, {5,8}, {6,7}
32. {1,3}, {1,4}, {1,5}, {1,8}, {2,4}, {2,5}, {2,7}, {2,8}, {3,6}, {3,7},
{3,8}, {4,5}, {4,7}, {5,6}, {6,7}, {6,8}
33. {1,3}, {1,4}, {1,5}, {1,6}, {2,5}, {2,6}, {2,7}, {2,8}, {3,5}, {3,6},
{3,7}, {4,5}, {4,6}, {4,8}, {5,7}, {5,8}
34. {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,6}, {2,8}, {3,7}, {4,7}, {4,8},
{5,7}, {5,8}, {6,7}
35. {1,5}, {1,6}, {1,8}, {2,3}, {2,4}, {2,5}, {2,6}, {3,6}, {3,7}, {4,7},
{4,8}, {5,7}, {5,8}, {6,8}
36. {1,3}, {1,4}, {1,7}, {2,4}, {2,5}, {2,8}, {2,9}, {3,6}, {3,8}, {3,9},
{4,6}, {4,7}, {5,6}, {5,8}, {6,9}, {7,9}
37. {1,4}, {1,6}, {1,7}, {1,9}, {2,3}, {2,8}, {2,9}, {3,4}, {3,5}, {3,8},
{4,7}, {5,6}, {5,7}, {5,8}, {6,8}, {6,9}, {8,9}
38. {1,4}, {1,5}, {1,6}, {1,7}, {2,7}, {2,8}, {2,9}, {3,4}, {3,5}, {4,6},
{4,9}, {5,8}, {6,8}, {6,9}, {7,9}
39. {1,6}, {1,7}, {1,8}, {2,6}, {2,7}, {2,8}, {3,4}, {3,6}, {3,9}, {3,10},
{4,9}, {4,10}, {5,8}, {5,9}, {5,10}, {7,8}
40. {1,2}, {1,5}, {1,6}, {1,8}, {2,3}, {2,6}, {2,7}, {2,8}, {3,4}, {3,7},
{3,8}, {4,5}, {4,6}, {4,7}, {5,6}, {5,7}, {5,8}
41. {1,2}, {1,5}, {1,6}, {1,8}, {2,3}, {2,7}, {2,8}, {3,4}, {3,7}, {3,8},
{4,5}, {4,6}, {4,7}, {5,6}, {5,7}, {6,8}
42. {1,5}, {1,6}, {1,7}, {2,6}, {2,7}, {2,8}, {3,5}, {3,7}, {3,8}, {4,6},
{4,7}, {4,8}, {5,6}
43. {1,2}, {1,6}, {1,7}, {1,8}, {2,4}, {2,6}, {2,8}, {3,5}, {3,6}, {3,7},
{4,5}, {4,7}, {5,8}, {6,8}
47
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
44. {1,3}, {1,4}, {1,5}, {1,8}, {2,4}, {2,5}, {2,7}, {2,8}, {3,6}, {3,7},
{3,8}, {4,5}, {4,7}, {5,6}, {6,7}, {6,8}
45. {1,4}, {1,5}, {1,6}, {2,3}, {2,6}, {2,7}, {2,8}, {3,4}, {3,5}, {3,7},
{3,8}, {4,6}, {4,8}, {5,6}, {5,7}, {6,8}
46. {1,6}, {1,7}, {1,8}, {2,6}, {2,7}, {2,8}, {3,5}, {3,6}, {3,8}, {4,5},
{4,6}, {4,8}, {5,7}
47. {1,4}, {1,5}, {1,6}, {1,8}, {2,4}, {2,7}, {2,8}, {3,4}, {3,6}, {3,8},
{4,7}, {5,6}, {5,7}, {6,7}
48. {1,2}, {1,3}, {1,5}, {1,6}, {2,4}, {2,6}, {2,8}, {3,7}, {3,8}, {4,5},
{4,9}, {5,8}, {5,9}, {6,7}, {6,9}, {7,8}
49. {1,2}, {1,7}, {1,8}, {1,9}, {2,3}, {2,9}, {3,4}, {3,5}, {3,9}, {4,5},
{4,7}, {4,9}, {5,6}, {5,8}, {6,7}, {6,8}, {7,9}
50. {1,2}, {1,3}, {1,4}, {1,6}, {2,5}, {2,9}, {3,4}, {3,6}, {3,7}, {4,8},
{4,9}, {5,6}, {5,7}, {6,8}, {8,9}
51. {1,2}, {1,6}, {1,9}, {2,3}, {2,8}, {2,10}, {3,5}, {3,8}, {4,6}, {4,7},
{4,9}, {5,7}, {5,10}, {6,7}, {7,9}, {8,10}
9
Маршруты в граах
Последовательность
[x1; u1; x2; u2; x3; : : : ; un 1; xn? (xi 2 X; ui 2 U );
в которой чередуются вершины и ребра, и при этом
8i 2
;n
1
1
ui = fxi; xi+1g;
называется маршрутом.
Чаще маршрут изображается последовательностью вершин
[x1; x2; : : : ; xn?;
для которой любые две соседние вершины смежны.
48
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Длина маршрута определяется либо как число ребер маршрута,
либо как сумма длин ребер (при введении весов ребер, называемых
их длиной)
l() =
X
u2
l(u):
Первый случай может быть включен во второй, если длину каждого
ребра по умолчанию считать равной 1.
Цепь маршрут, в котором все ребра попарно различны. Так, марш-
рут
[x1; x2; x3; x4; x5; x3; x2; x6? не является цепью ребро fx2; x3g по-
вторяется дважды.
Простая цепь это цепь, в которой нет повторяющихся вершин.
Так, цепь
[x1; x2; x3; x4; x2; x5? не является простой.
Маршрут замкнутый, если первая вершина маршрута совпадает с
последней.
Цикл замкнутая цепь (нет повторяющихся ребер).
Простой цикл цикл, у которого все вершины различны, кроме
совпадающих первой и последней вершин.
ра связен, если для любых двух его вершин существует цепь,
их соединяющая. Если гра
G не связен, то его можно разделить на
компоненты связности связные подграы, каждый из которых не
является собственным подграом никакого другого связного подграа из
G. Так, например, гра
G(f1; 2; 3; 4; 5; 6; 7g; ff1; 2g; f1; 3g; f2; 3g; f2; 4g; f5; 6gg)
состоит из трех компонент связности
G1(f5; 6gff5; 6gg); G2(f7g; ;);
G3(f1; 2; 3; 4g; ff1; 2g; f1; 3g; f2; 3g; f2; 4gg).
асстояние между вершинами длина кратчайшей цепи, их свя-
зывающей
(xi; xj ) =
min
=[xi ;:::;xj ?
l():
Диаметр связного граа расстояние между двумя наиболее уда-
ленными вершинами в грае
d(G) =
max
xi ;xj 2G
49
(xi; xj ):
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
адиусом граа называется минимум по всем вершинам расстоя-
ний от каждой из них до наиболее удаленной от нее вершины
r(G) = min max (x; y):
x2X y 2X
Центр граа множество вершин граа, расстояние от каждой из
которых до наиболее удаленной вершины граа равно радиусу граа
C
=
fxj x 2 X; x 2X x; xi
max
(
i
Так, для граа, изображенного на рис. 10,
) =
r(G)g:
r(G) = 2; C (G) = f1; 3; 4; 7g.
[x1; : : : ; xn?, проходимая в направлении ориента((xi ; xi+1) 2 U (i 2 1; n
1)), называется путем. Простой
В орграе цепь
ции дуг
путь есть простая ориентированная цепь. Контур есть ориентиро-
ванный цикл, а простой контур есть простой ориентированный цикл.
G(X; U ) называется связным, если из любой его вершины
x 2 X в любую его вершину y 2 X есть путь. При связности орграа
Оргра
аналогичным для обыкновенного граа образом вводятся диаметр,
радиус и центр орграа. Если оргра не связен, но обыкновенный
гра, полученный из него потерей ориентации дуг (заменой дуг на
ребра) является связным, то оргра называется слабо связным. Так,
оргра, изображенный на рис. 9, связный с диаметром 3, радиусом 2 и
центром {3}. А оргра
G(f1; 2; 3; 4g; f(1; 2); (1; 3); (1; 4); (2; 4); (4; 3)g),
отличающийся от предыдущего только ориентацией дуги между вершинами 1 и 3, не является связным,он слабо связный.
10
Задача о кратчайшем маршруте
Задача о кратчайшем маршруте для произвольных вершин
связного граа
G ормулируется следующим образом:
найти кратчайший маршрут
a
и
b
[a; : : : ; b? : l() = l(a; b).
Один из эективных алгоритмов нахождения кратчайшего маршрута предложен Дейкстрой. В этом алгоритме для каждой вершины
x вводятся 2 характеристики:
x расстояние от вершины a до x и
50
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
kx
номер предыдущей для
1 до
x.
x вершины на кратчайшем маршруте от
Пошаговое описание алгоритма:
o
Составляем множество
o
Среди всех вершин множества
1
2
S
всех вершин граа. Полагаем
o
Если
o
Исключаем вершину
4
S ищем вершину y с минимальным
= min
x2S
y
из множества
x = minfx ; y + l(y; x)g
o
Переходим к п. 2 .
o
Конец:
6
S
S
и пересчитываем харак-
вершин, смежных
y:
x 2 S; fy; xg 2 U ):
(
o
b
длина кратчайшего маршрута, а сам маршрут нахо-
дится по пометкам
11
x :
y = b, то переходим к п. 6o.
теристики остальных из множества
5
= 0,
ka = 0 и для каждой другой вершины x граа x = 1; kx = 0.
y
3
a
kx
предыдущих вершин:
[a; : : : ; kkb ; kb; b?.
Пример задачи на нахождение кратчайшего
маршрута в грае и ее решения
Пример 6. В списке ребер с их длинами каждый элемент есть упорядоченная пара: ребро как множество двух смежных вершин и длина
ребра:
( ({1,2}, 6), ({1,3}, 3), ({1,4}, 9), ({1,5}, 8), ({2,3}, 1), ({2,5}, 2),
({2,6}, 2), ({3,7}, 4), ({4,5}, 2), ({4,8}, 1), ({5,9}, 7), ({6,7}, 2),
({7,8}, 3), ({8,9}, 2) ).
A. В алгоритме Дейкстры для каждой вершины
x
вводятся 2 ха-
рактеристики:
x расстояние от начальной вершины (в условиях задачи 1) до x и
kx номер предыдущей вершины на кратчайшем маршруте от 1 до x.
В таблице выполнения алгоритма для каждого номера вершины заводим 2 колонки для
и k. Дадим пошаговое описание алгоритма:
51
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
o
1
S
Составляем множество
всех вершин граа. Полагаем
1
=
; k1 = 0 и для каждой другой вершины x граа x = 1; kx = 0.
0
o
2
Среди всех вершин множества
j
o
3
Если
S ищем вершину j с минимальным
= min
i2S
i:
j номер конечной (последней в условиях задачи) вершины,
o
то переходим к п. 6 .
o
4
Исключаем вершину
j
S
из множества
теристики вершин из множества
и пересчитываем харак-
S , смежных j :
i = minfi; j + ljig; ki = j;
где
lji
длина ребра
o
Переходим к п. 2 .
o
Конец:
5
6
fj; ig.
o
j
длина кратчайшего маршрута, а сам маршрут нахо-
k
дится по пометкам
предыдущих вершин:
j; kj ; kkj ; : : : .
B. Сведем выполнение алгоритма в следующую таблицу.
N
1
1
2
3
4
5
6
7
8
9
k k k k k k k k k
0
0
1
2
6
3
4
0
1
1
3
0
1
1
9
0
1
1
8
0
1
0
1
7
6
5
8
5
2
6
6
6
8
5
2
0
13
5
11
8
3
9
9
1
3
10
8
0
2
7
7
1
1
3
4
0
7
4
В этой таблице каждый столбец соответствует вершине граа и двум
его характеристикам
и
k,
каждая строка таблицы соответствует
определению новых значений характеристик при выполнении шагов
o
1
o
и 4
алгоритма, выбор вершины с минимальной характеристикой
52
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
обозначается заключением в рамку характеристик этой вершины (для
наглядности при необходимости эти характеристики сносятся в строку определения минимума
), а исключение вершины из множества S
помечается чертой над ее номером.
Мы получили длину 11 кратчайшего маршрута из вершины 1 в
вершину 9. Начиная с вершины 9, определяем последовательность номеров предшествующих вершин в найденном маршруте:
; ; ; ; ; ; :
9 8 4 5 2 3 1
Таким образом, кратчайший маршрут, соединяющий вершины 1 и 9:
[1; 3; 2; 5; 4; 8; 9?;
а его длина
l() = l(1; 3) + l(3; 2) + l(2; 5) + l(5; 4) + l(4; 8) + l(8; 9) = 11:
12
Эйлеровы маршруты
Эйлеровым маршрутом в грае называется маршрут (цепь, цикл),
содержащий все ребра граа. Эйлеровым ориентированным маршрутом в орграе называется ориентированный маршрут (путь, контур),
содержащий все дуги орграа. Критерий существования эйлеровой
цепи или цикла дает следующая теорема.
Теорема об эйлеровом маршруте.
Для того чтобы гра со-
держал эйлерову цепь, необходимо и достаточно, чтобы он был связен и имел ровно 2 вершины нечетной степени. Для того чтобы
гра содержал эйлеров цикл, необходимо и достаточно, чтобы он
был связен и не содержал вершин нечетной степени.
Доказательство. Необходимость. Если эйлерова цепь есть, то гра
связен (любые его вершины связаны этой цепью или ее частью). Нечетной степенью обладают только начальная и конечная вершины цепи.
Поэтому число вершин с нечетной степенью равно 2. Если мультигра
содержит эйлеров цикл, то он связен и все его вершины имеют четную
степень (при прохождении цикла сколько раз мы войдем в некоторую
его вершину, столько раз мы и выйдем из нее).
Достаточность. Доказательство проведем по индукции по числу ребер граа.
53
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
В случае, когда гра не имеет вершин нечетной степени, при числе
a и b, каждая из которых
имеет степень 2, и гра имеет цикл (a; b; a), который является эйле-
ребер
m(G) = 2
имеется ровно 2 вершины
ровым.
G связен и имеет ровно 2 вершины нечетной
степени a и b, при числе ребер m(G) = 1 утверждение справедливо, так как это ребро fa; bg и эйлеров путь [a; b?, а при числе ребер
m(G) = 2 утверждение также справедливо, так как есть эйлеров путь
[a; ; b?, где вершина, имеющая степень 2.
В случае, когда гра
Таким образом, основание индукции имеет место.
Пусть теперь утверждение теоремы справедливо для любого связного граа
G,
имеющего не более двух вершин нечетной степени, и
m(G) k, где k > 1, и докажем, что оно справедливо при m(G) =
k + 1. Пусть сначала гра G имеет ровно две вершины нечетной степени.
Отправим путешественника из вершины
a с условием не проходить
по одному и тому же ребру дважды. Если путешественник пришел в
x 6= b, то при x = a количество пройденных ребер, инцидентных a, четно (число выходов из вершины a равно числу входов в эту
вершину) и нечетная степень вершины a позволяет путешественнику
выйти из a по еще непройденному ребру, а если x 6= a, то количество
пройденных ребер, инцидентных x, нечетно (число входов в вершину x на 1 больше числа выходов из этой вершины) и четная степень
вершины x позволяет также выйти из этой вершины по еще непройвершину
денному ребру. Если невозможно идти дальше (все ребра, инцидентные вершине, уже пройдены), то это вершина
путешественником, обозначим через
b.
0 [a; : : : ; b?.
Цепь, пройденную
Однако при этом могут быть еще непройденные ребра граа. В
G , образованном удалением пройденных ребер, все вершины имеют уже четную степень и число его ребер m(G ) < k . Пусть
C1; : : : ; Cp компоненты связности G , содержащие хотя бы 1 ребро.
Так как m(Ci ) < k (i 2 1; k, то по предположению индукции для них
есть эйлеровы циклы 1 ; : : : ; p . Так как G связен, то цепь 0 встречает при ее прохождении все подграы C1 ; : : : ; Cp . Допустим, что
это происходит в вершинах x1 2 C1 ; : : : ; xp 2 Cp . Обозначим через
0[x; : : : ; y? отрезок цепи 0 от вершины x до вершины y. ассмотрим
подграе
0
0
0
54
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
цепь
0[a; : : : ; x1? + 1 + 0[x1; : : : ; x2? + 2 + + p + 0[xp; : : : ; b?:
Это и есть эйлерова цепь граа
G, которую необходимо было постро-
ить.
G не имеет вершин нечетной степени. Тогда,
удалив любое его ребро fa; bg, мы получим связный гра, содержащий
ровно 2 вершины нечетной степени a и b. Как мы только что доказали,
Пусть теперь гра
он имеет эйлерову цепь, а потому, добавив к этой цепи удаленное ребро
fa; bg, мы получим эйлеров цикл граа, что и требовалось. Теорема
доказана.
Замечание. Теорема очевидным образом переносится на мультигра (гра, между вершинами которого может быть более одного
ребра).
Теорема об эйлеровом ориентированном маршруте.
1. Для того чтобы оргра содержал эйлеров путь, необходимо и
достаточно, чтобы он был слабо связен и для всех вершин, кроме
двух, полустепень исхода была равна полустепени захода, для одной
вершины полустепень исхода была на 1 больше полустепени захода
и для другой вершины полустепень исхода была на 1 меньше полустепени захода.
2. Для того чтобы оргра содержал эйлеров контур, необходимо
и достаточно, чтобы он был слабо связен и для всех вершин полустепень исхода была равна полустепени захода.
Доказательство этой теоремы аналогично доказательству предыдущей для неориентированного граа. авенство полустепеней исхода и
захода для всех вершин, кроме двух, гарантирует, что, выйдя из вершины с полустепенью исхода большей полустепени захода, мы можем
остановиться только в вершине с полустепенью захода большей полустепени исхода, так как полустепени исхода и захода всех остальных
вершин равны.
Алгоритм отыскания эйлерова маршрута.
Конструкцию до-
казательства теорем нельзя использовать для построения эективного алгоритма отыскания эйлерова маршрута, так как оно содержит
неконструктивное предположение индукции.
Введем понятие перешейка граа, которое необходимо для описа-
55
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ния эективного алгоритма.
Перешейком в грае называется ребро, удаление которого приво-
дит к несвязности граа: нет маршрута из одного конца удаленного
ребра в другой (в одну компоненту связности попадает один конец
ребра, а в другую другой конец ребра).
Перешейком в орграе называется дуга, удаление которой приво-
дит к несвязности граа: из вершины конца дуги нет ориентированного маршрута в ее начало.
Опишем алгоритм построения эйлерова маршрута.
0:
1
Выходим из начальной вершины в зависимости от вида маршрута: при цикле или контуре из произвольной вершины, при цепи из любой вершины нечетной степени, при ориентированном пути
из вершины, полустепень исхода которой больше полустепени
захода. Все ребра (дуги) считаем непомеченными.
0:
2
Двигаемся из вершины при неориентированном маршруте по любому непомеченному ребру, не являющемуся перешейком в подграе непомеченных ребер, и помечаем пройденное ребро, а при
ориентированном маршруте по любой исходящей из вершины
непомеченной дуге, не являющейся перешейком в подграе из
непомеченных дуг, и помечаем ее.
0:
3
Повторяем предыдущий пункт до тех пор, пока не придем в вершину, все инцидентные ребра (исходящие дуги) которой уже помечены. Полученный маршрут и будет эйлеровым.
Для обоснования алгоритма нужно показать, что при выполнении
пункта 2
0
из достигнутой вершины всегда есть непомеченное исходя-
щее ребро (дуга), не являющееся перешейком, если эта вершина не
удовлетворяет условиям в пункте 3
0
алгоритма. Действительно, гра
из непомеченных ребер (дуг) удовлетворяет условиям теорем об эйлеровом маршруте, и эйлеров маршрут этого граа как раз выходит из
достигнутой вершины. Поэтому существует выходящее из этой вершины ребро (дуга) этого маршрута, которое не является перешейком.
Приведем теперь простой алгоритм, позволяющий определить, является ли выбранное ребро перешейком. Для этого в грае из непомеченных ребер будем определять компоненту связности другой вершины ребра (дуги), включая в нее эту вершину, затем смежные ей
56
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины по непомеченным ребрам (исходящим дугам), затем смежные им вершины по непомеченным ребрам (исходящим дугам) и т. д.
до тех пор, пока либо не будет включена другая вершина выбранного
ребра (дуги), либо процесс ормирования компоненты связности не
остановится с невключенной в нее другой вершиной выбранного ребра
(дуги). В первом случае выбранное ребро не является перешейком, а
во втором случае является.
13
Примеры задач на нахождение
эйлерова маршрута в грае и их решений
Пример 7.
2
66
66
66
4
001
101
001
010
110
010
100
001
011
000
100
100
3
77
77
77
5
Матрица смежности вершин граа симметрична, поэтому гра неориентированный. ра содержит 6 вершин и 7 ребер. Для анализа
связности граа образуем компоненту связности
C1, содержащую вер-
f g. Вершина 1 смежна
с вершинами 3, 4, 6. Добавим эти вершины: C1
f ; ; ; g. Вершина
3 смежна с вершинами 1, 2 и 5. Добавим их: C1
f ; ; ; ; ; g. Так
шину 1, и включим в нее эту вершину:
C1
=
1
=
как
C1
=
1 3 4 6
1 2 3 4 5 6
содержит все вершины граа, то гра связен.
Определяем степени вершин граа по матрице (число единиц в
каждой строке):
d1 = 3; d2 = 2; d3 = 3; d4 = 2; d5 = 2; d6 = 2. ра
содержит 4 вершины четной степени и 2 нечетной. Поэтому гра
не может содержать эйлеров цикл (все вершины для этого должны
иметь четную степень), но содержит эйлерову цепь, так как выполнены условия существования эйлеровой цепи:
Для того чтобы гра содержал эйлерову цепь, необходимо и достаточно, чтобы он был связен и содержал ровно две вершины нечетной
степени.
Опишем алгоритм нахождения эйлеровой цепи. Для этого все ребра
57
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
в начале алгоритма считаем непомеченными, а по мере их включения
в маршрут будем делать пометки соответствующих ребер.
o
1
Выбираем в качестве начальной любую вершину нечетной степени (для определенности берем вершину с меньшим номером) и
делаем ее текущей.
o
2
Если из текущей вершины нет непройденных (непомеченных) ребер, то алгоритм закончен: все ребра пройдены и цепь составляем
в порядке их прохождения.
o
3
Из текущей вершины выбираем любое ребро (для определенности
ребро, ведущее в вершину с наименьшим номером).
o
4
Если оно не является перешейком (из текущей вершины есть
еще непройденные ребра, а при временной пометке данного ребра гра непомеченных ребер не содержит маршрута из текущей
вершины в другую вершину данного ребра), то выбираем его, помечаем и делаем текущей вершину смежную по этому ребру с
o
предыдущей смежной вершиной. Переходим к п. 2 .
o
5
Если выбранное на предыдущем шаге ребро является перешейком, то выбираем следующее ребро, ведущее из текущей верши-
o
ны, и переходим к п. 4 .
Выполнение алгоритма сводим в следующую таблицу.
N
f; g f; g f; g f; g f; g f; g f; g
1 3
1 4
1 6
2 3
2 5
3 5
4 6
0
1
1
+
4
2
+
3
4
5
I
+
6
1
+
3
+
6
2
+
7
5
+
3
Каждый столбец (кроме первого и последнего) отвечает ребру граа.
Для пометки ребра ставим над ним черту. В первом столбце отмечаем
номер шага выполнения алгоритма, а в последнем номер текущей
58
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины. Если рассматриваемое ребро является перешейком, то на
пересечении текущей строки выполнения алгоритма и столбца ребра
ставим минус. В противном случае ставим плюс, помечаем ребро и
заносим новую текущую вершину.
По окончании алгоритма столбец текущей вершины определит эйлерову цепь. На шаге 1 выполнения алгоритма ребро {1,3} является
перешейком, так как после его временного исключения не существует маршрута, связывающего вершины 1 и 3: компонента связности в
грае непомеченных ребер, содержащая вершину 1, содержит также
смежные с ней вершины 4 и 6, но никаких других вершин (в частности, вершины 3) не содержит.
В результате выполнения алгоритма получена следующая эйлерова
цепь:
; ; ; ; ; ; ; :
(1 4 6 1 3 2 5 3)
Пример 8.
2
66
66
66
66
66
64
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
3
77
77
77
77
77
75
Матрица смежности вершин кососимметрична, поэтому это оргра.
Определяем связность граа как неориентированного. Включаем в
компоненту связности
C1
вершину 1:
ны вершины 3 и 5, добавляем их:
C1
C1
=
f g. Вершине 1 смежf ; ; g. Вершинам 3 и 5
=
1
1 3 5
смежны вершины 6, 7, 8. Добавляем их в компоненту связности:
f
; ; ; ; ;
g
C1 =
1 3 5 6 7 8 . Вершинам 6 и 8 смежны вершины 2 и 4. Добавляем их
в компоненту связности:
C1
=
f
; ; ; ; ; ; ;
g
1 2 3 4 5 6 7 8 . Поскольку компо-
нента связности содержит все вершины граа, он связен как неориентированный.
Находим полустепени исхода и захода для каждой вершины и сравниваем их:
59
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
1.
d1
2.
d2
3.
d3
4.
d4
5.
d5
6.
d6
7.
d7
8.
d8
; d+1 = 1 ! d1
+
= 1; d2 = 1 ! d2
+
= 2; d3 = 2 ! d3
+
= 1; d4 = 1 ! d4
+
= 2; d5 = 2 ! d5
+
= 2; d6 = 2 ! d6
+
= 1; d7 = 1 ! d7
+
= 2; d8 = 2 ! d8
= 1
d+1
+
= d2
+
= d3
+
= d4
+
= d5
+
= d6
+
= d7
+
= d8
=
Из того, что оргра слабо связен (связен как неориентированный) и
для каждой вершины полустепень исхода и полустепень захода совпадают, следует, что оргра содержит эйлеров контур, так как выполнены условия существования эйлерова контура:
Для того чтобы оргра содержал эйлеров контур, необходимо и достаточно, чтобы он был слабо связен и для каждой вершины полустепени исхода и захода были бы равны.
Опишем алгоритм нахождения эйлерова контура. Для этого все
дуги в начале алгоритма считаем непомеченными, а по мере их включения в маршрут будем делать пометки соответствующих дуг.
o
1
Выбираем в качестве начальной любую вершину нечетной степени (для определенности берем вершину 1) и делаем ее текущей.
o
2
Если из текущей вершины нет непройденных (непомеченных) выходящих дуг, то алгоритм закончен: все дуги пройдены и контур
составляем в порядке их прохождения.
o
3
Из текущей вершины выбираем любую непомеченную выходящую дугу (для определенности дугу, ведущую в вершину с наименьшим номером).
o
4
Если она не является перешейком (из текущей вершины есть еще
непройденные выходящие дуги, а при временной пометке данной
дуги из ее конечной вершины не существует пути до текущей
60
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины в орграе непомеченных дуг), то выбираем ее, помечаем и делаем текущей конечную вершину этой дуги. Переходим к
o:
п. 2
o
5
Если выбранная на предыдущем шаге дуга является перешейком, то выбираем следующую непомеченную выходящую дугу из
o
текущей вершины, помечаем ее и переходим к п. 4 .
Выполнение алгоритма сводим в следующую таблицу.
N
;
1 5
;
2 6
;
3 1
;
3 5
;
4 6
;
5 7
;
5 8
;
6 3
;
6 8
;
7 3
;
8 2
;
8 4
0
1
1
+
5
2
+
7
3
+
4
5
+
8
6
+
2
+
6
8
+
9
8
+
10
+
4
6
11
12
3
+
5
7
I
+
+
3
1
Каждый столбец (кроме первого и последнего) отвечает дуге орграа. Для пометки дуги ставим над ней черту. В первом столбце отмечаем номер шага выполнения алгоритма, а в последнем номер
текущей вершины. Если рассматриваемая дуга является перешейком,
то на пересечении текущей строки выполнения алгоритма и столбца
дуги ставим минус. В противном случае ставим плюс, помечаем дугу
и заносим новую текущую вершину. По окончании алгоритма столбец
текущей вершины определит эйлеров контур. Отметим, что на шаге
4 выполнения алгоритма дуга (3,1) является перешейком, так как из
вершины 1 нет уже выходящих непомеченных дуг, а потому нет пути
до вершины 3 в грае непомеченных дуг. На шаге 8 выполнения алгоритма дуга (6,3) также является перешейком, так как из вершины
3 можно достигнуть только вершины 1 в грае непомеченных дуг, но
никак не вершины 6.
61
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
В результате выполнения алгоритма получен следующий эйлеров
контур:
; ; ; ; ; ; ; ; ; ; ; ; :
(1 5 7 3 5 8 2 6 8 4 6 3 1)
14
Индивидуальное задание 7
14.1 Общее задание
1. Для граа, заданного списком ребер с их длинами, найти кратчайший маршрут из первой вершины граа (с номером 1) в последнюю вершину (с наибольшим номером):
a) описать алгоритм Дейкстры нахождения кратчайшего маршрута
в грае с пояснением всех вводимых в алгоритме обозначений;
b) свести выполнение алгоритма для заданного граа в таблицу;
) построить реализацию граа с указанием длин ребер и выделением жирными ребрами найденного кратчайшего маршрута.
2. Для граа (или орграа), заданного матрицей смежности вершин, найти эйлеров маршрут (цикл, контур, цепь, путь):
a) анализировать гра на существование эйлерова маршрута (цикла, контура, цепи, пути), сормулировав соответствующий критерий существования;
b) описать алгоритм нахождения эйлерова маршрута (цикла или
контура, цепи, пути);
) свести выполнение алгоритма для заданного граа в таблицу;
d) выписать полученный маршрут в качестве результата.
14.2 Варианты индивидуального задания 7
Задача 1
1. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({2,3}, 1), ({2,5}, 2), ({2,6}, 4),
({3,4}, 1), ({3,6}, 2), ({4,6}, 3), ({4,7}, 6), ({5,6}, 2), ({5,8}, 7),
({6,7}, 3), ({6,8}, 6), ({7,8}, 2) ).
62
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2. ( ({1,2}, 2), ({1,3}, 6), ({1,4}, 5), ({2,3}, 4), ({2,5}, 1), ({3,4}, 1),
({3,5}, 2), ({3,6}, 2), ({3,7}, 1), ({4,7}, 1), ({5,6}, 4), ({5,8}, 6),
({6,7}, 1), ({6,8}, 2), ({7,8}, 2) ).
3. ( ({1,2}, 1), ({1,3}, 4), ({1,4}, 7), ({1,5}, 4), ({2,5}, 2), ({3,7}, 4),
({4,6}, 1), ({4,7}, 1), ({5,6}, 2), ({5,8}, 6), ({6,8}, 4), ({7,8}, 1) ).
4. ( ({1,2}, 1), ({1,3}, 4), ({1,4}, 3), ({2,3}, 2), ({2,5}, 4), ({3,5}, 1),
({3,6}, 4), ({4,6}, 4), ({4,7}, 5), ({5,6}, 2), ({5,8}, 6), ({6,7}, 1),
({6,8}, 4), ({7,8}, 2) ).
5. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({2,3}, 1), ({2,5}, 3), ({2,6}, 5),
({3,4}, 1), ({3,7}, 2), ({4,5}, 2), ({4,7}, 3), ({5,8}, 4), ({6,7}, 1),
({6,8}, 2), ({7,8}, 4) ).
6. ( ({1,2}, 2), ({1,3}, 2), ({1,4}, 4), ({2,3}, 1), ({2,5}, 5), ({2,6}, 4),
({3,4}, 1), ({3,6}, 4), ({4,6}, 2), ({4,7}, 4), ({5,6}, 1), ({5,8}, 3),
({6,7}, 1), ({6,8}, 4), ({7,8}, 2) ).
7. ( ({1,2}, 3), ({1,3}, 4), ({1,4}, 2), ({2,3}, 1), ({2,5}, 3), ({3,4}, 1),
({3,5}, 2), ({3,6}, 4), ({3,7}, 2), ({4,7}, 3), ({5,6}, 1), ({5,8}, 4),
({6,7}, 2), ({6,8}, 2), ({7,8}, 4) ).
8. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({1,5}, 3), ({2,3}, 1), ({2,6}, 4),
({3,6}, 3), ({3,7}, 2), ({4,8}, 4), ({5,7}, 3), ({6,9}, 3), ({7,8}, 1),
({7,9}, 4) ({8,9}, 2) ).
9. ( ({1,2}, 1), ({1,3}, 2), ({1,4}, 2), ({1,5}, 7), ({2,6}, 2), ({3,6}, 1),
({3,7}, 2), ({4,7}, 1), ({5,8}, 2), ({5,9}, 2), ({6,7}, 1), ({6,9}, 6),
({7,8}, 1) ({7,9}, 6), ({8,9}, 5) ).
10. ( ({1,2}, 3), ({1,3}, 2), ({1,4}, 4), ({1,5}, 6), ({2,7}, 4), ({3,6}, 3),
({3,8}, 1), ({4,7}, 3), ({5,7}, 1), ({5,8}, 2), ({6,9}, 4), ({7,9}, 2)
({8,9}, 6) ).
11. ( ({1,5}, 2), ({1,6}, 4), ({1,7}, 3), ({2,3}, 2), ({2,5}, 2), ({2,8}, 7),
({3,4}, 3), ({3,5}, 4), ({3,6}, 2), ({3,7}, 3), ({3,8}, 6), ({4,7}, 6),
({4,8}, 2), ({5,6}, 1), ({6,7}, 1) ).
12. ( ({1,5}, 6), ({1,6}, 2), ({1,7}, 5), ({2,3}, 4), ({2,4}, 1), ({2,5}, 2),
({2,8}, 2), ({3,5}, 2), ({3,6}, 1), ({3,8}, 6), ({4,5}, 1), ({4,7}, 1),
({4,8}, 2), ({5,6}, 4), ({5,7}, 1) ).
63
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
13. ( ({1,4}, 4), ({1,5}, 7), ({1,6}, 4), ({1,7}, 1), ({2,5}, 1), ({2,6}, 4),
({2,8}, 1), ({3,4}, 2), ({3,5}, 1), ({3,8}, 4), ({4,7}, 2), ({4,8}, 6) ).
14. ( ({1,5}, 3), ({1,6}, 1), ({1,7}, 4), ({2,3}, 1), ({2,4}, 2), ({2,5}, 4),
({2,7}, 4), ({2,8}, 4), ({3,5}, 5), ({3,8}, 2), ({4,6}, 4), ({4,7}, 1),
({4,8}, 6), ({6,7}, 2) ).
15. ( ({1,2}, 4), ({1,3}, 2), ({1,5}, 3), ({2,3}, 1), ({2,5}, 1), ({2,6}, 2),
({3,4}, 3), ({3,7}, 5), ({4,5}, 2), ({4,8}, 4), ({5,6}, 3), ({6,7}, 1),
({6,8}, 4), ({7,8}, 2) ).
16. ( ({1,5}, 2), ({1,6}, 4), ({1,7}, 2), ({2,4}, 1), ({2,5}, 5), ({2,8}, 3),
({3,4}, 1), ({3,6}, 4), ({3,8}, 2) ({4,5}, 4), ({4,6}, 2), ({4,7}, 4),
({4,8}, 4), ({5,7}, 1), ({6,7}, 1) ).
17. ( ({1,2}, 2), ({1,4}, 3), ({1,6}, 4), ({2,5}, 3), ({2,6}, 1), ({3,5}, 2),
({3,6}, 4), ({3,7}, 1), ({3,8}, 2), ({4,6}, 1), ({4,7}, 3), ({5,6}, 2),
({5,8}, 4), ({6,7}, 2), ({7,8}, 4) ).
18. ( ({1,3}, 3), ({1,4}, 4), ({1,6}, 2), ({1,8}, 3), ({2,6}, 4), ({2,4}, 3),
({2,9}, 3), ({3,5}, 4), ({4,6}, 1), ({4,7}, 2), ({5,7}, 1), ({5,9}, 2)
({7,8}, 3), ({7,9}, 4) ).
19. ( ({1,2}, 2), ({1,3}, 1), ({1,4}, 7), ({1,5}, 2), ({2,7}, 2), ({2,8}, 1),
({3,8}, 2), ({4,6}, 2), ({4,9}, 2), ({5,7}, 1), ({6,7}, 1), ({6,9}, 5)
({7,8}, 1), ({7,9}, 6), ({8,9}, 6) ).
20. ( ({1,2}, 4), ({1,3}, 6), ({1,4}, 3), ({1,5}, 2), ({2,7}, 3), ({3,6}, 2),
({3,7}, 1), ({4,7}, 4), ({5,6}, 1), ({5,8}, 3), ({6,9}, 6), ({7,9}, 2)
({8,9}, 4) ).
21. ( ({1,5}, 7), ({1,6}, 6), ({1,7}, 2), ({2,3}, 1), ({2,5}, 2), ({2,6}, 4),
({2,8}, 2), ({3,4}, 1), ({3,6}, 2), ({3,8}, 4), ({4,6}, 3), ({4,7}, 6),
({4,8}, 3), ({5,6}, 2), ({6,7}, 3) ).
22. ( ({1,5}, 6), ({1,6}, 2), ({1,7}, 2), ({2,3}, 4), ({2,5}, 1), ({2,8}, 2),
({3,4}, 1), ({3,5}, 2), ({3,6}, 2), ({3,7}, 1), ({3,8}, 6), ({4,7}, 1),
({4,8}, 5), ({5,6}, 4), ({6,7}, 1) ).
23. ( ({1,5}, 6), ({1,6}, 4), ({1,7}, 1), ({2,5}, 2), ({2,8}, 1), ({3,7}, 4),
({3,8}, 4), ({4,6}, 1), ({4,7}, 1), ({4,8}, 7), ({5,6}, 2), ({5,8}, 4) ).
64
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
24. ( ({1,5}, 6), ({1,6}, 4), ({1,7}, 2), ({2,3}, 2), ({2,5}, 4), ({2,8}, 1),
({3,5}, 1), ({3,6}, 4), ({3,8}, 4), ({4,6}, 4), ({4,7}, 5), ({4,8}, 3),
({5,6}, 2), ({6,7}, 1) ).
25. ( ({1,5}, 4), ({1,6}, 2), ({1,7}, 4) ({2,3}, 1), ({2,5}, 3), ({2,6}, 5),
({2,8}, 2), ({3,4}, 1), ({3,7}, 2), ({3,8}, 4), ({4,5}, 2), ({4,7}, 3),
({4,8}, 3), ({6,7}, 1) ).
26. ( ({1,5}, 3), ({1,6}, 4), ({1,7}, 2), ({2,3}, 1), ({2,5}, 5), ({2,6}, 4),
({2,8}, 2), ({3,4}, 1), ({3,6}, 4), ({3,8}, 2), ({4,6}, 2), ({4,7}, 4),
({4,8}, 4), ({5,6}, 1), ({6,7}, 1) ).
27. ( ({1,5}, 4), ({1,6}, 2), ({1,7}, 4), ({2,3}, 1), ({2,5}, 3), ({2,8}, 3),
({3,4}, 1), ({3,5}, 2), ({3,6}, 4), ({3,7}, 2), ({3,8}, 4), ({4,7}, 3),
({4,8}, 2), ({5,6}, 1), ({6,7}, 2) ).
28. ( ({1,6}, 3), ({1,7}, 4) ({1,8}, 2), ({2,3}, 1), ({2,6}, 4), ({2,9}, 2),
({3,6}, 3), ({3,7}, 2), ({3,9}, 4), ({4,8}, 4), ({4,9}, 3), ({5,7}, 3),
({5,9}, 3), ({7,8}, 1) ).
29. ( ({1,5}, 2), ({1,6}, 6), ({1,7}, 6), ({1,8}, 5), ({2,6}, 2), ({2,9}, 1),
({3,6}, 1), ({3,7}, 2), ({3,9}, 2), ({4,7}, 1), ({4,9}, 2), ({5,8}, 2),
({5,9}, 7), ({6,7}, 1), ({7,8}, 1) ).
30. ( ({1,6}, 4), ({1,7}, 2) ({1,8}, 6), ({2,7}, 4), ({2,9}, 3), ({3,6}, 3),
({3,8}, 1), ({3,9}, 2), ({4,7}, 3), ({4,9}, 4), ({5,7}, 1), ({5,8}, 2),
({5,9}, 6) ).
31. ( ({1,2}, 7), ({1,3}, 6), ({1,4}, 2), ({2,3}, 2), ({2,5}, 2), ({3,4}, 3),
({3,5}, 4), ({3,6}, 2), ({3,7}, 3), ({4,7}, 6), ({5,6}, 1), ({5,8}, 2),
({6,7}, 1), ({6,8}, 4), ({7,8}, 3) ).
32. ( ({1,2}, 2), ({1,3}, 6), ({1,4}, 2), ({2,3}, 4), ({2,4}, 1), ({2,5}, 2),
({3,5}, 2), ({3,6}, 1), ({4,5}, 1), ({4,7}, 1), ({5,6}, 4), ({5,7}, 1),
({5,8}, 6), ({6,8}, 2), ({7,8}, 5) ).
33. ( ({1,2}, 1), ({1,3}, 4), ({1,4}, 6), ({2,5}, 1), ({2,6}, 4), ({3,4}, 2),
({3,5}, 1), ({4,7}, 2), ({4,8}, 4), ({5,8}, 7), ({6,8}, 4), ({7,8}, 1) ).
34. ( ({1,2}, 4), ({1,3}, 2), ({1,4}, 6), ({2,3}, 1), ({2,4}, 2), ({2,5}, 4),
({2,7}, 4), ({3,5}, 5), ({4,6}, 4), ({4,7}, 1), ({5,8}, 3), ({6,7}, 2),
({6,8}, 1), ({7,8}, 4) ).
65
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
35. ( ({1,4}, 4), ({1,6}, 4), ({1,7}, 2) ({2,3}, 1), ({2,5}, 1), ({2,6}, 2),
({2,8}, 4), ({3,4}, 3), ({3,7}, 5), ({3,8}, 2), ({4,5}, 2), ({5,6}, 3),
({5,8}, 3), ({6,7}, 1) ).
36. ( ({1,2}, 3), ({1,3}, 2) ({1,4}, 4), ({2,4}, 1), ({2,5}, 5), ({3,4}, 1),
({3,6}, 4), ({4,5}, 4), ({4,6}, 2), ({4,7}, 4), ({5,7}, 1), ({5,8}, 2),
({6,7}, 1), ({6,8}, 4), ({7,8}, 2) ).
37. ( ({1,3}, 2), ({1,5}, 4), ({1,7}, 4), ({2,5}, 3), ({2,6}, 1), ({2,8}, 2),
({3,5}, 2), ({3,6}, 4), ({3,7}, 1), ({4,6}, 1), ({4,7}, 3), ({4,8}, 3),
({5,6}, 2), ({6,7}, 2), ({6,8}, 4) ).
38. ( ({1,2}, 3), ({1,5}, 2) ({1,7}, 4) ({2,4}, 3), ({2,6}, 4), ({3,5}, 4),
({3,9}, 3), ({4,6}, 1), ({4,7}, 2), ({4,9}, 4), ({5,7}, 1), ({6,9}, 2),
({7,8}, 3), ({8,9}, 3) ).
39. ( ({1,4}, 2), ({1,6}, 5) ({1,7}, 6), ({1,8}, 6), ({2,7}, 2), ({2,8}, 1),
({2,9}, 2), ({3,8}, 2), ({3,9}, 1), ({4,6}, 2), ({4,9}, 7), ({5,7}, 1),
({5,9}, 2), ({6,7}, 1), ({7,8}, 1) ).
40. ( ({1,6}, 6), ({1,7}, 2) ({1,8}, 4), ({2,7}, 3), ({2,9}, 4), ({3,6}, 2),
({3,7}, 1), ({3,9}, 6), ({4,7}, 4), ({4,9}, 3), ({5,6}, 1), ({5,8}, 3),
({5,9}, 2) ).
41. ( ({1,2}, 4), ({1,3}, 2), ({1,5}, 3), ({2,3}, 1), ({2,5}, 1), ({2,7}, 2),
({3,4}, 2), ({3,7}, 4), ({4,7}, 2), ({4,8}, 7), ({5,6}, 6), ({5,7}, 3),
({6,7}, 3), ({6,8}, 2), ({7,8}, 6) ).
42. ( ({1,2}, 6), ({1,3}, 2), ({1,5}, 5), ({2,3}, 4), ({2,4}, 2), ({2,5}, 1),
({2,6}, 1), ({2,7}, 2), ({3,4}, 1), ({4,7}, 4), ({4,8}, 6), ({5,6}, 1),
({6,7}, 1), ({6,8}, 2), ({7,8}, 2) ).
43. ( ({1,2}, 4), ({1,3}, 1), ({1,4}, 4), ({1,5}, 7), ({2,6}, 4), ({3,4}, 2),
({4,7}, 2), ({4,8}, 6), ({5,6}, 1), ({5,7}, 1), ({6,8}, 1), ({7,8}, 4) ).
44. ( ({1,2}, 4), ({1,3}, 1), ({1,5}, 3), ({2,3}, 2), ({2,4}, 1), ({2,7}, 4),
({3,4}, 4), ({4,7}, 2), ({4,8}, 6), ({5,6}, 5), ({5,7}, 4), ({6,7}, 1),
({6,8}, 2), ({7,8}, 4) ).
45. ( ({1,2}, 4), ({1,3}, 2), ({1,5}, 3), ({2,3}, 1), ({2,5}, 1), ({2,6}, 2),
({3,4}, 3), ({3,7}, 5), ({4,5}, 2), ({4,8}, 4), ({5,6}, 3), ({6,7}, 1),
({6,8}, 4), ({7,8}, 2) ).
66
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
46. ( ({1,2}, 2), ({1,3}, 2), ({1,5}, 4), ({2,3}, 1), ({2,5}, 1), ({2,7}, 4),
({3,4}, 5), ({3,7}, 4), ({4,7}, 1), ({4,8}, 3), ({5,6}, 4), ({5,7}, 2),
({6,7}, 1), ({6,8}, 2), ({7,8}, 4) ).
47. ( ({1,2}, 4), ({1,3}, 3), ({1,5}, 2), ({2,3}, 1), ({2,4}, 2), ({2,5}, 1),
({2,6}, 2), ({2,7}, 4), ({3,4}, 3), ({4,7}, 1), ({4,8}, 4), ({5,6}, 3),
({6,7}, 2), ({6,8}, 4), ({7,8}, 2) ).
48. ( ({1,2}, 4), ({1,3}, 2), ({1,4}, 3), ({1,5}, 3), ({2,3}, 1), ({2,6}, 2),
({2,7}, 3), ({3,7}, 4), ({4,6}, 3), ({5,8}, 4), ({6,8}, 1), ({6,9}, 4)
({7,9}, 3), ({8,9}, 2) ).
49. ( ({1,2}, 2), ({1,3}, 1), ({1,4}, 7), ({1,5}, 2), ({2,6}, 2), ({2,7}, 1),
({3,7}, 2), ({4,8}, 2), ({4,9}, 2), ({5,6}, 1), ({6,7}, 1), ({6,8}, 1)
({6,9}, 6), ({7,9}, 6), ({8,9}, 5) ).
50. ( ({1,2}, 2), ({1,3}, 3), ({1,4}, 6), ({1,5}, 4), ({2,7}, 3), ({2,8}, 1),
({3,7}, 4), ({4,6}, 1), ({4,8}, 2), ({5,6}, 3), ({6,9}, 2) ({7,9}, 4),
({8,9}, 6) ).
51. ( ({1,3}, 4), ({1,4}, 3), ({1,6}, 2), ({2,3}, 2), ({2,4}, 3), ({2,6}, 4),
({2,7}, 3), ({2,8}, 6), ({3,4}, 1), ({3,6}, 1), ({4,7}, 6), ({5,2}, 2),
({5,6}, 2), ({5,8}, 7), ({7,8}, 2) ).
67
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
64
1.
2.
3.
2
66
66
66
66
64
2
66
66
66
66
66
66
66
66
66
64
Задача 2
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
3
77
77
77
77
77
75
0
0
1
0
1
1
1
0
0
0
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
1
1
1
0
0
0
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
1
0
0
0
1
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
68
3
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
4.
2
66
66
66
66
66
64
0
1
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
2
66
66
66
66
66
64
5.
6.
7.
2
66
66
66
66
66
64
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
3
77
77
77
77
77
75
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
0
0
1
1
1
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
0
1
0
1
1
1
0
0
2
66
66
66
66
64
0
1
0
1
1
1
0
1
0
1
0
1
0
0
0
1
0
1
0
1
1
1
0
1
0
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
1
0
1
0
69
3
77
77
77
77
77
75
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
8.
2
66
66
66
66
66
64
1
1
1
0
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
0
1
1
0
2
66
66
66
66
66
64
9.
10.
0
2
66
66
66
66
64
0
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
0
3
77
77
77
77
77
75
0
1
0
1
0
1
1
1
0
0
1
0
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
1
0
0
0
1
0
1
0
1
0
0
70
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
66
66
66
66
64
11.
12.
13.
2
66
66
66
66
66
64
0
1
0
1
0
0
0
1
0
0
1
0
1
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
3
77
77
77
77
77
77
77
77
77
75
0
0
1
1
1
0
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
0
1
0
1
0
0
2
66
66
66
66
64
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
0
1
1
0
1
1
0
0
0
0
1
0
1
1
0
0
1
1
1
0
1
0
1
0
71
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
14.
2
66
66
66
66
66
66
66
66
66
64
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
2
66
66
66
66
66
64
15.
16.
2
66
66
66
66
66
66
66
66
66
64
0
0
1
1
1
0
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
0
3
77
77
77
77
77
75
0
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
1
1
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
0
0
0
0
1
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
72
3
77
77
77
77
77
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
64
17.
18.
19.
2
66
66
66
66
64
2
66
66
66
66
66
66
66
66
66
64
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
1
0
1
0
0
3
77
77
77
77
77
75
0
0
1
0
1
1
1
0
0
0
1
1
1
1
1
0
0
0
1
0
0
0
1
0
0
1
1
1
1
1
1
1
0
0
0
1
1
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
73
3
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
20.
2
66
66
66
66
66
64
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
0
2
66
66
66
66
66
64
21.
22.
23.
2
66
66
66
66
66
64
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
0
1
1
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
3
77
77
77
77
77
75
0
0
1
0
1
1
1
0
0
0
0
1
0
1
1
1
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
0
2
66
66
66
66
64
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
74
3
77
77
77
77
77
75
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
24.
2
66
66
66
66
66
64
0
0
0
0
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
0
0
2
66
66
66
66
66
64
25.
26.
0
2
66
66
66
66
64
0
0
1
1
1
0
0
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
0
1
1
1
0
0
0
1
1
0
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
0
0
1
1
1
0
1
0
0
0
3
77
77
77
77
77
75
0
1
1
0
1
0
1
1
0
0
1
0
1
1
1
0
0
0
1
1
0
0
1
0
0
0
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
1
1
1
0
1
0
1
0
75
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
66
66
66
66
64
27.
28.
29.
2
66
66
66
66
66
64
0
0
0
0
1
0
1
0
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
1
0
1
0
0
0
3
77
77
77
77
77
77
77
77
77
75
0
0
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
2
66
66
66
66
64
0
0
1
0
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
0
1
1
1
0
76
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
30.
2
66
66
66
66
66
66
66
66
66
64
0
0
0
0
0
0
0
1
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
0
0
1
1
0
0
1
0
0
0
1
1
0
1
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
2
66
66
66
66
66
64
31.
32.
2
66
66
66
66
66
66
66
66
66
64
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
1
1
0
1
0
0
3
77
77
77
77
77
75
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
77
3
77
77
77
77
77
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
64
33.
34.
35.
2
66
66
66
66
64
2
66
66
66
66
66
66
66
66
66
64
0
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
3
77
77
77
77
77
75
0
0
1
0
1
1
1
0
0
0
1
0
1
0
1
0
0
0
1
1
1
0
1
0
0
1
1
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
78
3
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
36.
2
66
66
66
66
66
64
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
1
0
0
1
0
0
2
66
66
66
66
66
64
37.
38.
39.
2
66
66
66
66
66
64
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
0
3
77
77
77
77
77
75
0
0
0
1
1
1
0
1
0
0
1
1
1
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
2
66
66
66
66
64
0
0
1
0
1
1
1
0
0
0
1
1
0
0
1
0
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
0
79
3
77
77
77
77
77
75
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
40.
2
66
66
66
66
66
64
0
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
1
1
1
1
0
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
1
0
1
0
0
0
0
2
66
66
66
66
66
64
41.
42.
0
2
66
66
66
66
64
0
0
1
0
1
0
1
1
0
0
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
3
77
77
77
77
77
75
0
0
1
0
1
0
0
0
0
1
1
0
1
1
1
1
0
0
1
1
0
0
1
0
0
1
1
1
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
1
0
1
0
1
0
80
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
66
66
66
66
64
43.
44.
45.
2
66
66
66
66
66
64
0
0
1
1
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
3
77
77
77
77
77
77
77
77
77
75
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
1
0
1
1
0
0
0
1
1
1
0
1
0
1
1
0
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
2
66
66
66
66
64
0
1
1
1
0
0
1
1
0
0
0
1
1
1
1
0
0
1
1
1
0
1
0
1
0
0
0
0
0
1
1
0
0
1
1
0
1
1
0
1
0
1
1
1
0
0
1
1
0
81
3
77
77
77
77
75
3
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
46.
2
66
66
66
66
66
66
66
66
66
64
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
2
66
66
66
66
66
64
47.
48.
2
66
66
66
66
66
66
66
66
66
64
0
1
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
1
0
1
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
0
0
3
77
77
77
77
77
75
0
1
1
0
0
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
82
3
77
77
77
77
77
77
77
77
77
75
3
77
77
77
77
77
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2
66
66
66
66
66
64
49.
50.
51.
2
66
66
66
66
64
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
1
1
0
1
1
0
0
3
77
77
77
77
77
75
0
0
1
0
0
1
0
0
0
0
1
1
1
1
1
0
0
1
1
1
0
0
1
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
1
0
2
66
66
66
66
66
64
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
0
1
1
0
1
1
1
0
0
0
0
0
1
0
1
1
0
0
83
3
77
77
77
77
77
75
3
77
77
77
77
75
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Учебное издание
ублев Вадим Сергеевич
ЭЛЕМЕНТЫ ТЕОИИ АФОВ.
ИЗОМОФИЗМ, ПЛАНАНОСТЬ,
МАШУТЫ В АФАХ
(индивидуальные работы ќ 6 и 7 по дисциплине
ѕОсновы дискретной математикиї)
Методические указания
едактор, корректор И. В. Бунакова
Верстка В. С. ублев
Подписано в печать 30.12.2009 г. Формат 60
84/16.
Усл. печ. л. 4,88. Уч.-изд. л. 3,2. Тираж 80 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе
Ярославского государственного университета им. П. . Демидова.
Отпечатано на ризограе.
Ярославский государственный университет им. П. . Демидова
150000, Ярославль, ул. Советская, 14.
?ой 1.
Цепь маршрут, в котором все ребра попарно различны. Так, марш-
рут
[x1; x2; x3; x4; x5; x3; x2; x6? не является цепью ребро fx2; x3g по-
вторяется дважды.
Простая цепь это цепь, в которой нет повторяющихся вершин.
Так, цепь
[x1; x2; x3; x4; x2; x5? не является простой.
Маршрут замкнутый, если первая вершина маршрута совпадает с
последней.
Цикл замкнутая цепь (нет повторяющихся ребер).
Простой цикл цикл, у которого все вершины различны, кроме
совпадающих первой и последней вершин.
ра связен, если для любых двух его вершин существует цепь,
их соединяющая. Если гра
G не связен, то его можно разделить на
компоненты связности связные подграы, каждый из которых не
является собственным подграом никакого другого связного подграа из
G. Так, например, гра
G(f1; 2; 3; 4; 5; 6; 7g; ff1; 2g; f1; 3g; f2; 3g; f2; 4g; f5; 6gg)
состоит из трех компонент связности
G1(f5; 6gff5; 6gg); G2(f7g; ;);
G3(f1; 2; 3; 4g; ff1; 2g; f1; 3g; f2; 3g; f2; 4gg).
асстояние между вершинами длина кратчайшей цепи, их свя-
зывающей
(xi; xj ) =
min
=[xi ;:::;xj ?
l():
Диаметр связного граа расстояние между двумя наиболее уда-
ленными вершинами в грае
d(G) =
max
xi ;xj 2G
49
(xi; xj ):
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
адиусом граа называется минимум по всем вершинам расстоя-
ний от каждой из них до наиболее удаленной от нее вершины
r(G) = min max (x; y):
x2X y 2X
Центр граа множество вершин граа, расстояние от каждой из
которых до наиболее удаленной вершины граа равно радиусу граа
C
=
fxj x 2 X; x 2X x; xi
max
(
i
Так, для граа, изображенного на рис. 10,
) =
r(G)g:
r(G) = 2; C (G) = f1; 3; 4; 7g.
[x1; : : : ; xn?, проходимая в направлении ориента((xi ; xi+1) 2 U (i 2 1; n
1)), называется путем. Простой
В орграе цепь
ции дуг
путь есть простая ориентированная цепь. Контур есть ориентиро-
ванный цикл, а простой контур есть простой ориентированный цикл.
G(X; U ) называется связным, если из любой его вершины
x 2 X в любую его вершину y 2 X есть путь. При связности орграа
Оргра
аналогичным для обыкновенного граа образом вводятся диаметр,
радиус и центр орграа. Если оргра не связен, но обыкновенный
гра, полученный из него потерей ориентации дуг (заменой дуг на
ребра) является связным, то оргра называется слабо связным. Так,
оргра, изображенный на рис. 9, связный с диаметром 3, радиусом 2 и
центром {3}. А оргра
G(f1; 2; 3; 4g; f(1; 2); (1; 3); (1; 4); (2; 4); (4; 3)g),
отличающийся от предыдущего только ориентацией дуги между вершинами 1 и 3, не является связным,он слабо связный.
10
Задача о кратчайшем маршруте
Задача о кратчайшем маршруте для произвольных вершин
связного граа
G ормулируется следующим образом:
найти кратчайший маршрут
a
и
b
[a; : : : ; b? : l() = l(a; b).
Один из эективных алгоритмов нахождения кратчайшего маршрута предложен Дейкстрой. В этом алгоритме для каждой вершины
x вводятся 2 характеристики:
x расстояние от вершины a до x и
50
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
kx
номер предыдущей для
1 до
x.
x вершины на кратчайшем маршруте от
Пошаговое описание алгоритма:
o
Составляем множество
o
Среди всех вершин множества
1
2
S
всех вершин граа. Полагаем
o
Если
o
Исключаем вершину
4
S ищем вершину y с минимальным
= min
x2S
y
из множества
x = minfx ; y + l(y; x)g
o
Переходим к п. 2 .
o
Конец:
6
S
S
и пересчитываем харак-
вершин, смежных
y:
x 2 S; fy; xg 2 U ):
(
o
b
длина кратчайшего маршрута, а сам маршрут нахо-
дится по пометкам
11
x :
y = b, то переходим к п. 6o.
теристики остальных из множества
5
= 0,
ka = 0 и для каждой другой вершины x граа x = 1; kx = 0.
y
3
a
kx
предыдущих вершин:
[a; : : : ; kkb ; kb; b?.
Пример задачи на нахождение кратчайшего
маршрута в грае и ее решения
Пример 6. В списке ребер с их длинами каждый элемент есть упорядоченная пара: ребро как множество двух смежных вершин и длина
ребра:
( ({1,2}, 6), ({1,3}, 3), ({1,4}, 9), ({1,5}, 8), ({2,3}, 1), ({2,5}, 2),
({2,6}, 2), ({3,7}, 4), ({4,5}, 2), ({4,8}, 1), ({5,9}, 7), ({6,7}, 2),
({7,8}, 3), ({8,9}, 2) ).
A. В алгоритме Дейкстры для каждой вершины
x
вводятся 2 ха-
рактеристики:
x расстояние от начальной вершины (в условиях задачи 1) до x и
kx номер предыдущей вершины на кратчайшем маршруте от 1 до x.
В таблице выполнения алгоритма для каждого номера вершины заводим 2 колонки для
и k. Дадим пошаговое описание алгоритма:
51
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
o
1
S
Составляем множество
всех вершин граа. Полагаем
1
=
; k1 = 0 и для каждой другой вершины x граа x = 1; kx = 0.
0
o
2
Среди всех вершин множества
j
o
3
Если
S ищем вершину j с минимальным
= min
i2S
i:
j номер конечной (последней в условиях задачи) вершины,
o
то переходим к п. 6 .
o
4
Исключаем вершину
j
S
из множества
теристики вершин из множества
и пересчитываем харак-
S , смежных j :
i = minfi; j + ljig; ki = j;
где
lji
длина ребра
o
Переходим к п. 2 .
o
Конец:
5
6
fj; ig.
o
j
длина кратчайшего маршрута, а сам маршрут нахо-
k
дится по пометкам
предыдущих вершин:
j; kj ; kkj ; : : : .
B. Сведем выполнение алгоритма в следующую таблицу.
N
1
1
2
3
4
5
6
7
8
9
k k k k k k k k k
0
0
1
2
6
3
4
0
1
1
3
0
1
1
9
0
1
1
8
0
1
0
1
7
6
5
8
5
2
6
6
6
8
5
2
0
13
5
11
8
3
9
9
1
3
10
8
0
2
7
7
1
1
3
4
0
7
4
В этой таблице каждый столбец соответствует вершине граа и двум
его характеристикам
и
k,
каждая строка таблицы соответствует
определению новых значений характеристик при выполнении шагов
o
1
o
и 4
алгоритма, выбор вершины с минимальной характеристикой
52
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
обозначается заключением в рамку характеристик этой вершины (для
наглядности при необходимости эти характеристики сносятся в строку определения минимума
), а исключение вершины из множества S
помечается чертой над ее номером.
Мы получили длину 11 кратчайшего маршрута из вершины 1 в
вершину 9. Начиная с вершины 9, определяем последовательность номеров предшествующих вершин в найденном маршруте:
; ; ; ; ; ; :
9 8 4 5 2 3 1
Таким образом, кратчайший маршрут, соединяющий вершины 1 и 9:
[1; 3; 2; 5; 4; 8; 9?;
а его длина
l() = l(1; 3) + l(3; 2) + l(2; 5) + l(5; 4) + l(4; 8) + l(8; 9) = 11:
12
Эйлеровы маршруты
Эйлеровым маршрутом в грае называется маршрут (цепь, цикл),
содержащий все ребра граа. Эйлеровым ориентированным маршрутом в орграе называется ориентированный маршрут (путь, контур),
содержащий все дуги орграа. Критерий существования эйлеровой
цепи или цикла дает следующая теорема.
Теорема об эйлеровом маршруте.
Для того чтобы гра со-
держал эйлерову цепь, необходимо и достаточно, чтобы он был связен и имел ровно 2 вершины нечетной степени. Для того чтобы
гра содержал эйлеров цикл, необходимо и достаточно, чтобы он
был связен и не содержал вершин нечетной степени.
Доказательство. Необходимость. Если эйлерова цепь есть, то гра
связен (любые его вершины связаны этой цепью или ее частью). Нечетной степенью обладают только начальная и конечная вершины цепи.
Поэтому число вершин с нечетной степенью равно 2. Если мультигра
содержит эйлеров цикл, то он связен и все его вершины имеют четную
степень (при прохождении цикла сколько раз мы войдем в некоторую
его вершину, столько раз мы и выйдем из нее).
Достаточность. Доказательство проведем по индукции по числу ребер граа.
53
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
В случае, когда гра не имеет вершин нечетной степени, при числе
a и b, каждая из которых
имеет степень 2, и гра имеет цикл (a; b; a), который является эйле-
ребер
m(G) = 2
имеется ровно 2 вершины
ровым.
G связен и имеет ровно 2 вершины нечетной
степени a и b, при числе ребер m(G) = 1 утверждение справедливо, так как это ребро fa; bg и эйлеров путь [a; b?, а при числе ребер
m(G) = 2 утверждение также справедливо, так как есть эйлеров путь
[a; ; b?, где вершина, имеющая степень 2.
В случае, когда гра
Таким образом, основание индукции имеет место.
Пусть теперь утверждение теоремы справедливо для любого связного граа
G,
имеющего не более двух вершин нечетной степени, и
m(G) k, где k > 1, и докажем, что оно справедливо при m(G) =
k + 1. Пусть сначала гра G имеет ровно две вершины нечетной степени.
Отправим путешественника из вершины
a с условием не проходить
по одному и тому же ребру дважды. Если путешественник пришел в
x 6= b, то при x = a количество пройденных ребер, инцидентных a, четно (число выходов из вершины a равно числу входов в эту
вершину) и нечетная степень вершины a позволяет путешественнику
выйти из a по еще непройденному ребру, а если x 6= a, то количество
пройденных ребер, инцидентных x, нечетно (число входов в вершину x на 1 больше числа выходов из этой вершины) и четная степень
вершины x позволяет также выйти из этой вершины по еще непройвершину
денному ребру. Если невозможно идти дальше (все ребра, инцидентные вершине, уже пройдены), то это вершина
путешественником, обозначим через
b.
0 [a; : : : ; b?.
Цепь, пройденную
Однако при этом могут быть еще непройденные ребра граа. В
G , образованном удалением пройденных ребер, все вершины имеют уже четную степень и число его ребер m(G ) < k . Пусть
C1; : : : ; Cp компоненты связности G , содержащие хотя бы 1 ребро.
Так как m(Ci ) < k (i 2 1; k, то по предположению индукции для них
есть эйлеровы циклы 1 ; : : : ; p . Так как G связен, то цепь 0 встречает при ее прохождении все подграы C1 ; : : : ; Cp . Допустим, что
это происходит в вершинах x1 2 C1 ; : : : ; xp 2 Cp . Обозначим через
0[x; : : : ; y? отрезок цепи 0 от вершины x до вершины y. ассмотрим
подграе
0
0
0
54
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
цепь
0[a; : : : ; x1? + 1 + 0[x1; : : : ; x2? + 2 + + p + 0[xp; : : : ; b?:
Это и есть эйлерова цепь граа
G, которую необходимо было постро-
ить.
G не имеет вершин нечетной степени. Тогда,
удалив любое его ребро fa; bg, мы получим связный гра, содержащий
ровно 2 вершины нечетной степени a и b. Как мы только что доказали,
Пусть теперь гра
он имеет эйлерову цепь, а потому, добавив к этой цепи удаленное ребро
fa; bg, мы получим эйлеров цикл граа, что и требовалось. Теорема
доказана.
Замечание. Теорема очевидным образом переносится на мультигра (гра, между вершинами которого может быть более одного
ребра).
Теорема об эйлеровом ориентированном маршруте.
1. Для того чтобы оргра содержал эйлеров путь, необходимо и
достаточно, чтобы он был слабо связен и для всех вершин, кроме
двух, полустепень исхода была равна полустепени захода, для одной
вершины полустепень исхода была на 1 больше полустепени захода
и для другой вершины полустепень исхода была на 1 меньше полустепени захода.
2. Для того чтобы оргра содержал эйлеров контур, необходимо
и достаточно, чтобы он был слабо связен и для всех вершин полустепень исхода была равна полустепени захода.
Доказательство этой теоремы аналогично доказательству предыдущей для неориентированного граа. авенство полустепеней исхода и
захода для всех вершин, кроме двух, гарантирует, что, выйдя из вершины с полустепенью исхода большей полустепени захода, мы можем
остановиться только в вершине с полустепенью захода большей полустепени исхода, так как полустепени исхода и захода всех остальных
вершин равны.
Алгоритм отыскания эйлерова маршрута.
Конструкцию до-
казательства теорем нельзя использовать для построения эективного алгоритма отыскания эйлерова маршрута, так как оно содержит
неконструктивное предположение индукции.
Введем понятие перешейка граа, которое необходимо для описа-
55
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ния эективного алгоритма.
Перешейком в грае называется ребро, удаление которого приво-
дит к несвязности граа: нет маршрута из одного конца удаленного
ребра в другой (в одну компоненту связности попадает один конец
ребра, а в другую другой конец ребра).
Перешейком в орграе называется дуга, удаление которой приво-
дит к несвязности граа: из вершины конца дуги нет ориентированного маршрута в ее начало.
Опишем алгоритм построения эйлерова маршрута.
0:
1
Выходим из начальной вершины в зависимости от вида маршрута: при цикле или контуре из произвольной вершины, при цепи из любой вершины нечетной степени, при ориентированном пути
из вершины, полустепень исхода которой больше полустепени
захода. Все ребра (дуги) считаем непомеченными.
0:
2
Двигаемся из вершины при неориентированном маршруте по любому непомеченному ребру, не являющемуся перешейком в подграе непомеченных ребер, и помечаем пройденное ребро, а при
ориентированном маршруте по любой исходящей из вершины
непомеченной дуге, не являющейся перешейком в подграе из
непомеченных дуг, и помечаем ее.
0:
3
Повторяем предыдущий пункт до тех пор, пока не придем в вершину, все инцидентные ребра (исходящие дуги) которой уже помечены. Полученный маршрут и будет эйлеровым.
Для обоснования алгоритма нужно показать, что при выполнении
пункта 2
0
из достигнутой вершины всегда есть непомеченное исходя-
щее ребро (дуга), не являющееся перешейком, если эта вершина не
удовлетворяет условиям в пункте 3
0
алгоритма. Действительно, гра
из непомеченных ребер (дуг) удовлетворяет условиям теорем об эйлеровом маршруте, и эйлеров маршрут этого граа как раз выходит из
достигнутой вершины. Поэтому существует выходящее из этой вершины ребро (дуга) этого маршрута, которое не является перешейком.
Приведем теперь простой алгоритм, позволяющий определить, является ли выбранное ребро перешейком. Для этого в грае из непомеченных ребер будем определять компоненту связности другой вершины ребра (дуги), включая в нее эту вершину, затем смежные ей
56
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины по непомеченным ребрам (исходящим дугам), затем смежные им вершины по непомеченным ребрам (исходящим дугам) и т. д.
до тех пор, пока либо не будет включена другая вершина выбранного
ребра (дуги), либо процесс ормирования компоненты связности не
остановится с невключенной в нее другой вершиной выбранного ребра
(дуги). В первом случае выбранное ребро не является перешейком, а
во втором случае является.
13
Примеры задач на нахождение
эйлерова маршрута в грае и их решений
Пример 7.
2
66
66
66
4
001
101
001
010
110
010
100
001
011
000
100
100
3
77
77
77
5
Матрица смежности вершин граа симметрична, поэтому гра неориентированный. ра содержит 6 вершин и 7 ребер. Для анализа
связности граа образуем компоненту связности
C1, содержащую вер-
f g. Вершина 1 смежна
с вершинами 3, 4, 6. Добавим эти вершины: C1
f ; ; ; g. Вершина
3 смежна с вершинами 1, 2 и 5. Добавим их: C1
f ; ; ; ; ; g. Так
шину 1, и включим в нее эту вершину:
C1
=
1
=
как
C1
=
1 3 4 6
1 2 3 4 5 6
содержит все вершины граа, то гра связен.
Определяем степени вершин граа по матрице (число единиц в
каждой строке):
d1 = 3; d2 = 2; d3 = 3; d4 = 2; d5 = 2; d6 = 2. ра
содержит 4 вершины четной степени и 2 нечетной. Поэтому гра
не может содержать эйлеров цикл (все вершины для этого должны
иметь четную степень), но содержит эйлерову цепь, так как выполнены условия существования эйлеровой цепи:
Для того чтобы гра содержал эйлерову цепь, необходимо и достаточно, чтобы он был связен и содержал ровно две вершины нечетной
степени.
Опишем алгоритм нахождения эйлеровой цепи. Для этого все ребра
57
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
в начале алгоритма считаем непомеченными, а по мере их включения
в маршрут будем делать пометки соответствующих ребер.
o
1
Выбираем в качестве начальной любую вершину нечетной степени (для определенности берем вершину с меньшим номером) и
делаем ее текущей.
o
2
Если из текущей вершины нет непройденных (непомеченных) ребер, то алгоритм закончен: все ребра пройдены и цепь составляем
в порядке их прохождения.
o
3
Из текущей вершины выбираем любое ребро (для определенности
ребро, ведущее в вершину с наименьшим номером).
o
4
Если оно не является перешейком (из текущей вершины есть
еще непройденные ребра, а при временной пометке данного ребра гра непомеченных ребер не содержит маршрута из текущей
вершины в другую вершину данного ребра), то выбираем его, помечаем и делаем текущей вершину смежную по этому ребру с
o
предыдущей смежной вершиной. Переходим к п. 2 .
o
5
Если выбранное на предыдущем шаге ребро является перешейком, то выбираем следующее ребро, ведущее из текущей верши-
o
ны, и переходим к п. 4 .
Выполнение алгоритма сводим в следующую таблицу.
N
f; g f; g f; g f; g f; g f; g f; g
1 3
1 4
1 6
2 3
2 5
3 5
4 6
0
1
1
+
4
2
+
3
4
5
I
+
6
1
+
3
+
6
2
+
7
5
+
3
Каждый столбец (кроме первого и последнего) отвечает ребру граа.
Для пометки ребра ставим над ним черту. В первом столбце отмечаем
номер шага выполнения алгоритма, а в последнем номер текущей
58
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины. Если рассматриваемое ребро является перешейком, то на
пересечении текущей строки выполнения алгоритма и столбца ребра
ставим минус. В противном случае ставим плюс, помечаем ребро и
заносим новую текущую вершину.
По окончании алгоритма столбец текущей вершины определит эйлерову цепь. На шаге 1 выполнения алгоритма ребро {1,3} является
перешейком, так как после его временного исключения не существует маршрута, связывающего вершины 1 и 3: компонента связности в
грае непомеченных ребер, содержащая вершину 1, содержит также
смежные с ней вершины 4 и 6, но никаких других вершин (в частности, вершины 3) не содержит.
В результате выполнения алгоритма получена следующая эйлерова
цепь:
; ; ; ; ; ; ; :
(1 4 6 1 3 2 5 3)
Пример 8.
2
66
66
66
66
66
64
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
3
77
77
77
77
77
75
Матрица смежности вершин кососимметрична, поэтому это оргра.
Определяем связность граа как неориентированного. Включаем в
компоненту связности
C1
вершину 1:
ны вершины 3 и 5, добавляем их:
C1
C1
=
f g. Вершине 1 смежf ; ; g. Вершинам 3 и 5
=
1
1 3 5
смежны вершины 6, 7, 8. Добавляем их в компоненту связности:
f
; ; ; ; ;
g
C1 =
1 3 5 6 7 8 . Вершинам 6 и 8 смежны вершины 2 и 4. Добавляем их
в компоненту связности:
C1
=
f
; ; ; ; ; ; ;
g
1 2 3 4 5 6 7 8 . Поскольку компо-
нента связности содержит все вершины граа, он связен как неориентированный.
Находим полустепени исхода и захода для каждой вершины и сравниваем их:
59
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
1.
d1
2.
d2
3.
d3
4.
d4
5.
d5
6.
d6
7.
d7
8.
d8
; d+1 = 1 ! d1
+
= 1; d2 = 1 ! d2
+
= 2; d3 = 2 ! d3
+
= 1; d4 = 1 ! d4
+
= 2; d5 = 2 ! d5
+
= 2; d6 = 2 ! d6
+
= 1; d7 = 1 ! d7
+
= 2; d8 = 2 ! d8
= 1
d+1
+
= d2
+
= d3
+
= d4
+
= d5
+
= d6
+
= d7
+
= d8
=
Из того, что оргра слабо связен (связен как неориентированный) и
для каждой вершины полустепень исхода и полустепень захода совпадают, следует, что оргра содержит эйлеров контур, так как выполнены условия существования эйлерова контура:
Для того чтобы оргра содержал эйлеров контур, необходимо и достаточно, чтобы он был слабо связен и для каждой вершины полустепени исхода и захода были бы равны.
Опишем алгоритм нахождения эйлерова контура. Для этого все
дуги в начале алгоритма считаем непомеченными, а по мере их включения в маршрут будем делать пометки соответствующих дуг.
o
1
Выбираем в качестве начальной любую вершину нечетной степени (для определенности берем вершину 1) и делаем ее текущей.
o
2
Если из текущей вершины нет непройденных (непомеченных) выходящих дуг, то алгоритм закончен: все дуги пройдены и контур
составляем в порядке их прохождения.
o
3
Из текущей вершины выбираем любую непомеченную выходящую дугу (для определенности дугу, ведущую в вершину с наименьшим номером).
o
4
Если она не является перешейком (из текущей вершины есть еще
непройденные выходящие дуги, а при временной пометке данной
дуги из ее конечной вершины не существует пути до текущей
60
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
вершины в орграе непомеченных дуг), то выбираем ее, помечаем и делаем текущей конечную вершину этой дуги. Переходим к
o:
п. 2
o
5
Если выбранная на предыдущем шаге дуга является перешейком, то выбираем следующую непомеченную выходящую дугу из
o
текущей вершины, помечаем ее и переходим к п. 4 .
Выполнение алгоритма сводим в следующую таблицу.
N
;
1 5
;
2 6
;
3 1
;
3 5
;
4 6
;
5 7
;
5 8
;
6 3
;
6 8
;
7 3
;
8 2
;
8 4
0
1
1
+
5
2
+
7
3
+
4
5
+
8
6
+
2
+
6
8
+
9
8
+
10
+
4
6
11
12
3
+
5
7
I
+
+
3
1
Каждый столбец (кроме первого и последнего) отвечает дуге орграа. Для пометки дуги ставим над ней черту. В первом столбце отмечаем номер шага выполнения алгоритма, а в последнем номер
текущей вершины. Если рассматриваемая дуга является перешейком,
то на пересечении текущей строки выполнения алгоритма и столбца
дуги ставим минус. В противном случае ставим плюс, помечаем дугу
и заносим новую текущую вершину. По окончании алгоритма столбец
текущей вершины определит эйлеров контур. Отметим, что на шаге
4 выполнения алгоритма дуга (3,1) является перешейком, так как из
вершины 1 нет уже выходящих непомеченных дуг, а потому нет пути
до вершины 3 в грае непомеченных дуг. На шаге 8 выполнения алгоритма дуга (6,3) также является перешейком, так как из вершины
3 можно достигнуть только вершины 1 в грае непомеченных дуг, но
никак не вершины 6.
61
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
В результате выполнения алгоритма получен следующий эйлеров
контур:
; ; ; ; ; ; ; ; ; ; ; ; :
(1 5 7 3 5 8 2 6 8 4 6 3 1)
14
Индивидуальное задание 7
14.1 Общее задание
1. Для граа, заданного списком ребер с их длинами, найти кратчайший маршрут из первой вершины граа (с номером 1) в последнюю вершину (с наибольшим номером):
a) описать алгоритм Дейкстры нахождения кратчайшего маршрута
в грае с пояснением всех вводимых в алгоритме обозначений;
b) свести выполнение алгоритма для заданного граа в таблицу;
) построить реализацию граа с указанием длин ребер и выделением жирными ребрами найденного кратчайшего маршрута.
2. Для граа (или орграа), заданного матрицей смежности вершин, найти эйлеров маршрут (цикл, контур, цепь, путь):
a) анализировать гра на существование эйлерова маршрута (цикла, контура, цепи, пути), сормулировав соответствующий критерий существования;
b) описать алгоритм нахождения эйлерова маршрута (цикла или
контура, цепи, пути);
) свести выполнение алгоритма для заданного граа в таблицу;
d) выписать полученный маршрут в качестве результата.
14.2 Варианты индивидуального задания 7
Задача 1
1. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({2,3}, 1), ({2,5}, 2), ({2,6}, 4),
({3,4}, 1), ({3,6}, 2), ({4,6}, 3), ({4,7}, 6), ({5,6}, 2), ({5,8}, 7),
({6,7}, 3), ({6,8}, 6), ({7,8}, 2) ).
62
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2. ( ({1,2}, 2), ({1,3}, 6), ({1,4}, 5), ({2,3}, 4), ({2,5}, 1), ({3,4}, 1),
({3,5}, 2), ({3,6}, 2), ({3,7}, 1), ({4,7}, 1), ({5,6}, 4), ({5,8}, 6),
({6,7}, 1), ({6,8}, 2), ({7,8}, 2) ).
3. ( ({1,2}, 1), ({1,3}, 4), ({1,4}, 7), ({1,5}, 4), ({2,5}, 2), ({3,7}, 4),
({4,6}, 1), ({4,7}, 1), ({5,6}, 2), ({5,8}, 6), ({6,8}, 4), ({7,8}, 1) ).
4. ( ({1,2}, 1), ({1,3}, 4), ({1,4}, 3), ({2,3}, 2), ({2,5}, 4), ({3,5}, 1),
({3,6}, 4), ({4,6}, 4), ({4,7}, 5), ({5,6}, 2), ({5,8}, 6), ({6,7}, 1),
({6,8}, 4), ({7,8}, 2) ).
5. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({2,3}, 1), ({2,5}, 3), ({2,6}, 5),
({3,4}, 1), ({3,7}, 2), ({4,5}, 2), ({4,7}, 3), ({5,8}, 4), ({6,7}, 1),
({6,8}, 2), ({7,8}, 4) ).
6. ( ({1,2}, 2), ({1,3}, 2), ({1,4}, 4), ({2,3}, 1), ({2,5}, 5), ({2,6}, 4),
({3,4}, 1), ({3,6}, 4), ({4,6}, 2), ({4,7}, 4), ({5,6}, 1), ({5,8}, 3),
({6,7}, 1), ({6,8}, 4), ({7,8}, 2) ).
7. ( ({1,2}, 3), ({1,3}, 4), ({1,4}, 2), ({2,3}, 1), ({2,5}, 3), ({3,4}, 1),
({3,5}, 2), ({3,6}, 4), ({3,7}, 2), ({4,7}, 3), ({5,6}, 1), ({5,8}, 4),
({6,7}, 2), ({6,8}, 2), ({7,8}, 4) ).
8. ( ({1,2}, 2), ({1,3}, 4), ({1,4}, 3), ({1,5}, 3), ({2,3}, 1), ({2,6}, 4),
({3,6}, 3), ({3,7}, 2), ({4,8}, 4), ({5,7}, 3), ({6,9}, 3), ({7,8}, 1),
({7,9}, 4) ({8,9}, 2) ).
9. ( ({1,2}, 1), ({1,3}, 2), ({1,4}, 2), ({1,5}, 7), ({2,6}, 2), ({3,6}, 1),
({3,7}, 2), ({4,7}, 1), ({5,8}, 2), ({5,9}, 2), ({6,7}, 1), ({6,9}, 6),
({7,8}, 1) ({7,9}, 6), ({8,9}, 5) ).
10. ( ({1,2}, 3), ({1,3}, 2), ({1,4}, 4), ({1,5}, 6), ({2,7}, 4), ({3,6}, 3),
({3,8}, 1), ({4,7}, 3), ({5,7}, 1), ({5,8}, 2), ({6,9}, 4), ({7,9}, 2)
({8,9}, 6) ).
11. ( ({1,5}, 2), ({1,6}, 4), ({1,7}, 3), ({2,3}, 2), ({2,5}, 2), ({2,8}, 7),
({3,4}, 3), ({3,5}, 4), ({3,6}, 2), ({3,7}, 3), ({3,8}, 6), ({4,7}, 6),
({4,8}, 2), ({5,6}, 1), ({6,7}, 1) ).
12. ( ({1,5}, 6), ({1,6}, 2), ({1,7}, 5), ({2,3}, 4), ({2,4}, 1), ({2,5}, 2),
({2,8}, 2), ({3,5}, 2), ({3,6}, 1), ({3,8}, 6), ({4,5}, 1), ({4,7}, 1),
({4,8}, 2), ({5,6}, 4), ({5,7}, 1) ).
63
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
13. ( ({1,4}, 4), ({1,5}, 7), ({1,6}, 4), ({1,7}, 1), ({2,5}, 1), ({2,6}, 4),
({2,8}, 1), ({3,4}, 2), ({3,5}, 1), ({3,8}, 4), ({4,7}, 2), ({4,8}, 6) ).
14. ( ({1,5}, 3), ({1,6}, 1), ({1,7}, 4), ({2,3}, 1), ({2,4}, 2), ({2,5}, 4),
({2,7}, 4), ({2,8}, 4), ({3,5}, 5), ({3,8}, 2), ({4,6}, 4), ({4,7}, 1),
({4,8}, 6), ({6,7}, 2) ).
15. ( ({1,2}, 4), ({1,3}, 2), ({1,5}, 3), ({2,3}, 1), ({2,5}, 1), ({2,6}, 2),
({3,4}, 3), ({3,7}, 5), ({4,5}, 2), ({4,8}, 4), ({5,6}, 3), ({6,7}, 1),
({6,8}, 4), ({7,8}, 2) ).
16. ( ({1,5}, 2), ({1,6}, 4), ({1,7}, 2), ({2,4}, 1), ({2,5}, 5), ({2,8}, 3),
({3,4}, 1), ({3,6}, 4), ({3,8}, 2) ({4,5}, 4), ({4,6}, 2), ({4,7}, 4),
({4,8}, 4), ({5,7}, 1), ({6,7}, 1) ).
17. ( ({1,2}, 2), ({1,4}, 3), ({1,6}, 4), ({2,5}, 3), ({2,6}, 1), ({3,5}, 2),
({3,6}, 4), ({3,7}, 1), ({3,8}, 2), ({4,6}, 1), ({4,7}, 3), ({5,6}, 2),
({5,8}, 4), ({6,7}, 2), ({7,8}, 4) ).
18. ( ({1,3}, 3), ({1,4}, 4), ({1,6}, 2), ({1,8}, 3), ({2,6}, 4), ({2,4}, 3),
({2,9}, 3), ({3,5}, 4), ({4,6}, 1), ({4,7}, 2), ({5,7}, 1), ({5,9}, 2)
({7,8}, 3), ({7,9}, 4) ).
19. ( ({1,2}, 2), ({1,3}, 1), ({1,4}, 7), ({1,5}, 2), ({2,7}, 2), ({2,8}, 1),
({3,8}, 2), ({4,6}, 2), ({4,9}, 2), ({5,7}, 1), ({6,7}, 1), ({6,9}, 5)
({7,8}, 1), ({7,9}, 6), ({8,9}, 6) ).
20. ( ({1,2}, 4), ({1,3}, 6), ({1,4}, 3), ({1,5}, 2), ({2,7}, 3), ({3,6}, 2),
({3,7}, 1), ({4,7}, 4), ({5,6}, 1), ({5,8}, 3), ({6,9}, 6), ({7,9}, 2)
({8,9}, 4) ).
21. ( ({1,5}, 7), ({1,6}, 6), ({1,7}, 2), ({2,3}, 1), ({2,5}, 2)
Документ
Категория
Без категории
Просмотров
9
Размер файла
656 Кб
Теги
элементы, маршрут, графов, 704, рублев, изоморфизм, теория, планарность, графах
1/--страниц
Пожаловаться на содержимое документа