Дерево представляет собой связный граф

Элементы графа

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

Смежнымирёбрами называются два ребра, которые подходят к одной вершине, или выходят из неё. Иногда говорят, что этирёбра инцидентны вершине.

Степень r(X_i) вершиныX_i– это число инцидентных ей рёбер. Если ни одного ребра к вершинеX_iне подходит, тоr(X_i) = 0; если подходит одно ребро, тоr(X_i) = 1 и т.д..

Части графа

Различают подграфикусокграфа.

Подграф получают разбиением исходного графа по его вершинам. В этом случае вершины, по которым происходит разбиение, дублируются в подграфах, а ребра распределяются по ним.

Кусок получается разделением исходного графа путём «перерезания» рёбер. При разделении графа на куски не происходит образования новых вершин, которые распределяются по кускам. Ребра в этом случае разделяются на внутренние ребра кусков и на соединительные ребра (которые были «разрезаны»), соединяющие куски. Их число минимизируется при выполнении задачи разбиения.

Рис. 4.3 иллюстрирует образование подграфов и кусков графа.

Рис. 4.3. Подграфы и куски графа

Структурные свойства связных графов

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

Маршрут– последовательность рёбер, заданная парами вершин, в которых каждая пара вершин – смежная (рис. 4.4).

Пример маршрута: (X1,X2)(X2,X3)(X3,X1)(X1,X4)…, и т. д.

Цепь– маршрут, в котором все ребра различны. Простая цепь – это цепь, в которой все вершины различны.

Цикл– цепь, в которой совпадает начальная и конечная вершины. Простой цикл – это простая цепь, с совпадающими начальной и конечной вершинами.

Пример цикла: (X1,X2)(X2,X3)(X3,X1).

Гамильтонов циклHC– такой цикл, который проходит через все вершины графа по одному разу:HC= (X1,X2)(X2,X3)(X3,X4)(X4,X1). Его наличие в графе не очевидно, хотя его полезно знать для решения ряда топологических задач. Существуют алгоритмы для выделения гамильтонова цикла.

Деревья– особый тип графов. Дерево представляет собой связный граф без циклов (рис. 4.5). Во многих задачах проектирования монтажных соединений ставится задача поиска дерева на совокупности вершин с минимальной суммарной длиной рёбер. Формула для определения числаdдеревьев, которые можно построить наNвершинах, выглядит следующим образом:

Структурные свойства графа во многом определяют возможность реализации тех или иных алгоритмов их обработки.

Матрица соединений

Матрицы соединений используются для формализованного описания графов. Обозначение этой матрицы R.

Правило заполнения матрицы следующее. Столбцы и строки матрицы соответствуют вершинам графа; число строк и столбцов равно числу вершин, т. е. матрица квадратная. На пересечении строки iи столбцаjставится числоr_ij, соответствующее числу ребёр, которые соединяют эти вершины. Диагональными элементами матрицы являются нули, если в матрице отсутствуют петли. В противном случае проставляется число равное числу петель у соответствующей вершины. Ясно, что матрица симметрична относительно главной диагонали (r_ij=r_ji).

Ниже (рис. 4.6) приведена матрица соединений, в которой для наглядности строки и столбцы имеют заголовки x₁,x₂,x₃, . x_N, гдеNчисло вершин графа.

Рис. 4.6. Матрица соединений

Матрица соединений позволяет весьма просто рассчитать степень r(x_i) вершиныx_iграфа, которая есть число ребер, подходящих к этой вершине. Для определения степени произвольной вершиныx_i, как видно из матрицы соединений, необходимо рассчитать сумму всех элементов в соответствующей строке матрицы:

Можно привести пример анализа связности графа с использованием матрицы соединений. Для этого возьмём для наглядности очень простой несвязный граф (рис. 4.7), содержащий четыре вершины x₁,x₂,x₃,x₄; и два ребра, которые соединяют пары вершинx₁,x₄, иx₃,x₂.

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

Построим для заданного графа матрицу соединений (рис. 4.8).

Рис. 4.8. Матрица соединений для заданного графа

Для получения результата перенумеруем вершины графа, не изменяя его структуры, как показано на рис. 4.9, и построим для последнего варианта матрицу соединений (рис. 4.10). Эта матрица может быть разбита на подматрицы A_ii (рис. 4.11).

Рис. 4.9. Перенумерованные вершины графа

Рис. 4.10. Матрица соединений заданного несвязного графа

Рис. 4.11. Подматрицы матрицы соединений

Рёбра, включенные в подматрицу A_ii, относятся квнутреннимчастям графа, а рёбра, которые включены в подматрицыU_ij, естьсоединительныерёбра между подматрицами (частями) графаiиj. Таким образом, процедура разбиения графа при использовании матрицы соединений сводится к разбиению матрицы на отдельные подматрицы. Результат разбиения оценивается по одному из критериев разбиения, например – по отношениюU_ii/U_ijчисла внутренних рёберU_iiк числу соединительных рёберU_ij. Чем больше это отношение, тем выше качество разбиения, если граф описывает узлы электронной аппаратуры.

Число внутренних ребер определяется по сумме всех ребер в частях графа A_ii. В любом случае наиболее удачным решением при разбиении графа следует признать такое решение, при котором число ребер в подматрицахU_ijбудет минимально. Для несвязного графа матрицыU_ijдолжны быть нулевыми. В этом случае не будет соединительных рёбер между частямиA_ii, т. е. граф несвязный.

Источник

Деревья. Интуитивно понятно, что отдельные графы могут состоять из раз­розненных блоков, в то время как другие оказываются локализованны­ми в единый комплекс. Мы можем

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

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

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

