Связность графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
яется k-связным или k-реберно связным, соотношения между различными видами связности, зависимость чисел связности от других параметров графа и т. п. Так, если ?(G) - минимальная степень вершин графа G, то справедливы следующие неравенства: (G) ? ?(G) ? ?(G).
Для любых целых а, b, с (0 < а ? b ? с) существует граф G, у к-рого (G) = a, ?(G) = b, ?(G) = c. Если граф G имеет n вершин и ?(G) ? [n/2], то ?(G) = ?(G). Говорят, что множество S вершин, ребер или вершин и ребер разделяет вершины u и v, если u и v принадлежат разным компонентам связности графа G-S, полученного из G удалением элементов множества S. Справедливы следующие утверждения.
Наименьшее число вершин, разделяющих две несмежные вершины u и v, равно наибольшему числу простых цепей, не имеющих общих вершин, соединяющих u и v. Граф G является k-связным тогда и только тогда, когда любая пара его вершин соединена по крайней мере к вершинно непересекающимися цепями. Аналогичные теоремы справедливы и для реберной связности. Граф k-реберно связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере к реберно непересекающимися цепями. Множество ребер, удаление к-рых приводит к несвязному графу, наз. разрезом. В каждом графе наибольшее число реберно непересекающихся разрезов, разделяющих вершины u и v, равно наименьшему числу ребер простой цепи, соединяющей u и v, т. е. расстоянию d(u, v) между u и v.
Теорема несвязности графов
Граф является несвязным тогда и только тогда, когда множество его вершин V можно разбить на два непустых подмножества V1 и V2 так, чтобы любое ребро графа соединяло вершины из одного подмножества.
Доказательство
Пусть G(V,E) - несвязный граф. Зафиксируем некоторую вершину v графа и обозначим через V1 множество, состоящее из вершины v и всех тех вершин из V, которые соединены цепями с вершиной v. Множество V1 не пусто (оно содержит, но крайней мере, вершину v) и не совпадает с множеством V (при V1=V граф G(V,E)- связный, т.к. между его любыми двумя различными вершинами существует цепь, проходящая через v). Рассмотрим дополнение V2=V \ V1.
Множество V2- не пусто, и никакое ребро графа G(V,E) не соединяет ни одну вершину из V1 ни с одной вершиной из V2. Поэтому построенные множества V1 и V2 образуют искомое разбиение множества V.
Обратно, пусть существует разбиение V1 ? V2, множества V, удовлетворяющее условию теоремы.
Докажем, что тогда граф G(V,E) несвязный. Возьмем произвольную пару вершин v ? V1 и w ? V2 , из разных подмножеств и предположим, что существует цепь, соединяющая эти вершины. Такая цепь включает ребро, концы которого принадлежат разным подмножествам, что противоречит условию. Теорема доказана.
Вершина w графа называется достижимой из вершины v, если либо w=v, либо существует цепь с началом v и концом w.
Следствие из теоремы
Для того чтобы граф G был связным необходимо и достаточно, чтобы в нем из любой фиксированной вершины были достижимы все остальные вершины этого графа.
Свойства графов
Свойства графов:
. Каждая вершина графа входит в одну и только в одну компоненту связности.
. Любой конечный граф имеет конечное число компонент связности.
. Граф, состоящий из единственной компоненты связности, является связным.
. Каждая компонента связности графа является его подграфом.
. Для любого графа либо он сам, либо его дополнение является связным.
Доказательства свойств
Докажем свойства 4 и 5.
. Пусть G1(V1,E1) - некоторая компонента связности графа G(V,E) . Рассмотрим множество вершин V2=V \V1 графа G, не входящих в компоненту G1(V1,E1) . Если удалить каждую вершину из V2 вместе со всеми инцидентными ей ребрами, получим подграф графа G(V,E) совпадающий с компонентой связности G1(V1,E1).
. Пусть G(V,E) некоторый граф порядка n, а G=(V,E) - его дополнение до графа Кn. Когда граф G связен, утверждение очевидно. Пусть G несвязный граф G1(V1,E1) - одна из его компонент связности и V2=V \V1. Тогда для любых вершин v ? V1 , w ? V2 -, в дополнении G существует ребро vw ? E . Значит, любая вершина из V2 соединена с любой вершиной из V1ребром, принадлежащим E , а любые две вершины из V1 соединены цепью длины 2, оба звена которой также лежат в E . Поэтому граф G связен.
граф непустой вершина связь
Глава 2. Цепи и циклы
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. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом; в частности, любая петля или любая пара кратных ребер образует цикл.
Замечание. Маршрут, также н