3.5.2. Элементы теории графов

Теорию графов применяют для решения таких задач, как анализ электронных схем, разбиение и размещение электронных элементов, проектирование проводного и печатного монтажа, сетевое планирование и многих других. Это объясняется тем, что использование графов сокращает объем вычислений по сравнению с другими методами и, сохраняя наглядность описания объектов (конструкций), позволяет строить компактные и удобные для реализации на ЭВМ алгоритмы преобразований и оптимизации.

Понятие графа G(X,U) опирается на понятие множества.

Под абстрактным графом или просто графом G(X,U) понимают совокупность непустого множества X и изолированного от него подмножества U (возможно, пустого), представляющего собой множество всех упорядоченных пар (x_i, x_j), где x_i, x_jX. Элементы множеств X и U называют, соответственно, вершинами и дугами (ребрами) графа. Следовательно, граф - это множество X всех вершин x_i, связи между которыми определены множеством ребер U.

Геометрически граф можно представить в виде множества точек X={x_j} (j=1, 2,..., n) в n-мерном евклидовом пространстве Eⁿ и множества простых, направленных самонепересекающихся кривых U={u_k}(k=1, 2, ..., r), соединяющих x_i и x_j, которые находятся в некотором отношении друг к другу.

То, что элемент x_iX находится в отношении T_ij к элементу x_jX, отображается на графе соединением элементов x_i и x_j линией со стрелкой в направлении от x_i к x_j. Такие соединения вершин графа с указанием направления называют ориентированными ребрами или дугами и записывают так: u_k=(x_i, x_j) x_i T_ij x_j.

Граф, в котором все вершины соединены дугами, называют ориентированным, орграфом, направленным или несимметрическим графом.

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

Рассмотрим ориентированный граф, показанный на рис. 3.2.

Рисунок 3.2. Ориентированный граф

Этот граф определяет следующую систему уравнений:

Граф, в котором для любых двух вершин x_i, x_jX справедливо выражение T_ij = T_ji, называют неориентированным, неографом, ненаправленным или симметрическим графом.

В таком графе вершины x_i, и x_j соединены ненаправленной кривой, называемой ребром графа (рис. 3.3).

Рисунок 3.3. Неориентированные графы

Две вершины x_i, x_jX считаются смежными, если они определяют ребро (дугу) и, соответственно, два различных ребра (дуги) смежны, если они имеют общую вершину

Иными словами, вершина x_j смежна x_i, если x_jГx_i,, где Гx_i – отображение x_i на множество Х.

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

Граф задан, если задано непустое множество Х и отображение Г множества Х в Х. Обозначим его G(X, Г). При геометрической реализации такого графа каждую вершину x_iX соединяют со всеми вершинами x_jГx_i.

Например, для графа G(X, Г) (рис. 3.3 (a)) можно записать:

X={x_j} (j=1, 2, ..., 5); Гx₁=x₂,x₅; Гx₂=x₁,x₃,x₄; Гx₃=x₂,x₄; Гx₄=x₂,x₃,x₅; Гx₅=x₁,x₄.

Вершина x_i инцидента ребру (дуге) u_j если она является началом или концом ребра (дуги). Аналогично утверждение, что ребро (дуга) u_j инцидентно вершине x_i, если оно входит или выходит из этой вершины.

Число ребер (дуг), инцидентных некоторой вершине x_i, называют локальной степенью вершины и обозначают (x_i).

Для графа (рис. 3.3, б) можно записать:

(x₁) = (x₄) = (x₅) = 3; (x₂) = (x₈) = 4; (x₃) = 1; (x₆) = (x₇) = (x₉) = 2.

Учитывая, что каждое ребро неориентированного графа инцидентно двум вершинам, получим выражение, связывающее число ребер графа со степенями вершин

Из этого выражения следует, что число вершин с нечетной степенью в графе четное, так как при опускании всех вершин x_i с четными степенями (x_i) сумма слева остается четной.

Вершину, не инцидентную никакому ребру (дуге), называют изолированной.

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

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

u_k=(x_i, x_i)  x_i T_ii x_i.

Такую связь называют петлей.

Граф называют конечным, если число его ребер конечно и бесконечным, если число его ребер бесконечно.

Граф называют однородным степени t, если степени всех его вершин t.

Примеры бесконечных однородных графов приведены на рис. 3.4.

Рисунок 3.4. Бесконечные однородные графы

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

Существенной характеристикой графа является его связность.

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

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

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

