double arrow

Элементы графов. Подграфы. Валентность

После рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным составным элементам графов.

Определение 9.6. Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G'), если V' включенов V и/или Е' включенов Е.

Определение 9.7. Если V' = V, то G' называется остовным подграфом G.

Определение 9.8. Если V' включенов V и Е' включенов Е (причем V' не равно V и E' не равно E), то граф G' называется собственным подграфом графа G.

Определение 9.9. Подграф G'(V',Е') называется правильным подграфом графа G(V,Е), если G' содержит все возможные ребра G. Правильный подграф G'(V, Е') графа G(V, Е) определяется подмножеством вершин V'.

Определение 9.10. Количество ребер, инцидентных вершине v, называется степенью (или валентностью вершины v) и обозначается d (v).

Причем 0 £ d (v) £1 d (v) = |Г(v)|.

Обозначим минимальную степень вершины графа G через d(G), а максимальную — через D(G).

Определение 9.11. Если степени всех вершин равны k, то граф называется регулярным степени k:

Степень регулярности является инвариантом графа и обозначается r (G). Для нерегулярных графов r (G) не определено.

Пример: Ниже приведена диаграмма регулярного графа степени 3

Если степень вершины равна 0, то вершина называется изолированной. Если степень вершины равна 1, то вершина называется концевой, или висячей.

Для орграфа число дуг, исходящих из вершины v, называется полустепенъю исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d (v) и d+(v).


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: