9957
.pdf
130
|
|
(y2,y3) |
(x1y2)→(x1y3) |
(z2,z3) |
|
|
(y3,y1) |
(x1y3)→(x1y1) |
(z3,z1) |
2 |
z4=(x2y1), z5=(x2y2), z6=(x2y3) |
(y1,y1) |
(x2y1)→(x2y1) |
(z4,z4) |
|
|
(y1,y2) |
(x2y1)→(x2y2) |
(z4,z5) |
|
|
(y2,y3) |
(x2y2)→(x2y3) |
(z5,z6) |
|
|
(y3,y1) |
(x2y3)→(x2y1) |
(z6,z4) |
3 |
z1=(x1y1), z4=(x2y1) |
(x1,x2) |
(x1y1)→(x2y1) |
(z1,z4) |
|
|
(x2,x1) |
(x2y1)→(x1y1) |
(z4,z1) |
4 |
z2=(x1y2), z5=(x2y2) |
(x1,x2) |
(x1y2)→(x2y2) |
(z2,z5) |
|
|
(x2,x1) |
(x1y2)→(x1y2) |
(z5,z2) |
5 |
Z3=(x1y3), z6=(x2y3) |
(x1,x2) |
(x1y3)→(x2y3) |
(z3,z6) |
|
|
(x2,x1) |
(x2y3)→(x1y3) |
(z6,z3) |
Рис. 3.39. Произведение графов G1 × G2
Граф считается полностью заданным в строгом смысле, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин и ребер, называются изомофными.
Определение 8. Два графа G1 (V1, E1 ) и G2 (V2 , E2 ) называются
изоморфными, если существует биекция (взаимно однозначное отображение) ϕ
множества V1 на множество V2 такое, что для любых двух вершин a V1 , b V2 (a,b) E1 (ϕ (a),ϕ (b)) E2 .
Тот факт, что графы G1 и G2 изоморфны, записывается следующим
образом: G1 G2 .
Некоторые свойства изоморфизма графов:
1)число ребер и число вершин у изоморфных графов должно быть одинаковым;
2)при всяком изоморфизме графов G1 и G2 соответствующие друг другу вершины должны иметь одинаковую степень.
131
Например, все три графа на рисунке 3.40 изоморфны друг другу (изоморфизм
определяется нумерацией вершин).
Рис. 3.40. Изоморфные графы
На рисунках 3.41 представлены попарно неизоморфные графы.
Рис. 3.41. Неизоморфные графы
В общем случае узнать, изоморфны ли два графа, достаточно сложно.
Однако для многих графов их неизоморфность устанавливается на основе инвариантов. Инварианты – это характеристики графов, которые сохраняются при изоморфизме. Некоторые простые инварианты: число ребер, набор степеней, число циклов заданной длины. Если удается установить, что для двух исследуемых графов некоторый инвариант принимает разные значения, то эти графы неизоморфны.
G1 |
G2 |
G3 |
G4 |
Рис 3.42.
132
Пример 3.18. Распознавание изоморфизма неориентированных графов
(рис.3.42) с помощью анализа вектора степеней.
Так как при изоморфизме пара смежных вершин переходит в пару смежных, а пара несмежных вершин в пару несмежных, то число ребер у двух изоморфных графов должно быть одинаковым. Поэтому графы G1 и G2 на рисунке 3.42, у которых разное количество ребер неизоморфны. У графов G1 и G3 одинаковое число ребер, но они тоже неизоморфны. Это можно установить,
сравнивая степени вершин. При изоморфизме каждая вершина переходит в вершину той же степени. Но если выписать степени всех вершин G1 в
неубывающем порядке, то получиться последовательность (2,2,3,3,3,3), а для графа G3 получиться последовательность (2,2,2,3,3,4). Так как последовательности различные, то значит, графы неизоморфны.
Для графов G1 и G4 наборы степеней одинаковы, но в G4 есть цикл длины 3, а в графе G1 такого цикла нет, следовательно, графы неизоморфны. ■
Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным. Для изоморфизма двух n-вершинных графов само определение этого отношения дает способ проверки: надо просмотреть все n!
взаимно однозначных соответствий между множествами вершин и установить,
совмещаются ли полностью ребра графа хотя бы при одном соответствии.
Однако даже весьма грубая оценка показывает, что такое решение задачи "в
лоб" практически непригодно: уже при n=20 перебор всех n! вариантов потребовал бы около 40 лет машинного времени.
Теорема 3. Два графа изоморфны между собой тогда и только тогда,
когда матрицу смежности одного из них можно получить из матрицы смежности другого с помощью одновременной перестановки строк и столбцов этой матрицы (т.е. одновременно с перестановкой i– той и j– той строк матрицы осуществляется и перестановка i– того и j– того столбцов матрицы).
Теорема 4. Два графа изоморфны между собой тогда и только тогда,
когда матрицу инцидентности одного из них можно получить из матрицы
133
инцидентности другого с помощью перестановок строк и столбцов этой матрицы.
Пример 3.19. На рисунке 3.43 изображены два графа G1 и G2 с одним и тем же множеством вершин {a, b, c, d}.
Рис. 3.43
Это разные графы, так как в графе G1 есть ребро (a, c), а в графе G2 нет.
Но G1 G2 , |
так как изоморфизмом, |
например, |
является отображение, |
||||||||||||
заданное в таблице: |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
х (вершина графа G1) |
a |
b |
|
c |
d |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
ϕ (х) (вершина графа G2 ) |
a |
b |
|
d |
c |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||
Доказательство изоморфизма графов на рис.3.43: |
|
|
|
|
|
|
|||||||||
Рассмотрим цепочку преобразований, переводящую матрицу смежности |
|||||||||||||||
графа G2 в матрицу смежности графа G1: |
|
|
|
|
|
|
|
|
|
|
|||||
|
0 1 |
0 |
1 |
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
|
s(G2 ) = |
|
|
¾¾¾¾¾¾® |
|
|
|
||||||||
|
|
1 |
|
поменяли местами строки 3 |
и 4 |
|
0 |
1 |
|
||||||
|
1 0 |
0 |
|
|
|
|
|
|
|
|
1 |
0 |
|||
|
0 1 |
0 |
1 |
|
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
|
1 0 |
0 |
|
|
|
|
|
|
|
|
0 |
1 |
|||
|
|
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
¾¾¾¾¾¾® |
|
|
|
= S (G1) |
||
поменяли местами столбцы 3 |
и 4 |
1 |
0 |
0 |
1 |
|
|
|
|||||
|
|
1 |
0 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
|
|
|
0 |
|
|||
134
Задачи.
1. Постройте полный граф и дополнение для данных двух графов.
|
Граф G1 |
|
Граф G2 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2.Найдите объединение, пересечение, разность и произведение двух графов.
а) |
б) |
в)
3. Составьте матрицы смежности для графов G1 , G2 , G1ÈG2, G1ÇG2, если
1 |
2 |
3 |
4 |
5 |
|
|
2 |
3 |
4 |
5 |
6 |
|
||||||||||||||
1 |
|
|
|
0 |
0 |
1 |
0 |
1 |
|
|
|
2 |
|
|
|
0 |
1 |
|
1 |
0 |
0 |
|
|
|
||
|
|
|
|
|
|
|
|
|
||||||||||||||||||
2 |
|
|
|
0 |
0 |
1 |
0 |
0 |
|
|
|
3 |
|
|
|
1 |
|
0 |
1 |
0 |
1 |
|
|
|
||
а) A(G1 ) = 3 |
|
|
|
1 |
1 |
0 1 |
1 |
|
|
|
A(G2 ) = 4 |
|
|
|
1 |
1 |
0 1 |
1 |
|
|
|
|||||
4 |
|
|
|
0 |
0 |
1 |
0 |
1 |
|
|
|
5 |
|
|
|
0 |
0 |
1 |
0 |
1 |
|
|
|
|||
5 |
|
|
|
1 |
0 |
1 |
1 |
0 |
|
|
|
6 |
|
|
|
0 |
1 |
|
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
135
1 |
2 |
|
3 |
4 |
5 |
|
|
|
|
|
2 |
3 |
5 |
|
6 |
7 |
||||||||||
1 |
|
|
|
0 |
1 |
|
1 |
1 |
1 |
|
2 |
|
|
|
0 |
1 |
|
1 |
0 |
1 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||||||||||||||||||
2 |
|
|
|
1 |
|
0 |
1 |
1 |
0 |
|
3 |
|
|
|
1 |
0 |
|
1 |
0 |
1 |
|
|
|
|
||
б) A(G1 ) = 3 |
|
|
|
1 |
1 |
0 1 |
0 |
|
A(G2 ) = 5 |
|
|
|
1 |
1 |
0 1 |
0 |
|
|
|
|
||||||
4 |
|
|
|
1 |
|
1 |
|
1 |
0 |
0 |
|
6 |
|
|
|
0 |
0 |
|
1 |
0 |
1 |
|
|
|
|
|
5 |
|
|
|
1 |
|
0 |
0 |
0 |
0 |
|
7 |
|
|
|
1 |
1 |
|
0 |
1 |
|
0 |
|
|
|
|
|
4. Найдите объединение, пересечение, разность и произведение двух графов
1) |
2) |
3) |
4) |
5) |
6) |
7) |
8) |
9) |
10) |
|
136 |
|
|
|
|
11) |
|
12) |
|
|
|
13) |
|
14) |
|
|
|
15) |
|
16) |
|
|
|
17) |
|
18) |
|
|
|
19) |
|
20) |
|
|
|
21) |
|
22) |
|
|
|
23) |
|
24) |
|
|
|
25) |
|
|
|
|
|
137
5.Графы, изображенные на рис.3.44 а) и б) изоморфны, но они не изоморфны графу на рис. 3.44 в). Почему?
Рис. 3.44
6. Изоморфны ли данные графы? Ответ обоснуйте.
а) G1 |
G2 |
|
|
|
|
б) H1 |
H2 |
в) G3 |
G4 |
г) H3 |
H4 |
138
3.3. Маршруты, цепи и циклы в графах. Связные графы.
Метрические соотношения.
Маршрут в графе G(V,E) – это чередующаяся последовательность вершин и рёбер v1, e1, v2 , e2 ,…, vn , en , в которой любые два соседних элемента инцидентны.
Очевидно следующее свойство маршрута: любые два последовательных ребра либо смежные, либо одинаковые.
Говорят, что маршрут соединяет вершины v1 и vn , которые называются соответственно началом и концом маршрута. Вершины v2 ,…, vn−1 называются
промежуточными. Маршрут называется замкнутым или циклическим, если v1 = vn , иначе маршрут называется открытым.
Длиной маршрута называется число ребер в нем. Для любой вершины vi тривиальным маршрутом, вообще не содержащим ребер, является маршрут из vi в vi .
На рис.3.45 можно выделить маршрут из v в w: v→w→x→y→z→z→y→w. Он имеет длину,
равную семи.
Рис.3.45
Примеры маршрутов в графе на рис. 3.46, следуя которым можно попасть из A1 в A5 :
1)( A1 , A4 ), ( A4 , A5 );
2)( A1 , A2 ), ( A2 , A4 ), ( A4 , A5 );
Рис.3.46.
3) ( A1 , A4 ), ( A4 , A2 ), ( A2 , A1 ), ( A1 , A4 ), ( A4 , A5 )
139
В одних маршрутах ребра повторяются, в других нет. Можно указать маршрут от A1 до A5 , содержащий все вершины графа. Таков, например, маршрут: ( A1 , A2 ), ( A2 , A4 ), ( A4 , A3 ), ( A3 , A1 ), ( A1 , A4 ), ( A4 , A5 ).
Маршрут, в котором все ребра разные, называется цепью. Из определения следует, что последовательность ребер (3) (рис. 3.46) не является цепью в графе. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, называется простой цепью.
Цикл – это замкнутая цепь. Простым циклом в графе называется цикл,
не проходящий ни через одну из вершин графа более одного раза.
Граф, не содержащий циклов, называется ациклическим.
Приведем доказательства некоторых простых свойств маршрутов, цепей и циклов.
Свойство 1. Пусть G – некоторый граф. Тогда любой маршрут,
соединяющий две различные вершины, содержит простую цепь, соединяющую
те же вершины, а любой цикл содержит простой цикл.
Доказательство. Пусть x1, x2 ,…, xn – маршрут. Если все его вершины
различны, то это уже простая цепь. В противном случае, пусть xi = x j , |
i < j , |
|
тогда последовательность x1, x2 ,…, xi−1, xi , x j+1,…, xn , |
полученная из |
этого |
маршрута удалением отрезка последовательности от xi +1 |
до x j , тоже является |
|
маршрутом. Новый маршрут соединяет те же вершины и имеет меньшую длину. Продолжая действовать таким образом, после конечного числа
«спрямлений» получим простую цепь, соединяющую x1 и xn .■
Свойство 2. Во всяком цикле, проходящем через некоторое ребро,
содержится простой цикл, проходящий через это ребро.
Доказательство. Пусть |
имеется цикл, проходящий через ребро (a,b). |
|
Если удалить это ребро из |
графа, |
то в полученном подграфе останется |
маршрут, соединяющий a и |
b. По |
свойству 1 существует простой путь |
x1, x2 ,…, xn , соединяющий эти вершины, то есть пара (a,b) совпадает с парой