Подграфы. Операции над графами

Рассмотрим граф G =(P,A) с множеством вершин P и множеством рёбер А. Граф G^’= (P’,A’) называется подграфом графа G, если P ’ и A ’ являются подмножествами Р и А, при чем ребро содержится в A’ только в том случае, если его концевые вершины содержатся в Р’.

Пусть Р’ – некоторое подмножество множества вершин графа G =(P,A) и пусть A’ – множество всех рёбер графа G, концевые вершины которых входят в Р’. Тогда граф G ^’=(P’,A’) называется вершинно-порождённым подграфом графа G.

Обозначим через A’ некоторое подмножество множества рёбер графа G =(P,A), и пусть P ’ есть множество всех вершин графа G, инцидентных рёбрам из A ’. Тогда граф G^’ =(P’,A’) называется рёберно-порожденным подграфом графа G.

На рис. 3.4 изображены вершинно-порожденный подграф G₁ графа G, представленного на рис.3.1 (множество вершин Р₁,Р₃,Р₄) и рёберно-порожденный подграф G₂ того же графа G (множество рёбер £₁, £₃, £₄, £ ₆)

Рис.3.4

Операции над графами:

1. Объединением графов G₁ =(P₁,A₁) и G₂ =(P₂,A₂) называется граф G=G₁ G₂, множество вершин которого есть объединение множеств вершин графов G₁ и G₂ (P= P₁ P₂), а множество рёбер является объединением множеств рёбер этих графов (A=A₁ A₂).

2. Пересечением графов G₁ и G₂ называется граф G=G₁∩G₂, множество вершин которого есть пересечение P₁∩P₂, а множеством рёбер- пересечение A₁∩A₂.

3. Кольцевой суммой двух графов называется граф G1 + G2, порожденный на множестве ребер (А1 А2)\(А1∩А2), т.е. на множестве ребер, присутствующих либо в G1, либо в G2, но не принадлежащих их пересечению G1∩G2.

Очевидно, что все эти три операции коммутативны. На рис.35 изобра -жены графы: G1,G2, G1 G2; G1∩G2, G1 + G2.

G1 G2

G1∩G2

G1 G2 G1 + G2

Рис.35

Поиск по сайту: