Виды подграфов

Пусть дан граф G = (X, A), где X = {хi}, i = 1, 2, ..., n – множество вершин, A = { ai }, i = 1, 2, ..., m – множество дуг.

Подграфом ,б, а исходный граф – на ,а.

Остовным подграфом Gp = (X, Ap ) графа G называется граф, для которого $$A_{p} \subset A$$. Таким образом, остовный подграф имеет то же самое множество вершин, что и исходный граф G, но множество дуг подграфа Gp является подмножеством множества дуг исходного графа. Примеры остовных подграфов приведены на ,в. Для графа, имеющего m дуг, можно построить k остовных подграфов

k=C1m+C2m+...+Cm-1m=2m-1

Порожденным подграфом Gs =(Xs , Гs ) называется граф, для которого $$X_{s} \subset X$$ и для каждой вершины $$х_{i} \in X_{s}$$ прямое отображение $$Г_{s} (х_{i}) = Г(х_{i}) \cap X_{s}$$. Таким образом, порожденный подграф состоит из подмножества вершин Xs множества вершин исходного графа и всех таких дуг графа G, у которого конечные и начальные вершины принадлежат подмножеству Xs . Примеры порожденных подграфов приведены на ,г.

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

Сильно связные графы и компоненты графа

Графы могут быть классифицированы по связности: сильно связные, односторонне связные, слабо связные и несвязные.

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

Орграф называется односторонне связным, или односторонним, если для любых двух различных его вершин хi и xj существует, по крайней мере, один путь из хi в xj или из xj в хi или оба пути существуют одновременно. Граф на ,б не является сильным, так как в нем нет пути из х1 в х3 , но является односторонне связным.

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

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

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

Максимальным подграфом графа G относительно свойства Р называется порожденный подграф Gsm , обладающий этим свойством и такой, что не существует другого порожденного графа Gs , у которого $$Х_{s} \supset Х_{sm}$$ и который так же обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связанность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится ни в каком другом сильном подграфе. Такой подграф называется сильной компонентой графа. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента – максимальный слабый подграф.

Например, в графе, приведенном на ,б, подграф, состоящий из вершин ,в, подграф не содержащий вершины {х1, х4, х5, х6}, является односторонней компонентой.

В графе, приведенном на ,г, оба подграфа, включающие вершины {х1, х5, х6} и {х2, х3, х4} являются слабыми компонентами, и у этого графа только две компоненты.

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