5. Подграфы

Пусть дан граф G=(X, А). Остовным подграфом G_p графа G называется граф (X, А_р), для которого .

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

Пусть дан граф G = (X, Г). Порожденным подграфом ²) G₃, называется граф , для которого и для каждой вершины . Таким образом, порожденный подграф состоит из подмножества вершин множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству X₃. Часто бывает удобно обозначать подграф G₃ просто символом ; мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы.

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

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

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

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