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

Пусть V={v₁,…,v_N}– произвольное конечное множество элементов, аU={u₁,…,u_R}– множество элементов, каждый из которых представляет собой пару элементов множестваV: u_k=(v_i,v_j).Тогда совокупность обоих множествG=<V,U>называется графом. Элементы множестваVназываются вершинами (узлами) графа, элементы множестваU– ребрами графа, причем еслиu_k=(v_i,v_j), то вершиныv_iиv_jинцидентны ребруu_k, а реброu_kинцидентно вершинамv_iиv_j. Две вершины, инцидентные одному ребру, или два ребра, инцидентные одной вершине, называются смежными или сосудними. Понятие смежности относится только к однородным элементам графа (вершинам или ребрам) в отличие от понятия инцидентности, относящемуся к неоднородным элементам.

Рис. 1.1

Ребро u_k=(v_i,v_j) называется ориентированным (направленным), или дугой, если вершины v_i и v_j являются упорядоченными, в противном случае ребро называется неориентированным. Дуга- это направленное ребро, она имеет начало и конец. Началу соответствует первая по порядку вершина, инцидентная данной дуге, а концу – вторая.

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

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

Граф без петель и кратных ребер называется простым или обыкновенным.

Рис. 1.2

Если в графе нет рёбер (U=), то он называется пустым или нуль-графом.

Если в простом графе все вершины попарно соединены рёбрами, то граф называется полным.

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

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

Маршрутом в графе называется последовательность вершин и ребер (v₁,u₁,v₂,u₂,…,v_n,u_n,v_n+1)такая, что реброu_kинцидентно вершинамv_kиv_k+1. Цепью называется маршрут, в который каждая вершина входит не более одного раза. Другими словами, цепь – это несамопересекающийся маршрут. На рис. 1.3 (v₆,u₆,v₃,u₃,v₄,u₅,v₅)- цепь,но(v₆,u₆,v₃,u₃,v₄,u₄,v₁,u₁,v₂,u₂,v₃,u₃,v₄,u₅,v₅)– маршрут.

Рис. 1.3

Цепь называется путем, если каждое ее ребро u_kлибо не ориентировано, либо ориентировано в направлении отv_kкv_k+1. Замкнутая цепь называется циклом. Замкнутый путь, называется контуром.

На рис. 1.3 вершины (v₂,v₁,v₄,v₃) с соответствующими ребрами образуют цепь, но не путь, (v₃,v₄,v₅) – путь, (v₁,v₄,v₃,v₂,v₁) – цикл, но не контур, (v₁,v₂,v₃,v₄,v₁) – контур.

Частью G графа G=<V,U> такой, что G=<V,U> и VV, UU, называется граф, вершины и рёбра которого являются подмножеством вершин и рёбер данного графа. Различают несколько видов частей графа.

Подграфом называется часть графа, содержащая его некоторые вершины и рёбра.

Суграфом называется часть графа, содержащая все его вершины, но не все рёбра. Часть графа, не вошедшая в подграф, называется его дополнением.

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

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

Расстоянием между вершинами v_iиv_jd(v_i, v_j)называется количество ребер в минимальной цепи, соединяющей эти вершины. Как и всякая метрическая величина,dобладает следующими свойствами:

1. d(v_i, v_j)=d(v_j, v_i);

2. d(v_i, v_j)  0 , d(v_i, v_j)=0, если v_i= v_j;

3. d(v_i, v_j)+d(v_j, v_k)  d(v_i, v_k), - правило треугольника.

Диаметром графа называется максимальное из всех расстояний между вершинами на графе.

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

То есть

Вершина, для которой r(v)=R(G),называется центром графаG.

Пример:

Операции над графами

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

1. Добавление ребра: если вершины v_i и v_j не смежны, то можно построить граф G+u, где u=(v_i, v_j).

2. Объединение: граф H называется объединением (или наложением) графов F и G, если V_H=V_FV_G и U_H=U_FU_G. Пишут H=GF (рис. 1.6)

Объединение GF называют дизъюнктивным, если V_F*V_G= (рис. 1.5)

Рис. 1.7. Пересечение.

3. Пересечением графов G и F называется граф H такой, что V_H=V_FV_G, U_H=U_FU_G. Обозначается: H=GF

4. Произведением G₁G₂=G называется граф, для которого V_G=V₁V₂ - декартово произведение множеств вершин исходных графов, а U_G строится так: вершины (v¹₁, v₁²) и (v¹₂, v²₂) смежны в графе G тогда и только тогда, когда или v¹₁ =v¹₂, а v₁² и v²₂ соседние в G₂, или v₁²= v₂², а v¹₁ и v¹₂ соседние в G₁.

Рис 1.8

Очевидно,что |G₁G₂| = |G₁|*|G₂|, а |U(G₁G₂)| =|G₁|*R₂+|G₂|*R₁