ВУЗ:
Составители:
Рубрика:
9
Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается
сложным. Очевидно, что отношение изоморфизма графов является
эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно.
Следовательно, множество всех графов разбивается на классы так, что графы из
одного класса попарно изоморфны, а графы из разных классов не изоморфны.
Изоморфные
графы естественно отождествлять, т.е. считать совпадающими и
изображать одним рисунком. В некоторых ситуациях приходится различать
изоморфные графы и тогда вводится понятие «помеченный граф». Граф порядка n
называется помеченным, если его вершинам присвоены некоторые метки.
Например, номера 1,2,…,n. Отождествив каждую из вершин графа с ее номером,
определим равенство помеченных графов G и Н
одного и того же порядка условием:
G=Н тогда, когда EG=ЕН. На рис. 5 изображены два равных помеченных графа. На
рис. 10 изображены три разных помеченных графа. Чтобы подчеркнуть, что
рассматриваемые графы различаются с точностью до изоморфизма, говорят:
«абстрактный граф».
Рис. 10
Справедливо утверждение: число l
n
помеченных графов порядка n равно 2
С
2
n
.
Дополнительным графом (или дополнением)
G для произвольного графа G
называется граф с теми же вершинами, что и G, и с теми и только теми ребрами,
которые необходимо добавить к графу G, чтобы получился полный граф. На рис. 11
изображен граф G (слева) и дополнительный к нему (справа).
Рис. 11
Очевидно, что
G =G и
HG ≅
, если G
≅
Н. Граф, изоморфный своему дополнению,
называется
самодополнительным. Иногда приходится рассматривать более общие
объекты, чем определенный выше граф, в которых две вершины могут соединяться
более чем одним ребром.
Мультиграф – это пара (V,E), где V – непустое
множество (вершин), а Е – семейство подмножества V
(2)
(ребер). В этом
определении допускается существование кратных ребер. Дальнейшее обобщение
состоит в том, что кроме кратных ребер допускаются еще
петли, т.е. ребра,
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
