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

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

Граф G — это математический объект, состоящий из множества вершин X = {.Г], х2,..., и множества ребер А = {alt а2,

..., ап). Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, А).

Для многих задач несущественно, являются ли ребра отрезками прямых или криволинейными дугами; важно лишь то, какие вершины соединяет каждое ребро.

Существует два основных вида графов (и множество их подвидов) — ориентированные и неориентированные.

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным (табл. 3.1). Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом) (табл. 3.2).

Таблица 3.1

Примеры ориентированных графов

Граф

Вершины

Дуги

Обучение

Курсы

Необходимое предшествование (например, курс по языку Pascal полезно изучить прежде, чем курс по Delphi, и г.п.)

Одевание

ребенка

Предметы

гардероба

Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.)

Организация

Сотрудники

Иерархия (начальник — подчиненный)

Таблица 3.2

Примеры неориентированных графов

Граф

Вершины

Ребра

Семья

Люди

Родственные связи

Город

Перекрестки

Улицы

Сеть

Компьютеры

Кабели

Метро

Станции

Пересадки

Листок в клеточку

Клеточки

Наличие общей границы

Пример 3.1. На рис. 3.1 изображен неориентированный граф G = (X, А):

Пример смешанного графа

Рис. 3.3. Пример смешанного графа

Пример неориентированного графа

Рис. 3.1. Пример неориентированного графа

Пример 3.2. На рис. 3.2 изображен ориентированный граф G = (X, А): Пример ориентированного графа

Рис. 3.2. Пример ориентированного графа

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

Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным (рис. 3.3).

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

Граф, содержащий кратные ребра, называется мультиграфом (рис. 3.4).

Пример мультиграфа

Рис. 3.4. Пример мультиграфа

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

Ребро может соединять вершину саму с собой. Такое ребро называется петлей (рис. 3.5).

Пример петли графа, пример псевдографа

Рис. 3.5. Пример петли графа, пример псевдографа

Граф с кратными ребрами и петлями называется псевдографом.

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Например, на рис. 3.6 изображен граф G = (X, Л), где X = {а, b, с, d}y А = 0.

Пример графа, не имеющего ребер

Рис. 3.6. Пример графа, не имеющего ребер

Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины х и у инцидентны ребру а, если эти вершины соединены а.

Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину.

Степенью вершины графа называется число ребер, инцидентных этой вершине.

Вершина, имеющая степень 0, называется изолированной, а степень 1 — висячей.

Например, для графа, расположенного на рис. 3.7, число ребер, инцидентных вершине (d): d(d) = 1; d(b) = 3; d(b) = 2; d{e) = 2; d(f) = 0.

Пример графа с изолированной и висячей вершинами

Рис. 3.7. Пример графа с изолированной и висячей вершинами

Необходимость учитывать ориентацию ребер в ориентированном графе приводит к расщеплению понятия «степень вершины» на две части — полустепепъю захода вершины vd - (Vj)] называется число ребер, заходящих в vv полустепепъю исхода vd + (?;,)] — число ребер, выходящих из нее.

Граф, степени всех вершин (к) которого одинаковы, называется однородным графом степени к.

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

Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G(x), т.е. G(x) = {у: (х, у) е G).

Множество G(x) называют образом вершины х. Соответственно G~x(y) — множество вершин, из которых исходят дуги, ведущие в вершину у G~x(y) = {х (х, у) е G). Множество G~l(y) называют прообразом вершины у.

Пример 3.3. В ориентированном графе, изображенном на рис. 3.8, началом дуги ах является вершина х1? а ее концом — вершина х2; вершина xt инцидентна дугам а{ и а2 G(x{) = {х2, х3}, G(x2) = 0, G x3) = {xj, G~'{xx) = 0.

Пример ориентированного графа Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G

Рис. 3.8. Пример ориентированного графа Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа (рис. 3.9).

Пример графа и его подграфов

Рис. 3.9. Пример графа и его подграфов:

а — граф; б — подграф (1); в — подграф (2); г — подграф (3) Граф G = (X, А) — полный, если для любой пары вершин Xj и хj существует ребро (х,-, Xj). Примеры полных графов представлены на рис. 3.10.

Примеры полных графов

Рис. 3.10. Примеры полных графов

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

Граф G = (X, А) — симметрический (рис. 3.11), если для любой дуги (Xj, Xj) существует противоположно ориентированная дуга (xj, xt).

Пример симметрического графа

Рис. 3.11. Пример симметрического графа

Граф G = (X, А) — планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг (рис. 3.12-3.13).

Пример неочевидного планарного графа

Рис. 3.12. Пример неочевидного планарного графа

Пример очевидного планарного графа (тот же, что и на рис. 3.12)

Рис. 3.13. Пример очевидного планарного графа (тот же, что и на рис. 3.12)

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >