1         Теория графов. Основные понятия

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

Графом G(X, U) называют совокупность множества вершин X = (x₁, x₂, …, x_n) и ребер U = (u₁, u₂, …, u_m), если каждое ребро

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

Инцидентность - отношение типа "лежит на" или "проходит через". Если связываемые вершины x_i и x_j в (1) упорядочены, то ребро становится направленным и называется дугой. Граф с направленными связями называют направленным графом (ориентированным графом или орграфом), в противном случае — ненаправленным (неориентированным). Граф называют смешанным, если в нем имеются как ребра, так и дуги. Ребра, соединяющие одинаковые вершины, — кратные или параллельные. Граф без петель, но с кратными ребрами — мультиграф. Максимальное число кратных ребер называется мультичислом графа.

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

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

Граф G₁(X, U₁) является частичным графом (суграфом) графа G₂(X, U₂), если U₁ Ì U₂. Т.е. в частичном графе сохраняются все вершины, а некоторые ребра опущены. Если опущены некоторые вершины и инцидентные им ребра, получим подграф.

Граф G₁(X₁, U₁) называется куском графа G₂(X₂, U₂), если X₁ Ì X₂ и в U₁ входят все ребра из U₂, инцидентные X₁.

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

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

Последовательность ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину, называют маршрутом. В орграфах аналогом маршрута является путь, т.е. такая последовательность дуг, в которой конец одной дуги является началом другой дуги. Маршрут, все ребра которого различны, является цепью, а если различны все вершины, то маршрут — простая цепь. Замкнутая цепь является циклом, замкнутая простая цепь — простым циклом. Цикл, содержащий все ребра графа, называют эйлеровым циклом, а граф, имеющий эйлеров цикл, — графом Эйлера. Простой цикл, который включает все вершины графа, называют гамильтоновым циклом. Для орграфов понятиям цепь и цикл соответствуют понятия путь и контур. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед­ ние заданы).

Рис. 1.  Пример графа

Деревом графа называют связный неориентированный граф без циклов. Если при этом граф несвязный, то его название — лес. Любое дерево, построенное на n вершинах, содержит n—1 ребер, а лес, состоящий из n вершин и p деревьев, имеет n - p ребер. Если дерево содержит все вершины графа, то это остов или остовное дерево (покрывающее дерево).

Дерево может быть выделено из любого (ненулевого) графа. Если дерево — покрывающее, то множество ребер графа разбивается на подмножество ветвей и подмножество хорд (дополнений ребер дерева). При этом связный граф, имеющий п вершин и k ребер, содержит n—1 ветвей и k – n + 1 хорд. Если граф несвязный, то число хорд, входящих в дополнение леса, равно k – n + p. Ориентированное дерево называется прадеревом. Начальная вершина прадерева называется корнем.

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

В матрице инцидентности столбцы соответствуют вершинам, а строки — ребрам. Если вершина x_q инцидентна ребру u_p, то pq-й элемент матрицы неориентированного графа равен единице, иначе нулю. В орграфе элемент матрицы инцидентности равен +1, если дуга входит в вершину, и -1, если выходит из вершины. Для неориентированного графа суммы элементов матрицы в каждой строке и в каждом столбце равны степеням соответствующих вершин.

Таблица 1    

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

Таблица 2

Если вершины графа распределены на два подмножества x₁ и x₂ таким образом, что связи имеются только между вершинами разных подмножеств, то такой граф называют двудольным графом (графом Кёнига).

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

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

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