Математическое моделирование на графах. Часть 1. Берцун В.Н. - 18 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

18 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Доказательство. Пусть множества вершин V
i
и V
j
определяют
две различные компоненты связности. Тогда нет цепи (пути) из вер-
шины x
i
∈V
i
в вершину x
j
∈V
j
, а это противоречит связности графа. ■
1.5. Изоморфизм графов
Как уже отмечалось, один и тот же граф на рисунках может вы-
глядеть по-разному. Например, на рис. 1.20 изображен один и тот же
граф [15, 16].
Рис. 1.20
Говорят, что два графа G
1
(V
1
,E
1
) и G
2
(V
2
,E
2
) изоморфны (G
1
~ G
2
),
если существует биекция (взаимно-однозначное отображение) f :
V
1
→ V
2
, сохраняющая смежность [16]:
е
1
= (а, в) ∈ E
1
⇒ е
2
= (f (а), f (в)) ∈ E
2
,
е
2
= (а, в) ∈ E
2
⇒ е
1
= (f
–1
(а), f
–1
(в)) ∈ E
1
.
Изоморфизм графов есть отношение эквивалентности, так как он
обладает свойствами: рефлексивности (G
1
~ G
1
); симметричности
(если G
1
~ G
2
, то G
2
~ G
1
); транзитивности (если G
1
~ G
2
и G
2
~ G
3
,
то G
1
~ G
3
). Понятие изоморфизма для графов имеет наглядное тол-
кование. Допустим, что рёбра графов являются эластичными нитя-
ми, связывающими узлы – вершины. Тогда изоморфизм можно
представить как перемещение узлов и растяжение нитей. Очевидно,
что два графа являются изоморфными, если они отличаются лишь
идентификацией своих вершин. Например, на рис. 1.21 приведены
два графа G и G
1
, изоморфизм которых определяется изоморфной
подстановкой [17]
1
165432
ABCDE F
f
⎛⎞
=
⎜⎟
⎝⎠
.

Страницы