Основы синтеза и диагностирования автоматов. Воронин В.В. - 75 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

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

Рубрика: 

71
Приведем еще один простейший пример изоморфных графов.
На рис. 2.38 графы G
1
, G
2
и G
3
изоморфны при любой разметке их
вершин. Можно убедиться в
том, что свойство изомор-
физма есть отношение экви-
валентности на графах.
С числовыми характеристиками и изоморфизмом графа связано
понятие инварианта. Инвариант данного графа G - это число, кото-
рое принимает одно и тоже значение на любом графе, изоморфном
G. Так, число вершин
n и число дуг m являются инвариантами. Пол-
ный набор инвариантов
определяет граф с точ-
ностью до изоморфизма.
Например, числа n и m
образуют полный набор инвариантов для всех графов с числом вер-
шин, меньшим четырёх. Например, для n=3 и m=1 имеем полный на-
бор из трех изоморфных графов, представленный на рис. 2.39
.
G
1
v
1
v
2
v
3
v
4
v
5
v
6
u
2
u
6
u
5
u
3
u
1
u
4
G
2
G
3
u
6
u
3
u
5
u
4
u
1
u
2
G
4
Рис. 2.37
Рис. 2.38
G
1
G
2
G
3
Рис. 2.39

Страницы