5. Подграфы

Пусть дан граф Остовным подграфом графа называется граф для которого . Таким образом, остовный подграф имеет то же самое множество вершин, что и граф но множество дуг подграфа является подмножеством множества дуг исходного графа.

Граф на рис. остовный подграф графа изображенного на рис. 1.4(a).

Пусть дан граф Порожденным подграфом называется граф для которого и для каждой вершины Таким образом, порожденный подграф состоит из подмножества вершин множества вершин исходного графа и всех таких дуг графа которых конечные и начальные вершины принадлежат подмножеству Часто бывает удобно обозначать подграф просто символом мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы.

На рис. 1.4(b) показан порожденный подграф графа, приведенного на рис. 1.4(a), содержащий только вершины и дуги, которые их связывают.

Рис. 1.4. (см. скан) (а) Граф. (б) Остовный подграф. (в) Порожденный подграф, (г) Подграф.

Соединяя приведенные выше два определения, можно сформулировать определение подграфа. Граф, показанный на рис. 1.4(г), является подграфом графа, приведенного на рис. 1.4(a).

Рассмотрим граф, вершины которого представляют сотрудников некоторого учреждения, а дуги — линии связи между сотрудниками. Тогда граф, представляющий только наиболее важные каналы связи данного учреждения, является остовным подграфом; граф, который подробно представляет линии связи только какой-то части этого учреждения (например, отделения), является порожденным подграфом, а граф, который представляет только важные линии связи в пределах отделения, является подграфом.