Теоретико-множественное представление графов

Графы и способы их представления

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

Граф задается множеством точек или вершин х₁, х₂,..., х_n и множеством линий или ребер a₁, a₂,..., a_m, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом.

Графом называется двойка вида

G = (X, A),

где X = {x_i}, i = 1, 2,..., n – множество вершин графа, A = {a_i}, i = 1, 2,..., m – множество ребер графа.

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

Рис. 1.2.

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

Дуга a_i может быть представлена упорядоченной парой вершин (х_n, х_k), состоящей из начальной х_n и конечнойх_k вершин. Например, для графа G₁ (рис. 1.2,а) дуга a₁ задается парой вершин (x₂, x₁), а дуга а₃ парой (x₂, x₃). Если х_n, х_k – концевые вершины дуги a_i, то говорят, что вершины х_n и х_k инцидентны дуге a_i или дуга a_iинцидентна вершинам х_n и х_k.

Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе G₃ (рис. 1.2,в) дуга a₇является петлей.

Каждая вершина орграфа х_i может характеризоваться полустепенью исхода d₀(х_i) и полустепенью захода d_t(х_i).

Полустепенью исхода вершины х_i — d₀(х_i) называется количество дуг, исходящих из этой вершины. Например, для орграфа G₁ (рис. 1.2,а) характеристики полустепеней исхода следующие: d₀(х₁)=1, d₀(х₂)=2, d₀(х₃)=2, d₀(х₄)=1.

Полустепенью захода вершины х_i — d_t(х_i) называется количество дуг, входящих в эту вершину. Например, для орграфа G₁: d_t(х₁)=2, d_t(х₂)=1, d_t(х₃)=2, d_t(х₄)=1.

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

где n – число вершин графа, m – число дуг.

Каждая вершина неориентированного графа х_i может характеризоваться степенью вершины d(х_i).

Степенью вершины х_i – d(х_i) называется количество ребер, инцидентных этой вершине. Например, для орграфа G₁(рис. 1.2,б) характеристики степеней следующие: d(х₁)=2, d(х₂)=3, d(х₃)=3, d(х₄)=2.

Способы описания графов

Теоретико-множественное представление графов

Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис. 1.3 и рис. 1.4.

G₄ = (Х, А),

где Х = {х_i}, i = 1, 2, 3, 4 – множество вершин; А = {a_i }, i = 1, 2,..., 6 – множество дуг, причем А = {(х₁, х₂), (х₄, х₂), (х₂, х₄), (х₂, х₃), (х₃, х₃), (х₄, х₁)}.

Рис. 1.3.

G₅ = (X, A),

где X = {B, C, D, E, F} – множество вершин графа, A = {a_i}, i = 1, 2,..., 5 – множество дуг графа, причем a₁ = (F, B), a₂ = (B, E), a₃ = (F, D), a₄ = (E, C), a₅ = (C, D).

Рис. 1.4.

Задание графов соответствием

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

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины х_i — Г(х_i) является множество вершин, в которые существуют дуги из вершины х_i, т. е. .

Так для орграфа на рис. 1.3 описание заданием множества вершин и соответствия выглядит следующим образом:

G₄=(X, Г),

где X = {х_i}, I = 1, 2,..., 4 – множество вершин, Г(х₁) = { х₂ }, Г(х₂) = { х₃, х₄ }, Г(х₃) = { х₃ },Г(х₄) = { х₁, х₂ } – отображения.

Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис. 1.2,бГ(х₂) = { х₁, х₃, х₅ }, Г(х₄) ={ х₃, х₅} и т. д.