При решении практических задач довольно часто возникает необходимость
указывать направление на ребрах графа (ориентировать ребра).
Определение. Ориентированным графом (сокращенно: орграфом)
называется множество точек и соединяющих эти точки ориентированных непрерывных
линий.
Точки, как и прежде, будем называть вершинами, ориентированные
линии – дугами графа. Орграф часто будем обозначать парой (V,E), где V –
множество вершин, Е – множество дуг графа. При изображении орграфа ориентацию
будем указывать стрелкой на дуге (см. рис. 6.1). Если дуга е, соединяющая
вершины x и y, ориентирована от х и y, то будем говорить, что х – начало
дуги и х – конец дуги е, или что дуга е выходит из х и заходит
в y. Такую дугу е будем иногда называть (x,y)–дугой. Например, дуга е2
выходит из вершины а и заходит в вершину b (см. рис. 6.1).
Вершины x и y будем называть смежными, если существует (x,y)–дуга
или (y,x)–дуга. Если дуга е соединяет вершины x и y, то будем говорить, что е инцидентна
вершинам x и y.
Рис. 6.1
Дугу, выходящую из
некоторой вершины и заходящую в ту же вершину, будем называть петлей, а дуги, выходящие из одной и той
же вершины и заходящие в одну и ту же вершину, будем называть кратными. Так, дуги е5 и е6
являются кратными, а дуга е1 – петлей (см. рис. 6.1). Вершину,
из которой не выходит и в которую не заходит ни одна дуга, будем называть изолированной. Например, i –
изолированная вершина.
Обобщим понятие
степени вершины для орграфов.
Определение. Пусть G – орграф. Полустепенью исхода r–(v) вершины v графа G
называется число дуг, выходящих из v, полустепенью захода r+(v) – число дуг,
заходящих в v.
Например, для графа,
изображенного на рис. 6.1, имеем, что r–(b)=2, r+(b)=1, r–(c)=0, r+(c)=3.
Следующее утверждение
достаточно очевидно.
Предложение. Сумма полустепеней исхода всех вершин графа
равна суммe полустепеней захода всех вершин.
Определение. Вершина v ориентированного графа называется источником, если r+(v)¹0 и r–(v)¹0, и стоком, если r+(v)¹0 и r–(v)=0.
Так для графа на
рис. 6.1 вершина с является стоком, а источника этот граф не имеет. Ясно,
что орграф может иметь несколько источников и стоков.
Ориентированные графы
возникают в различных областях. Так, например, блок–схема алгоритма решения
задачи является ориентированным графом, где вершинами являются блоки. Схема
различных коммуникаций с односторонним движением, эйлеров граф с указанным
направлением обхода ребер, схема маршрутов движения на местности – примеры
ориентированных графов.
Как и в
неориентированном случае, мы будем задавать орграф, изображая на рисунке
соответствующую геометрическую фигуру. Однако для решения задач, связанных с
графами на компьютере, такое задание графа является неудобным. Для задания
графа в этих случаях используются фактически те же способы, что и в
неориентированном случае. Пусть n – число вершин, m – число ребер орграфа
G=(V,E), V={v1,v2,…,vn} и E={e1,e2,…em}.
Матрица инцидентности графа G – это
матрица A=(aij) размера n´m такая, что
Матрица смежности графа G – это квадратная матрица B=(bij)
порядка n такая, что bij есть число дуг с началом в вершине vi
и концов в vj. На рис. 6.2 и 6.3 приведены примеры задания
графов соответственно матрицами инцидентности и смежности.
Рис. 6.2
Рис. 6.3
Для задания орграфов
используются также списки смежностей
и список дуг. В первом случае для каждой вершины v формируется список
вершин, в которые заходят дуги, выходящие из v. В списке дуг каждая дуга е
представляется парой вершин (x,y), где х – начало, y – конец дуги е.
Введем понятие
изоморфизма для орграфов.
Определение. Орграфы G1=(V1,E1)
и G2=(V2,E2) изоморфны, если существует биекция j: V1®V2 такая, что для любых вершин x,yÎV1 число
(x,y)–дуг из Е1 равно числу (j(x), j(y)) – дуг из Е2.
Графы G1 и
G2, изображенные на рис. 6.4, изоморфны; биекция j определяется нумерацией вершин.
Нам понадобится также
понятие подграфа.
Определение. Орграф G′=(V′,E′) называется подграфом орграфа G=(V,E), если V′ÍV, E′ÍE и если дуга e инцидентна вершинам x и y и eÎE′, x,yÎV′. Если V′=V, то подграф G′ называется суграфом.
Примеров приводить не
будем, поскольку понятие подграфа в ориентированном случае полностью аналогично
такому же понятию в неориентированном случае.
Рис. 6.4
В заключение параграфа
рассмотрим орграфы без кратных дуг. Такому графу G очевидным образом ставится в
соответствие бинарное отношение R, заданное на множестве вершин:
(x,y)ÎRÛ в графе G существует
(x,y)–дуга.
В этом случае граф G
мы будем иногда называть графом бинарного
отношения R. Например, графу G,
изображенному на рис. 6.5,
Рис. 6.5
соответствует
отношение R={(a,a), (a,b), (a,c), (a,d), (c,d), (d,a)}, заданное на множестве
V={a,b,c,d}.
|