Как правило, из диаграммы графа всегда можно сказать, сколько компонент он имеет. Иногда это сразу видно, а иногда требуется более внимательный анализ. Граф, представленный на рис. 1, имеет две компоненты связности, одна из которых — это нулевой граф с вершиной 4>.

Выше мы рассмотрели пути и циклы графа. Существует специальный тип графа, называемый «дерево», который вообще не имеет циклов. Впервые ввел понятие деревьев физик Густав Кирхгофф в 1847. Будучи студентом Кенигсбергского университета, он сформулировал законы, управляющие течением тока в электрических сетях. Сети проводов могут быть рассмотрены, как графы. Уравнения, которые вытекают из законов Кирхгоффа, не являются незави­симыми и Кирхгофф использовал деревья для получения независимого подмножества уравнений.

В последние десятилетия компьютерная наука столкнулась с тем фактом, что деревья обеспечивают удобные структуры для хранения и исправления определенных типов данных — так называемых иерархи­ческих баз данных.

Определение 3.7. Дерево- это связанный граф, который не содержит циклов.

Из определения сразу ясно, что деревья не имеют петель или кратных ребер. Каждая петля является цепью и если ребра е_i и e_j соединяют одну пару вершин, то последовательность е_i, e_j будет циклом.

На рис. 5 приведены примеры деревьев.

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

Определение 1.8. Пусть Г- связный граф с множеством вершин V. Деревом покрытия графа Г называется подграф, который является деревом, и множеством вершин которого является множество V.

Теорема 1.1. Каждый связный граф содержит в себе покрывающее дерево.

Доказательство: Пусть Г — связный граф; если Граф не, содержит циклов, то доказывать ничего не надо, ибо Г сам по себе — дерево покрытия. Предположим, что Г содержит цикл. Удаление любого ребра из цикла дает граф, который все еще остается связным. Если новый граф все еще содержит циклы, то опять удалим одно ребро этого цикла. Продолжим процесс до тех пор, пока результирующий граф Г не будет содержать ни одного цикла. Мы не удалили ни одной вершины, поэтому граф Г имеет такое же множество вершин, как и граф Г, и на каждой стадии процесса обрезания цикла связность графа не нарушалась. Итак, граф Г — связный и представляет собой дерево покрытия графа Г.

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

Простая структура деревьев позволяет нам легко получить некоторые элементарные положения с ними связанные, которые сформули­рованы в виде следующей теоремы.

ТЕОРЕМА 1.2. Пусть Т — дерево с множеством вершин V и множеством ребер Е. Тогда:

(i) для каждой пары различных вершин v и w существует единственный путь в Т, связывающий их;

(ii) удаление любого ребра из Т приводит к образованию графа с двумя компонентами, каждая из которых является деревом;

Более того, связанный граф, удовлетворяющий любому одному из этих свойств, является деревом.

(i) Пусть v и w — любые две различные вершины графа Т; так как Т — связанный граф, то существует путь Р₁ е₁, е₂. е_n связывающий v и w. Предположим, что существует другой путь Р₂: f₁, f₂. f_m, который также связывает v и w. В некоторой точке эти два пути должны расходиться. Пусть v* — является последней вершиной, до которой, перед началом расхождения, пути p₁ и Р₂ имели общую часть. Так как оба пути заканчиваются на вершине w, то эти пути должны опять соединиться. Пусть w* — первая вершина, в которой пути Р₁ Р₂ сходятся (см. рис. 6). Определим путь так: берем ребра пути Р₁, связывающие v* и w* и присоединяем ребра пути Р₂, связывающие w* и v*. Такой путь связывает вершину v* саму с собой без повторения ребер, то есть это цепь графа Т. Однако, этого не может быть, ибо Т — дерево. Следовательно, существует только единственный путь, связывающий v и w.

(ii) Пусть «е» — произвольное ребро графа Т, связывающее вершины v и w и пусть Г- граф, получаемый путем удаления ребра «е» из графа Т. Так как ребро «е» представляет собой единственный путь графа Т, связывающий v и w, то у графа Г нет пути, связывающего вершины v и w, то есть Г — несвязный.

Пусть V₁ — множество вершин графа Г, которые могут быть связаны путем графа Г с вершиной v и пусть V₂ — множество вершин графа Г, которые могут быть связаны путем графа Г с вершиной w. Тогда V₁ V₂ = V и V₁, V₂ определяют два связных подграфа графа Г. Каждая из этих компонент графа Г является деревом, ибо любая цепь в какой -либо из компонент была бы также цепью графа Т.

(iii) Доказывается по индукции числа вершин графа Т.

Теперь докажем, что если Г — связный граф, удовлетворяющий свойству (i) или (ii), то Г- дерево.

Начнем с первого. Пусть Г — связный граф и пусть Г удовлетворяет (i). Если у графа Г имеется цикл, содержащий пару различных вершин v и w, то этот цикл обеспечивает существование двух различных путей, связывающих v и w. Так как это противоречит условию (i), то таких циклов нет. Не будет также и петель у графа Г. Если V-петля при вершине v и w — любая другая вершина, то существует два различных пути, связывающих v и w: один путь начинается с «е», а другой нет. Следовательно, если Г вообще не содержит циклов, то Г- дерево.

Наконец, предположим, что Г — связный граф и выполняется свой свойство (ii). Если Г содержит цикл, то мы можем удалить ребро цикла, не нарушая связанности Г, что противоречит (ii). Следовательно, опять Г вообще не должен содержать циклов и поэтому Г является деревом.

Источник