Основные понятия теории графов. Гладких О.Б - 41 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

136
дов в вершину. Далее определим частичную под-
становку, соединяя вершины x
i
; и у
i
, с одинаковы-
ми числами (рис. 5.13).
x
1
(1, 1) х
2
(1, 1) х
3
(3, 2) х
4
(1, 2) х
5
(2, 2) х
6
(2, 2) х
7
(1, 1)
y
1
(2, 2) y
2
(1, 1) y
3
(2, 2) у
4
(1, 1) y
5
(1, 2) y
6
(1, 1) y
7
(3, 2)
Рис. 5.13.
В результате получим подстановку
1234567
4275316
x
xxxxxx
yyyyyyy
⎛⎞
⎜⎟
⎝⎠
Следовательно, графы С
1
и С
2
изоморфны.
Задача 5.11.
Для неориентированного графа, изображен-
ного на рис. 5.14, постройте матрицу смежности и
матрицу инцидентности.
41
где G
–1
(x
4
) – прообраз вершины x
4
.
G
–1
(x
4
) = {x
2
, x
3
, x
5
}.
Подставим в (4) последовательно r = 2, r = 3 и r = 5,
чтобы определить, для какого r это равенство вы-
полняется:
λ
2
(2) + c
24
= 1 + 7 ≠
λ
4
(3) = 6,
λ
3
(2) + c
34
= 1 + 1 ≠
λ
4
(3) = 6,
λ
5
(2) + c
54
= 2 + 4 =
λ
4
(3) = 6,
Таким образом, вершиной, предшествующей
вершине x
4
, является вершина x
5
.
Для вершины x
5
предшествующая ей верши-
на x
r
определяется из соотношения (2) полученно-
го при s = 5:
λ
r
(1) + c
r5
=
λ
5
(2), x
r
∈
G
–1
(x
5
), (5)
где G
–1
(x
5
) – прообраз вершины x
5
.
G
–1
(x
5
) = {x
1
, x
2
}.
Подставим в (5) последовательно r = 1 и r = 2, что-
бы определить, для какого r это равенство выпол-
няется:
λ
1
(1) + c
15
= 0 + 3 ≠
λ
5
(2) = 2,
λ
2
(1) + c
25
= 1 + 1 =
λ
5
(2) = 2,
Таким образом, вершиной, предшествующей
вершине x
5
, является вершина x
2
.
Для вершины x
2
предшествующая ей верши-
на x
r
определяется из соотношения (2) полученно-
го при s =2: 
дов в вершину. Далее определим частичную под-                    где G –1(x4) – прообраз вершины x4.
становку, соединяя вершины xi; и уi, с одинаковы-                                 G –1(x4) = {x2, x3, x5}.
ми числами (рис. 5.13).                                          Подставим в (4) последовательно r = 2, r = 3 и r = 5,
x1(1, 1) х2(1, 1) х3(3, 2) х4(1, 2) х5(2, 2) х6(2, 2) х7(1, 1)   чтобы определить, для какого r это равенство вы-
                                                                 полняется:
                                                                            λ2 (2) + c24 = 1 + 7 ≠ λ4 (3) = 6,
                                                                            λ3 (2) + c34 = 1 + 1 ≠ λ4 (3) = 6,
                                                                            λ5 (2) + c54 = 2 + 4 = λ4 (3) = 6,
y1(2, 2) y2(1, 1) y3(2, 2) у4(1, 1) y5(1, 2) y6(1, 1) y7(3, 2)
                                                                       Таким образом, вершиной, предшествующей
                             Рис. 5.13.                          вершине x4, является вершина x5.
В результате получим подстановку                                       Для вершины x5 предшествующая ей верши-
                                                                 на xr определяется из соотношения (2) полученно-
                 ⎛ x1   x2   x3   x4    x5   x6   x7 ⎞
                 ⎜y                                              го при s = 5:
                 ⎝ 4    y2   y7   y5    y3   y1   y6 ⎟⎠
                                                                         λr (1) + cr5 = λ5 (2), xr ∈ G –1(x5), (5)
Следовательно, графы С1 и С2 изоморфны.                          где G –1(x5) – прообраз вершины x5.
                                                                                     G –1(x5) = {x1, x2}.
                         Задача 5.11.
                                                                 Подставим в (5) последовательно r = 1 и r = 2, что-
      Для неориентированного графа, изображен-
                                                                 бы определить, для какого r это равенство выпол-
ного на рис. 5.14, постройте матрицу смежности и
                                                                 няется:
матрицу инцидентности.
                                                                          λ1 (1) + c15 = 0 + 3 ≠ λ5 (2) = 2,
                                                                          λ2 (1) + c25 = 1 + 1 = λ5 (2) = 2,
                                                                       Таким образом, вершиной, предшествующей
                                                                 вершине x5, является вершина x2.
                                                                       Для вершины x2 предшествующая ей верши-
                                                                 на xr определяется из соотношения (2) полученно-
                                                                 го при s =2:


                                       136                                                      41

Страницы