1.2. Подграфы и дополнения

Рассмотрим называется подграфом G, если V и Е являются соответственно такими подмножествами V и Е, что ребро содержится в Е только в том случае, если содержатся в V. G называется собственным подграфом G, если Е — собственное подмножество Е или V — собственное подмножество V. Если все вершины графа G присутствуют в подграфе G графа G, тогда G называется остсвным подграфом G.

Рис. 1.2. Граф и некоторые его подграфы. а) — граф ; б — подграф G; в — подграф ; г — подграф

Например, рассмотрим показанный на рис. 1.2, а граф G. Граф G, изображенный на рис. 1.2, б, является подграфом G. Множество его вершин — Он является собственным подграфом G. Граф G" на рис. 1.2, в является остовным подграфом

Некоторые из вершин подграфа могут быть изолированными. Например, показанный на рис. 1.2, г подграф G" является подграфом с изолированной вершиной.

Если подграф графа G не содержит изолированных вершин, тогда по определению подграфа каждая вершина V является концевой вершиной некоторого ребра Е. Таким образом, в

этом случае Е однозначно определяет V и, следовательно, подграф G. Подграф G называется порожденным подграфом графа G на множестве ребер Е (или просто реберно-порожденным подграфом графа G) и обозначается как

Заметим, что множество вершин V графа является наименьшим подмножеством V, содержащим все концевые вершины ребер в Е. Подграфы G и G" на рис. 1.2, б, в являются реберно-порожденными подграфами графа G на рис. 1.2, а, тогда как показанный на рис. 1.2, г, не является реберно-порожденным подграфом.

Определим теперь вершинно-порожденный подграф. Пусть V — подмножество множества вершин V графа . Тогда подграф называется порожденным подграфом графа G на множестве вершин V (или просто вершинно-порожденным подграфом графа G), если Е является таким подмножеством Е, что ребро входит в Е тогда и только тогда, когда входят в Другими словами, если принадлежат V, то каждое ребро Е, имеющее в качестве концевых вершин должно входить в Е. Заметим, что в этом случае V полностью определяет и, таким образом, подграф G. Следовательно, вершинно-порожденный подграф можно обозначить как Например, граф, представленный на рис. 1.3, является вершинно-порожденным подграфом графа G на рис. 1.2, а.

Рис. 1.3. Вершинно-порожденный подгргф графа С, изображенного на рис. 1.2, а.

Заметим, что множество ребер вершинно-порожденного подграфа на множестве является таким наибольшим подмножеством Е, что концевые вершины всех его ребер принадлежат V.

Подграф G графа G называется максимальным подграфом по отношению к некоторому свойству Р, если G обладает свойством Р и G не является собственным подграфом никакого другого подграфа графа G, обладающего свойством Р.

Подграф G графа G называется минимальным подграфом графа G по отношению к некоторому свойству Р, если G обладает свойством Р и никакой подграф графа G, обладающий свойством Р, не является собственным подграфом графа

Максимальное и минимальное подмножества некоторого множества по отношению к свойству определяются аналогичным образом.

Например, множество вершин V реберно-порожденного подграфа графа является минимальным подмножеством V, содержащим концевые вершины всех ребер Е. С другой стороны, множество ребер Е вершинно-порожденного подграфа является

Рис. 1.4. Граф и его дополнение. a - граф G; б — граф G, дополняющий граф

Рис. 1.5. Другой пример графа и его дополнения, а — граф б — граф G дополняющий граф

таким максимальным подмножеством Е, что концевые вершины всех его ребер принадлежат V.

Позднее мы увидим, что «компонента» (разд. 1.4) графа G является максимальным «связным» подграфом графа G, а «остовное дерево» (гл. 2) связного графа G является минимальным «связным» остовным подграфом графа

Определим теперь понятие «дополнение графа».

Граф называется дополнением простого графа , если ребро входит в Е в том и только в том случае, если оно не входит в Е. Другими словами, две вершины смежны в G тогда и только тогда, когда они не смежны в G. На рис. 1.4 представлены граф и его дополнение. В качестве другого примера рассмотрим граф, изображенный на рис. 1.5, а. В этом графе между каждой парой вершин имеется ребро. Следовательно, в дополнении G графа G вообще не будет ребер, т. е. G будет содержать только изолированные вершины. Граф G изображен на рис. 1.5, б.

Пусть является подграфом графа . Подграф графа G называется дополнением G в G. Например, подграф G" на рис. 1.2 является дополнением G в графе

Следующий пример иллюстрирует некоторые из рассмотренных понятий.

Предположим, что мы хотим доказать следующее утверждение.

В любой группе из шести человек трое либо обоюдно знакомы, либо обоюдно незнакомы.

Представляя людей вершинами графа, а наличие знакомства между ними — ребрами, соединяющими соответствующие вершины, можно увидеть, что приведенное выше утверждение можно сформулировать следующим образом:

В любом простом графе G с шестью вершинами имеются три либо попарно смежные, либо попарно несмежные вершины.

Используя определение дополнения графа, замечаем, что это утверждение эквивалентно следующему:

Для любого графа G с шестью вершинами справедливо, что G или G содержит три попарно смежные вершины.

Для доказательства этого проделаем следующее. Рассмотрим произвольную вершину v простого графа G с шестью вершинами. Заметим, что, если v не смежна с тремя вершинами в G, она должна быть смежна с тремя вершинами в G. Поэтому, не нарушая общности, допустим, что v смежна в G с некоторыми тремя вершинами Если две из этих вершин, например смежны в G, то вершины попарно смежны в G, и утверждение доказано.

Если в G никакие две из трех вершин не смежны, тогда они попарно несмежны. Следовательно, по определению дополнения вершины попарно смежны в G, и утверждение снова доказано.