Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети

§1. Понятие орграфа

При решении практических задач довольно часто возникает необходимость указывать направление на ребрах графа (ориентировать ребра).


Определение. Ориентированным графом (сокращенно: орграфом) называется множество точек и соединяющих эти точки ориентированных непрерывных линий.

Точки, как и прежде, будем называть вершинами, ориентированные линии – дугами графа. Орграф часто будем обозначать парой (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}.

§2. Обходы в орграфах

§3. Бесконтурные графы

§4. Пути в сетях

§5. Потоки в сетях

Задачи

Ответы указания и решения


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru