Графы и сети. Харитонова Е.В. - 13 стр.

UptoLike

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

Рубрика:

● Если каждое ребро помечено, то говорят, что это размеченный ориен-

тированный или просто размеченный граф, с пониманием того, что это ориен-

тированный граф.

● Размеченный граф G = G(V, L, E) представляет собой множество вер-

шин V, множество меток L и множество E, которое является подмножеством V

× L

× V.

Таким образом, ребро e графа G имеет вид (a, l, b), где l – метка, а a, b –

вершины.

Графически ребро e = (a, l, b) размеченного графа обозначается, как на

рис. 1.18, или, как на рис. 1.19, если ребро – петля.

Рис. 1.18. Рис. 1.19.

Графы, представленные на рис. 1.20 и 1.21, являются примерами типич-

ных размеченных графов, называемых автоматами.

Рис. 1.20

Рис. 1.21

● Ориентированный граф G′(V′, E′) называется ориентированным под-

графом ориентированного графа G(V, E), обозначается G

′

(V′, E′) ≼ G(V, E), ес-

ли V′ ⊆ V, E′ ⊆ E.

Таким образом, каждая вершина в G′ является вершиной в G и каждое

ориентированное ребро в G′ является ориентированным ребром в G.

b b

a, b