ВУЗ:
Составители:
70
Число внешней устойчивости β(G). Множество внешней устой-
чивости Т
⊂
Х графа G=<X,Г> называют внешне устойчивым, если
любая вершина, не принадлежащее Т, соединена дугами с вершинами
из Т, т.е. для любого x
∉
Т имеет место Г(x)
∩
Т
≠∅
.
Множество внешней устойчивости, содержащее наименьшее
число элементов, называется наименьшим внешне устойчивым мно-
жеством, а число элементов этого множества называют числом
внешней устойчивости графа G. Примеры внешне устойчивых мно-
жеств для G на рис. 2.36
T
1
={1, 3, 4,}; T
2
={2, 3, 5}; T
3
={1, 3, 4}; T
4
={1, 3, 5}; T
5
={1, 2, 3, 4,
5}. Следовательно,
β
(G)=3.
Числом вершинной связности
λ
(G) называют наименьшее коли-
чество вершин графа G, удаление которых приводит к несвязному
графу или к тривиальному графу (т.е. графу, состоящему из одной
вершины).
Для определенных классов графов имеются и другие числовые
характеристики, например, для деревьев характерны древесность,
толщина и др. При решении задач теории графов часто возникает
необходимость изучения взаимосвязи
различных характеристик.
Изоморфизм графов. Граф называют перенумерованным (поме-
ченным), если его вершины отличаются одна от другой какими-либо
пометками. Выше мы каждую вершину помечали либо цифрой, либо
прописной буквой, либо прописной буквой с индексом. Два графа G
и H изоморфны (G≅H), если между их множествами вершин сущест-
вует взаимно
однозначное соответствие, сохраняющее смежность.
Например, граф G
1
на рис. 2.37 изоморфен графу G
2
при соот-
ветствии v
i
↔
u
i
, и каждый из них изоморфен графу G
3
при любой его
разметке, а все они изоморфны G
4
.
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
