Дискретная математика. Никищенков С.А - 16 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

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

Рубрика: 

Все вершины полного двудольного графа
21
,nn
K , принадлежащие подмножествам
V
1
, и V
2
, попарно соединены ребрами (дугами).
Граф, вершина v
i
которого имеет степень ρ
(
v
i
)=n–1, а остальные – ρ
(
v
i
)=1,
называется звёздным (рис. 23,б).
Граф с обозначенными (пронумерованными) вершинами называется
помеченным. Пометка служит не только для идентификации вершин и дуг, но может
также задавать семантику предметной области.
Примером помеченного графа является граф переходов конечного автомата,
вершины которого интерпретируются внутренними, а дуги – входными (выходными)
состояниями автомата.
Граф, каждой вершине которого
сопоставлен вес c
i
, называется графом со
взвешенными вершинами.
Граф, каждому ребру которого e
j
сопоставлен вес c
i
, называется графом со
взвешенными ребрами.
Полностью взвешенный граф имеет все вершины и дуги (ребра) взвешенными.
Веса вершин и дуг имеют количественную меру.
Понятие "вес" интерпретируется в зависимости от контекста задачи. Например
для вершин, оно может означать стоимость обработки, потенциал, высоту и т.д., а для
дуг – стоимость транспортировки, величину тока,
расстояние и т.д. В задачах
многокритериальной оптимизации вершине и дуге может сопоставляться более чем один
вес.
2.6. Части, суграфы и подграфы
Части графа именуются в направлении усиления их свойств в следующей
последовательности: часть → суграф → нулевой суграф → покрывающий суграф →
остов → подграф (клика) → звездный подграф.
1.Граф
H является частью графа G (Н⊂ G), если вершины графа H включают в
себя вершины части G: V(H)
⊂
V(G) и E(H)
⊂
E(G). Примеры графа и его части приведены
на рис. 24,а, б.
2. Если множества вершин графа G и его части H совпадают: V(H)=V(G),то такая
часть графа называется суграфом (рис. 24,в). Если E(H)=∅, то суграф является
нулевым.
v v v
1
1
1
2
1
3
v v v
2
1
2
2
2
3
v
2
v
1
v
3
v
4
a) б)
Рис. 23

Страницы