Связность графов

курсовая работа

§4. Новые определения

Маршрутом в данном графе G называется конечная последовательность ребер вида

{v0,v1},{v1,v2}, …, {vm-1,vm}

(обозначаемая также через (v0> v1> v2> …> vm) Очевидно следующее свойство маршрута: любые два последовательных ребра либо смежны, либо одинаковы. Но не всякая последовательность ребер, обладающая этим свойством, является маршрутом (в качестве примера рассмотрим звездный граф и возьмем его ребра в произвольном порядке). Каждому маршруту соответствует последовательность вершин vо, v1, ..., vm; v0 называется начальной вершиной, а vm -- конечной вершиной маршрута. Таким образом, мы будем говорить о маршруте из v0 в vm. Заметим, что для любой вершины V^ тривиальным маршрутом, вообще не содержащим ребер, является маршрут из v0 в v0. Длиной маршрута называется число ребер в нем; например, на Рис. 1 маршрут v>w>x>y>z>z>y>w из v в w имеет длину, равную семи.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины v0, v1 ..., vm различны (кроме, может быть, v0= vm).

Рис 4.1

Цепь или простая цепь замкнуты, если v0= vm. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом; в частности, любая петля или любая пара кратных ребер образует цикл.

Замечание. Маршрут, также называют путем, реберной последовательностью. Цепь называют путем, полупростым путем; простую цепь -- цепью, путем, дугой, простым путем, элементарной цепью; замкнутую цепь -- циклической цепью, контуром; цикл -- контуром, контурной цепью, простым циклом, элементарным циклом.

Чтобы разобраться в приведенных выше определениях, рассмотрим еще раз Рис. 1. Мы видим, что v>w>x>y>z>z>x -- цепь, v>w>x>y>z-- простая цепь, v>w>x>y>z>x>v -- замкнутая цепь и v>w>x>y>v-- цикл. Цикл длины три (например, v>w>x>v) называется треугольником.

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

Теорема 5А. Граф является связным в смысле данного выше определения тогда и только тогда, когда он связен в смысле определения из §3.

Доказательство. => Пусть граф G связен в смысле определения из данного параграфа. Допустим, что G представляет собой объединение двух (непересекающихся) подграфов, а v и w -- вершины, принадлежащие разным подграфам. Любая простая цепь из v в w должна содержать ребро, инцидентное некоторым двум вершинам из разных подграфов; так как такого ребра не существует, получили противоречие.

<= Теперь предположим, что граф G связен в смысле определения из § 3 и не существует никакой простой цепи, связывающей заданную пару вершин v и w. Тогда, по данному выше определению компонент связности, вершины v и w будут принадлежать разным компонентам. Исходя из этого, можно представить G в виде объединения двух графов, одним из которых является компонента, содержащая v, а другим -- объединение оставшихся компонент. Отсюда и получаем нужное противоречие. //

Теперь, когда мы представляем себе, что такое связность, естественно попытаться найти какие-нибудь свойства связных графов. Одно направление исследования -- поиск оценок для числа ребер простого графа с n вершинами и заданным числом компонент. Если такой граф связен, то естественно ожидать, что число ребер в нем минимально тогда, когда он не имеет циклов (такой граф называется деревом), и максимально, когда он является полным графом. Отсюда следовало бы, что число ребер в связном графе заключено между n-- 1 и n(n -- 1)/2. Этот результат является частным случаем более сильного утверждения, которое сейчас докажем.

Теорема 5В. Пусть G -- простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

n -- k < m < (n -- k)(n -- k + 1)/2.

Доказательство. Неравенство m ? n -- k докажем индукцией по числу ребер в G. Если О -- вполне несвязный граф, то утверждение очевидно. Если в графе G число ребер минимально (скажем m0), то удаление любого ребра должно привести к увеличению числа компонент на единицу. Таким образом, в получившемся графе будет n вершин, k + 1 компонент и m0 -- 1 ребер. Следовательно, в силу индуктивного предположения m0 -- 1 > n -- (k+1), откуда сразу же получается m0 > n -- k, что и утверждалось.

Для доказательства оценки сверху можно считать каждую компоненту графа G полным графом. Предположим, что Сi и Сj -- две компоненты соответственно с ni и nj; вершинами и ni ? nj? 1. Если мы заменим Сi и Сj; на полные графы с ni + 1 и nj -- 1 вершинами, то общее число вершин не изменится, а число ребер увеличится на положительную величину

1/2{(ni+1) ni - ni (ni -1)}-1/2{ nj (nj -1)-( nj -1)( nj -2)} = ni- nj +1.

Следовательно, для того чтобы число ребер в графе G было максимально возможным (при заданных n и k), G должен состоять из k-- 1 изолированных вершин и полного графа с n -- k + 1 вершинами. Отсюда сразу вытекает нужное неравенство. //

Следствие 5С. Любой простой граф с т вершинами и более чем (n-- 1)(n -- 2)/2 ребрами связен. //

Другое направление исследования связных графов задается следующим вопросом: насколько сильно связен связный граф? Этот вопрос можно сформулировать и так: сколько ребер нужно удалить из графа, чтобы он перестал быть связным?

Рис. 2 Рис. 3

Для обсуждения данного вопроса удобно ввести еще два определения. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу. Например, в графе, изображенном на Рис. 2, каждое из множеств {е12, е5} и {е3, е6, е7, е8) является разделяющим; несвязный граф, оставшийся после удаления второго из этих множеств, показан на Рис. 3. Далее, назовем разрезом такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. В рассмотренном выше примере разрезом будет только второе разделяющее множество. Легко видеть, что после удаления ребер, принадлежащих разрезу, остается граф, имеющий ровно две компоненты. Если разрез состоит из единственного ребра e, то е называется мостом, или перешейком (Рис. 4).

Все эти определения легко переносятся на несвязные графы. В произвольном графе G разделяющим множеством называется такое множество ребер, удаление которого увеличивает число компонент вG. Разрезом в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.

Делись добром ;)