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

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

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

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

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

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

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

Дополнительным частичным графом H(A) графа G(X) является единственный граф, состоящий из ребер графа G(X), не принадлежащих некоторому частичному подграфу H_A(A) графа G(X) (рис.2.11).

Звездным графом, определяемым вершиной х, называется граф, со­стоящий из всех ребер G(X), имеющих х концевой вершиной. Петли в х могут как включаться, так и не включаться в звездный граф.