Граф, все вершины которого попарно смежны, называют сильносвязным или полным графом и обозначают К_n, где n – число вершин графа (рис. 3.5)

Рисунок 3.5. Полный граф К₅

Последовательность ребер u_kU заданных парами вершин вида (x₀, x₁) (x₁, x₂)...(x_l-1, x_l), в которой любые два соседних ребра смежные, называется маршрутом.

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

Если в цепи нет повторяющихся вершин кроме соседних, то такая цепь называется простой.

Циклом называют последовательность ребер u₁=(x₁, x_i), ..., u_k=(x_j, x₁), при которой в результате обхода вершин графа по этим ребрам возвращаются в исходную вершину x₁.

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

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

Цикл называют элементарным, если он не содержит в себе никаких других циклов.

Цикл считают минимальным, если он включает минимальное число ребер, и максимальным, если он содержит максимальное число ребер графа.

Таким образом, цикл - это замкнутая цепь.

Большое значение в задачах конструкторского проектирования ЭВМ имеют эйлеровы и гамильтоновы циклы.

Эйлеров цикл – это цикл, в котором содержатся все ребра графа.

Граф, имеющий такой цикл, называют эйлеровым графом. На рисунке 3.6. изображен граф «Сабли Магомета». Это эйлеров граф, эйлеров цикл х₁ х₆ х₉ х₁₀ х₁₁ х₇ х₄ х₂ х₆ х₈ х₉ х₃ х₁₀ х₅ х₄ х₃ х₂ х₁.

Рисунок 3.6. Пример эйлерова графа

Необходимым и достаточным условием наличия в конечном связном графе эйлерова цикла является четность степеней всех его вершин (теорема Эйлера).

Цикл называют гамильтоновым, если он проходит через каждую вершину один раз.

Известно (теорема Оре – Дирака (1960 г.)), что граф имеет гамильтонов цикл, если сумма локальных степеней двух любых вершин графа больше или равна числу вершин графа, т.е. x_i x_jX [(x_i) + (x_j)  n].

Из теоремы следует результат Дирака (1952 г.): граф имеет гамильтонов цикл, если локальные степени любых его вершин x_i, x_jX [(x_i)  n/2].

Граф с гамильтоновым циклом изображен на рисунке 3.7. Гамильтонов цикл обозначен штрих-пунктирной линией.

Рисунок 3.7. Пример графа с гамильтоновым циклом

Н есмотря на некоторое сходство в определениях эйлеровых и гамильтоновых циклов, используемые для их отыскания методы имеют мало что общего. Критерий существования эйлерова цикла был установлен просто, для гамильтонова цикла такого общего правила не известно. Более того, иногда для конкретного графа бывает затруднительно сказать, имеет ли он такой цикл или нет. Существуют лишь частные критерии наличия в графе гамильтонова цикла. То, что критерии существования гамильтонова цикла в графе являются достаточными, но не необходимыми можно проиллюстрировать с помощью графа-куба (рис. 3.8).

x_i, x_jX [(x_i) + (x_j) = 6 < 8]

x_i, x_jX [(x_i) =3 < 4].

Рисунок 3.8. Трехсвязный кубический граф

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

Два графа G и G’ изоморфны, если они имеют одинаковое число вершин и если каждой паре вершин, соединенных ребром (дугой), в одном графе, соответствует такая же пара вершин, соединенных ребром (дугой), в другом графе (рис. 3.9).

Рисунок 3.9. Пример изоморфных графов

Решение ряда задач конструкторского проектирования ЭВМ связано с изоморфными преобразованиями графа, т.е. с построением графа, изоморфного заданному. Например, с целью сокращения числа пересечений ребер графа, изображенного на плоскости, уменьшения суммарной длины ребер графа.

Граф, у которого существует хотя бы одна пара вершин, соединенная кратными ребрами (дугами в одном направлении), называют мультиграфом (рис. 3.10). Максимальное число кратных ребер (дуг) в графе называют мультичислом графа.

Мультичисло мультиграфа, представленного на рис. 3.10, равно трем.

Если в графе G(X, U) опущены некоторые ребра, а число вершин осталось прежним, то полученный граф G(X, U’) называют частичным графом G(X, U) или суграфом. На рис. 3.11 показан частичный граф мультиграфа рис. 3.10.

Рисунок. 3.10. Пример мультиграфа G1

Рисунок 3.11. Частичный граф мультиграфа G1