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

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

Графом  называют совокупность множества вершин  и ребер , если каждое ребро 

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

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

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

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

Граф  называется куском графа , если  и в  входят все ребра из , инцидентные .

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

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

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

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

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

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

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

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

Таблица 1    

В квадратной матрице смежности й элемент равен числу ребер, соединяющих вершины  и .

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

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

Таблица 2    

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

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

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