4.3 Части и подграфы

Граф Н называется частью графа G (Н Ì G), если его вершины V(H) содержатся в множестве вершин графа G и все ребра Н являются ребрами G.

Нуль-граф считается частью любого графа. Всякое единственное ребро графа есть его часть. Вообще, все части Н графа G можно получить, выбирая в качестве множества ребер Н все возможные семейства ребер на G.

Вопрос: Сколько частей Н имеет граф G, Состоящий из N ребер? - 2N.

Важный тип частей графа составляют подграфы. Пусть А – подмножество вершин V графа G. Тогда подграф G(А) графа G(V) есть такая часть графа G, множеством вершин которой является А, ребрами являются все ребра из G, оба конца которых инцидентны вершинам А.

Если А = V, то подграф G(А) совпадает с G. Для единственной вершины А подграф G(А) состоит из петель в А.

Для любой части Н графа G существует единственная дополнительная часть (дополнение) , состоящая из всех ребер графа G, не принадлежащих Н:

= G – Н.

Пусть Н1 и Н2 – две части G. Сумма этих частей есть Н = Н1 Н2, то есть часть G, состоящая из всех ребер, которые принадлежат Н1 или Н2 или им обоим. Их пересечение D = Н1 Н2 состоит из ребер, принадлежащих одновременно Н1 и Н2.

Если вместо Н2 используем , то сумма этих частей дает исходный граф G:

Н1 = G.

< Предыдущая		Следующая >