Графы. Общие понятия

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

Рисунок 1. Общий вид графа.

Пример: схема автомобильных дорог, связывающих города некоторой области, является характерным примером графа.

Таким образом, граф задается множеством вершин и множеством ребер. Запись G=(V,X), V={V₁, V₂, V₃}, X={X₁={V₁,V₂}, X₂={V₁,V₃}}, определяет граф G с тремя вершинами V₁, V₂, V₃ и двумя ребрами X₁, X₂. Ребро X₁ соединяет вершины V₁ и V₂, X₂соединяет вершины V₁ и V₃.

Ориентированный граф – это граф, у которого пары в наборе X являются упорядоченными (т.е. ребро имеет начало и конец), графы с неупорядоченными парами из X, называются неориентированными.

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

Пример: пусть 2V={V₁,V₂,V₃}, X={x₁{V₁,V₂},x₂={V₂,V₁},x₃={V₂,V₃}}

Тогда D=(V,X) – ориентированный граф.

Дуга – это направленное ребро в орграфе.

Пример: в приведенном выше примере для орграфа D=(V,X)дугами являются ребра x₁, x₂, x₃

Смешанный граф – это граф, содержащий как дуги, так и ненаправленные ребра.

Рисунок 3. Смешанный граф.

Петля – ребро графа, начальная и конечная вершины которого совпадают.

Рисунок 4. Ориентированный граф с петлями.

Пример: пусть D=(V,X) – ориентированный граф, V={V₁,V₂,V₃},

X={x₁={V₁,V₁},x₂={V₁,V₂},x₃{V₂,V₂},x₄{V₁,V₂},x₅{V₃,V₃}}, тогда x₁,x₃,x₅ – петли.

Пара (или большее число) ребер, соединяющих одни и те же вершины, например xi и xj, являются параллельными и называются кратными.

Изолированная вершина – вершина, в которую не входит ни одно ребро и ни одно не выходит из нее.

Рисунок 5. Граф с изолированными вершинами.

Пример: пусть D=(V,X) – ориентированный граф, V = {V₁,V₂V₃,V₄}, X={x₁={V₂,V₃},x₂ ={V₃,V₂}} тогда V₁,V₄ – изолированные вершины.

Вершина V инцидентна дуге x тогда и только тогда, когда V является либо началом, либо концом дуги x.

Рисунок 6. Вершины V₁ и V₂ инцидентны дуге x₁.

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

Рисунок 7 (а) и (б).

Пример: вершины V₁ и V₂ смежны, т.к. существует ребро x, инцидентное им обоим (рис (а)). Ребра x₁ и x₂ смежны, т.к. существует вершина V, инцидентная им обоим (рис (б)).

Пустой граф – граф G=(X,R),в котором R=ø.

Рисунок 8. Пустой граф

Пример: пусть G=(X,R) – граф, изображенный на рисунке 8. Он является пустым, т.к. R=ø,X={x₁, x₂ x₃}

Полный граф – граф G=(X,R),в котором любая пара вершин соединена единственным ребром.

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

Маршрут длины H – чередующаяся последовательностьx₁, u₁ x₂,...,u_h,x_h+1 вершин x_i и ребер u_i, обладающих тем свойством, что пара соседних элементов соединена.

Рисунок 10.

Пример: изображённая на рисунке 10 последовательность вершин V₁x₁V₂x₃V₄x₄V₃ является маршрутом длины 3, соединяющим вершины V₁V₃ в этом графе.

Цепь – маршрут, в котором все ребра различны.

Рисунок 11.

Пример:пусть D=(V,X) – ориентированный граф, приведенный на рисунке 11. Тогда V₁x₂V₂x₃V₂x₄V₃ – цепь из V₁ в V₃ длины 3.

Простая цепь – цепь, в которой все вершины различны.

Пример: для ориентированного графа D=(V,X), приведенного на рисунке 11, V₁x₁V₂x₄V₃ и V₁x₂V₂x₄V₃ – простые цепи из V₁ в V₃длины 2.

Минимальная длина простой цепи с началом в V₁ и концом в V₂ называется расстоянием между этими вершинами. – цепь, в которой все вершины различны.

Рисунок 12.

Цикл – цепь, у которой начальная и конечная вершина совпадают.

Рисунок 13.

Пример: пусть G=(X,R) – граф, показанный на рисунке 13, тогда x₁y₁x₂y₂x₃y₃x₁ – цикл.

Рисунок 14 (а), (б).

Пример: пусть G=(X,R) – исходный граф, показанный на рисунке 14 (а), тогда G'=(X',R') – некоторый подграф графа G=(X,R) (рисунок (б)).

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

Пример: оба графа, которые были приведены на рисунках 14 (а) и (б), являются также связанными графами.

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

Рисунок 15 (а),(б).

Пример: следующие два ориентированных графа, показанных на рисунках 15 (а) и (б), являются сильносвязанными орграфами.

Обыкновенный граф – неориентированный граф, который не содержит параллельных ребер и петель; орграф, который не содержит строго параллельных дуг и петель.

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

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

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

Пример: граф G, изображенный на рисунке 17, является деревом. Из рисунка видно, что выполняется соотношение |V|=|R+1|=11 (в нашем случае).