Частичные графы и подграфы

Граф Н(х) называется частичным для графа G(X), если все ребра Н(Х) являются ребрами G(X) и множество вершин графа Н(Х) совпадает с множеством вершин графа G(X), то есть Н(х) Ì G(x) " х Î X (рис.3.8).

Рис. 3.8. Граф G(X) и частичный для него граф Н(Х)

Частичный граф содержит часть ребер (дуг). Он также может быть ориентированным или неориентированным в зависимости от исходного графа.

Отметим, что ноль-граф графа G(X) считается его частичным гра­фом. Все частичные графы Н(Х) для G(X) можно получить, выбирая в качестве ребер Н(Х) всевозможные подмноже­ства множества ребер графа G(X).

Подграфом G_A(A) графа G(X), где А Ì X, называется граф, вершинами которого являются элементы множества
А Ì X, а ребра­ми ­– все ребра из G, концевые вершины которых лежат в А (рис.3.9).

Хо

Хо

Х4

 

Рис. 3.9. Подграф G_A(A) графа G(X)

Таким образом, под­граф содержит часть вершин вместе с ребрами, со­единяющими эти вершины. Иначе, G_A(A) – подграф графа G(X), если А Ì X и G_A(x) = G(x)ÇА " х Î Х.

Если А = X, то G_A(A) = G(X). Для единственной вершины А = {а} подграф G_A(a) со­стоит из петель вокруг а. Под­графом G_A(A) графа G(X) будет ноль-граф, если
А Ì X есть подмножество изолированных вершин графа.

Под­граф будет ориентированным или неориен­тированным в зависимо­сти от исходного графа.

Частичным подграфом Н_А(А), А Ì X графа G(X) называется подграф (рис. 3.10), ребрами которого являются некоторые ребра из G(X), оба конца которых лежат в А. Иначе, Н_А(А) – частичный под­граф графа G(X), если А Ì X и Н_А(х) Ì G(x) Ç A " х Î Х.

Дополнительным частичным графом Н(А) графа G(X) явля­ется единственный граф, состоящий из ребер графа G(X), не при­надлежащих некоторому частичному подграфу Н_А(А) графа G(X) (рис. 3.11).