флеров

Связность

Пусть граф G - неориентированный. Две вершины a и b называются связанными, если существует путь S с начальной вершиной a и конечной вершиной b, S=< a , a₁ , ... , a_n , b >. Если S проходит через какую-нибудь вершину a_i более одного раза, то можно, очевидно, удалить его циклический участок и при этом остающиеся ребра будут составлять путь S из a в b. Отсюда следует, что связанные путем вершины связаны и простым путем. Граф называется связным, если любая его пара вершин связана. Для всякого графа существует такое разбиение множества его вершин

на попарно непересекающиеся подмножества вершин V_i, что вершины в каждом V_i связаны, а вершины из различных V_i не связаны.

Граф H называется частью графа G, если множество его вершин V(H) содержится во множестве вершин V(G) графа G и все ребра H являются ребрами G. Для любой части H графа G существует единственная дополнительная часть (дополнение) , состоящее из всех ребер графа G, которые не вошли в H, и инцидентных им вершин. Особенно важным типом частей являются подграфы.

Пусть V^ -подмножество вершин графа G = < V, E >, V^  V. Подграф G(V^,E^), определяемый множеством V^, есть такая часть графа G, множеством вершин которой является V^, а ребрами - все ребра из G, оба конца которых лежат в V^:

= .

Тогда в соответствии с разбиением мы получаем прямое разложение

графа G на непересекающиеся связные подграфы G(V_i). Эти подграфы называются связными компонентами (или компонентами связности) графа G.

Теорема 3.2. Если в конечном неориентированном простом графе G ровно две вершины a₀ и b₀ имеют нечетную локальную степень, то они связаны.

Доказательство. По теореме 3.1, каждый конечный граф имеет четное число вершин нечетной степени. Так как это условие выполняется и для той компоненты G, которой принадлежит a₀, то b₀ принадлежит той же компоненте связности. 

Теорема 3.3. Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно

Доказательство. Пусть в графе G связная компонента G_i имеет n_i вершин. Тогда максимальное число ребер в G равно . Это число достигается, когда каждый из графов G_i полный и имеет n_i вершин. Допустим, что среди графов G_i найдутся хотя бы два, которые имеют более одной вершины, например n₂ n₁ > 1. Построим вместо G другой граф G^ с тем же числом вершин и компонент, заменяя G₁ и G₂ полными графами G₁^ и G₂^ соответственно с n₁-1 и n₂+1 вершинами. Легко видеть, что это увеличит число ребер. Таким образом максимальное число ребер должен иметь граф, состоящий из k -1 изолированных вершин и одного полного графа с n - k + 1 вершинами.

Из теоремы 3.3 следует для случая k = 2 следующее утверждение.

Теорема 3.4. Простой неориентированный граф с n вершинами и с числом ребер, большим, чем

связен.

Содержание