Остовы графа

Остов графа

Пусть G — произвольный (n, m)-граф с k компонентами связности. Если G — не дерево, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф G, называется остовом графа G.

Остовым (покрывающим) деревом графа G называется любое дерево T, являющееся суграфом графа G. Покрывающее дерево T в связном графе определяется неоднозначно.

Связный граф имеет единственное покрывающее дерево тогда и только тогда, когда он сам является деревом.

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

Суграф T графа G называется каркасом этого графа, если он является лесом, который на любом компоненте связности графа G образует дерево.

Теорема

Число ребер произвольного графа G с n вершинами и m ребрами, имеющего k компонент связности, которое необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m-n+k.

Доказательство теоремы

Пусть H_i, i=i, k-компоненты связности графа G, и пусть H_i-(n_i,m_i)-графы. После удаления ребер из циклов компоненты H_i она превратится в дерево, которое имеет n_i−1 ребер. Значит, из H_i необходимо удалить m_i-(n_i−1) ребер. Суммируя по всем компонентам, находим, что для получения остова из графа G необходимо удалить $\sum_{i=1}^k$ (m_i-n_i+1)= $\sum_{i=1}^k$ m_i — $\sum_{i=1}^k$ n_i + $\sum_{i=1}^k$ 1=m-n+k ребер, что и требовалось доказать.

Определения

Число ν(G)=m-n+k называется цикломатическим числом (циклическим рангом) графа G. Число ν*(G)=n-k, то есть число ребер, входящих в любой остов графа G называется его коциклическим рангом. ν(G)+ν*(G)=m. Корневым деревом называется дерево T=(V,E) с выделенной вершиной ν, принадлежащая V, при этом вершина ν называется корнем дерева. Для каждой вершины корневого дерева её уровень — это длина цепи от корня до этой вершины.

Следствия

Следствие 1 Граф G является лесом тогда и только тогда, когда ν(G)=0.

Следствие 2 Граф G имеет единственный цикл тогда и только тогда, когда ν(G)=1.

Следствие 3 Граф G, в котором число ребер не меньше, чем число вершин, имеет цикл.

Теорема (Кирхгоф)

Число остовов в связном графе G порядка n≥2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G) графа G.

Теорема. Орграф сильно связан, если в нем существует остовной циклический маршрут.

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.

Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.