Элементы теории графов. Сюсюкалов А.И - 11 стр.

UptoLike

ВУЗ: 

РГРТУ | Рязань

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

Рубрика: 

7
рёбрам. Если
i
v ,
k
v – смежные вершины, то столбец
ki
vv ,
содержит 1 в строках
i
v ,
k
v . Остальные элементы матрицы рав-
ны нулю.
Граф
G
, имеющий
n
вершин, представляется матрицей
размером
n
n
, называемой матрицей смежности. Её строки и
столбцы соответствуют вершинам. Элемент матрицы, стоящий
на пересечении строки
i
v и столбца
j
v , равен 1, если существу-
ет ребро
ji
vv , . Остальные элементы матрицы равны нулю.
Определение 1.23. Графы
111
, EVG ,
222
, EVG на-
зываются изоморфными, если между ними существует взаимно-
однозначное отображение
:
212121
, EEVVGG , ко-
торое сохраняет соответствие между рёбрами графов, т.е. для
любого ребра
uve , графа
1
G верно
uvee
,
,
где
e
– ребро
2
G .
Таким образом, изоморфные графы различаются только
обозначениями. К сожалению, установить изоморфизм доста-
точно трудно, что показывает следующий пример. На рис. 5
изображены два изоморфных графа. Одно из возможных изо-
морфных отображений:
31
uv ,
52
uv ,
63
uv ,
74
uv ,
25
uv ,
16
uv ,
47
uv ,
98
uv ,
89
uv ,
1010
uv .

Страницы