3.1. Основные определения

3.1.1. Общие понятия

Граф Gзадается множествомвершин(точек) Х = {х₁, ..., х_n} и множествомребер(линий) А = {а₁, .., а_n}, соединяющих между собой все или часть этих вершин. Таким образом, графGполностью определяется заданием двух множеств (Х, А).

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

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

Пример.Для графа, изображенного на рис. 3.1: множество вершинX= {х₀,х₁,х₂,х₃,х₄,х₅} и закон соот­ветствия между вершинами:

G(x ₀) = {x₁, x₂},

G(x₁) = {x₀, x₂, x₄},

G(x₂) = {x₀, x₁, x₅},

G(x₃) = {x₄},

G(x₄) = {x₁, х₃},

G(x₅) = {x₂},

G(x₆) = .

Рис. 3.1. Пример задания графа

Ребра графа– линии, соединяющие вершины, указывают на соответствие между вершинами в графе.

Запись g= (x_i,x_j) говорит, что реброgинцидентновершинам х_iиx_j, а вершины х_i,x_jинцидентныребруg. Две вершины х_i,x_jназы­ваютсясмежными, если они определяют ребро графа. Два ребра графа называютсясмежными, если их концы имеют общую верши­ну.

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

3.1.2. Ориентированные и неориентированные графы

Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не прини­мается во внимание.

Ребро графа называетсяориентированным, если этот порядок существенен. В этом случае говорят, что для ребраg= (x_i,x_j):x_i– начальная,ax_j– конечная вершины ребра.

Ориентирован­ное ребро называют дугой графа (рис. 3.2).

Рис. 3.2. Дуга ориентированного графа

Граф называется неориентиро­ванным или неорграфом, если каждое ребро его не ориентированно, иориентирован­ным или орграфом, если каждое ребро его ориенти­рованно. Если граф содержит ори­ентированные и неориентирован­ные ребра, он называетсясмешанным.

Полным неориентированным графомназывается графU(X), ребрами которого являются всевозможные пары (x_i,x_j) для всех возможных вершинx_i,x_jX,ij. В таком графе все вершины являются смежными (рис. 3.3).

Рис. 3.3. Полные неориентированный и

ориентированный графы

Полным ориентированным графом U₀(X) называ­ется граф, у которого любые две вершины соединены хотя бы в одном направле­нии.

Петлей называется ребро g = (x_i, x_i), у которого начальная и конечная вершины совпадают (рис. 3.4) Петля обычно считается неориентиро­ванной.

Рис. 3.4. Петля

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

Рис. 3.5. Неориентированный и ориентированный мультиграфы

Дополнением графа G(X) является такой граф G_d(X), ко­торый совместно с графом G(X) образуют полный граф: U(X) = G(X)  G_d(X).