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

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

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

Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом.

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

G = (X, A),

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

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

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


Рис. 1.2.

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

Дуга ai может быть представлена упорядоченной парой вершин (хn, хk), состоящей из начальной хn и конечнойхk вершин. Например, для графа G1 (рис. 1.2,а) дуга a1 задается парой вершин (x2, x1), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга aiинцидентна вершинам хn и хk.

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

Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0i) и полустепенью захода dti).

Полустепенью исхода вершины хi — d0i) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис. 1.2,а) характеристики полустепеней исхода следующие: d01)=1, d02)=2, d03)=2, d04)=1.

Полустепенью захода вершины хi — dti) называется количество дуг, входящих в эту вершину. Например, дляорграфа G1: dt1)=2, dt2)=1, dt3)=2, dt4 )=1.

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

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

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

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

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

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

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

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

G4 = (Х, А),

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

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


Рис. 1.3.

G5 = (X, A),

где X = {B, C, D, E, F} – множество вершин графа, A = {ai}, i = 1, 2, ..., 5 – множество дуг графа, причем a1 = (F, B), a2 = (B, E), a3 = (F, D), a4 = (E, C), a5 = (C, D).

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


Рис. 1.4.

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

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

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

Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Теоретико-множественное представление графов - student2.ru .

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

G4=(X, Г),

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

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

Наши рекомендации