Понятие графа

Графом G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е – множество ребер).

Число вершин графа (порядок графа) G обозначим p, а число
ребер – q.

Пусть v₁, v₂ – вершины, е = (v₁, v₂) – соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность – отношение между разнородными элементами.

Пример.

Данная диаграмма изображает граф, имеющий четыре вершины и пять ребер. В этом графе вершины v₁ и v₂ смежны, а вершины v₁ и v₃ не смежны. Смежные ребра: e₁ и e₅. Несмежные ребра: e₁ и e₃. Ребро е₁ инцидентно вершинам v₁ и v₂, вершина v₁ инцидентна ребрам е₁ и е₄.

Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е – дугами.

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

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

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

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

Максимальное число ребер, соединяющих две вершины графа, называется мультичислом графа.

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

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

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с p вершинами обозначается K_p.

Граф G’(V’, E’) называется подграфом графа G(V, E) (обозначается G’ Ì G), если V’ Ì V, а E’ – множество всех ребер G, оба конца которых принадлежат V’.

Двудольный граф (или биграф, или четный граф) – это граф G(V, E), такой что множество V разбито на два непересекающихся множества V₁ и V₂, причем всякое ребро из Е соединяет вершину из V₁ с вершиной из V₂. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V₁ и V₂, то он называется полным двудольным графом. Если ½V₁½ = m и ½V₂½ = n, то полный двудольный граф обозначается K_m,n.

Пример. Диаграмма графа K3,3.

Граф, состоящий из простого цикла с k вершинами, обозначается C_k.

Пример. С3 – треугольник.

Количество ребер, инцидентных вершине v, называется (локальной) степенью (или валентностью) вершины v и обозначается d(v):

0 £ d(v) £ p – 1

Если степени всех вершин равны k, то граф называется регулярным (однородным) степени k.

Пример. Диаграмма регулярного графа степени 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d^–(v) и d⁺(v).

Если в орграфе полустепень захода некоторой вершины равна нулю (т.е. d⁺(v) = 0), то такая вершина называется источником, если же нулю равна полустепень исхода (т.е. d^–(v) = 0), то вершина называется стоком.

Графы G₁ и G₂ равны, то есть G₁ = G₂, если их множества вершин и ребер совпадают: V₁ = V₂ и E₁ = E₂. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

Пример.

Три внешне различные диаграммы являются диаграммами одного и того же графа.

Дополнением графа G(V₁, E₁) называется граф `G(V₂, E₂), где V₂ = V₁ & E₂ = = {e Î V₁ ´ V₁ ½ e Ï E₁}.

G `G