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

Определение 2.17. Если f - функция, то Df - область определения, а Rf - область значений функции f.

Пример 2.23.

Для примера 2.22 а) Df - {1, 3, 4, 5}; Rf - {2, 4, 6}.

Для примера 2.22 б) Df = Rf = (-, ).

Каждому элементу x Df функция ставит в соответствие единственный элемент y Rf. Это обозначается хорошо известной записью y = f(x). Элемент x называется аргументом функции или прообразом элемента y при функции f, а элемент y значением функции f на x или образом элемента x при f.

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

Определение 2.18. Если Df = X и Rf = Y, то говорят, что функция f определена на X и принимает свои значения на Y, а f называют отображением множества X на Y (X Y).

Определение 2.19. Функции f и g равны, если их область определения - одно и то же множество D, и для любого x D справедливо равенство f(x) = g(x).

Это определение не противоречит определению равенства функций как равенства множеств (ведь мы определили функцию как отношение, т. е. множество): множества f и g равны, тогда и только тогда, когда они состоят из одних и тех же элементов.

Определение 2.20. Функция (отображение) f называется сюръективной или просто сюръекцией, если ля любого элемента y Y существует элемент x X, такой, что y = f(x).

Таким образом, каждая функция f является сюръективным отображением (сюръекцией) Df Rf.

Если f - сюръекция, а X и Y - конечные множества, то .

Определение 2.21. Функция (отображение) f называется инъективной или просто инъекцией или взаимно однозначной, если из f(a) = f(b) следует a = b.

Определение 2.22. Функция (отображение) f называется биективной или просто биекцией, если она одновременно инъективна и сюръективна.

Если f - биекция, а X и Y - конечные множества, то =.

Определение 2.23. Если область значений функции Df состоит из одного элемента, то f называется функцией-константой.

Пример 2.24.

а) f(x) = x2 есть отображение множества действительных чисел на множество неотрицательных действительных чисел. Т.к. f(-a) = f(a), и a -a, то эта функция не является инъекцией.

б) Для каждого xR = (-, ) функция f(x) = 5 - функция-константа. Она отображает множество R на множество {5}. Эта функция сюръективна, но не инъективна.

в) f(x) = 2x + 1 является инъекцией и биекцией, т.к. из 2x1 +1 = 2x2 +1 следует x1 = x2.

Определение 2.24. Функция, реализующая отображение X1 X2 ... Xn Y называется n-местной функцией.

Пример 2.25.

а) Сложение, вычитание, умножение и деление являются двуместными функциями на множестве R действительных чисел, т. е. функциями типа R2 R.

б) f(x, y) = - двуместная функция, реализующая отображение R (R \ ) R. Эта функция не является инъекцией, т.к. f(1, 2) = f(2, 4).

в) Таблица выигрышей лотереи задает двуместную функцию, устанавливающую соответствие между парами из N2 (N - множество натуральных чисел) и множеством выигрышей.

Поскольку функции являются бинарными отношениями, то можно находить обратные функции и применять операцию композиции. Композиция любых двух функций есть функция, но не для каждой функции f отношение f-1 является функцией.

Пример 2.26.

а) f = {1, 2>, <2, 3>, <3, 4>, <4, 2>} - функция.

Отношение f-1 = {<2, 1>, <3, 2>, <4, 3>, <2, 4>} не является функцией.

б) g = {<1, a>, <2, b>, <3, c>, <4, D>} - функция.

g-1 = {<a, 1>, <b, 2>, <c, 3>, <D, 4>} тоже функция.

в) Найдем композицию функций f из примера а) и g-1 из примера б). Имеем g-1f = {<a, 2>, <b, 3>, <c, 4>, <d, 2>}.

fg-1 = .

Заметим, что (g-1f)(a) = f(g-1(a)) = f(1) = 2; (g-1f)(c) = f(g-1(c)) = f(3) = 4.

Элементарной функцией в математическом анализе называется всякая функция f, являющаяся композицией конечного числа арифметических функций, а также следующих функций:

1) Дробно-рациональные функции, т.е. функции вида

a0 + a1x + ... + anxn

b0 + b1x + ... + bmxm.

2) Степенная функция f(x) = xm, где m - любое постоянное действительное число.

3) Показательная функция f(x) = ex.

4) логарифмическая функция f(x) = logax, a >0, a 1.

5) Тригонометрические функции sin, cos, tg, ctg, sec, csc.

6) Гиперболические функции sh, ch, th, cth.

7) Обратные тригонометрические функции arcsin, arccos и т.д.

Например, функция log2(x3 +sincos3x) является элементарной, т.к. она есть композиция функций cosx, sinx, x3, x1 + x2, logx, x2.

Выражение, описывающее композицию функций, называется формулой.

Для многоместной функции справедлив следующий важный результат, полученный А. Н. Колмогоровым и В. И. Арнольдом в 1957 г. и являющийся решением 13-ой проблемы Гильберта:

Теорема. Всякая непрерывная функция n переменных представима в виде композиции непрерывных функций двух переменных.

Способы задания функций

1. Наиболее простой способ задания функций - это таблицы (табл. 2.2):

Таблица 2.2

x	x1	x2	...	xn
f(x)	f(x1)	f(x2)	...	f(xn)

Пример 2.27.

Бросается игральная кость. Пусть k - число выпавших очков, а p(k) - вероятность того, что при случайном бросании кости выпадет k очков, k = 1, 2, ..., 6.

В этом случае функция p(k) может быть задана следующей таблицей (табл. 2.3):

Таблица 2.3

k	1	2	3	4	5	6
p(k)	1/6	1/6	1/6	1/6	1/6	1/6

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

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

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

Пример 2.28.

f(x) = sin(x + x) является композицией следующих функций:

g(y) = y; h(u, v) = u + v; w(z) = sinz.

3. Функция может быть задана в виде рекурсивной процедуры. Рекурсивная процедура задает функцию, определенную на множестве натуральных чисел, т. е. f(n), n = 1, 2,... следующим образом: а) задается значение f(1) (или f(0)); б) значение f(n + 1) определяется через композицию f(n) и других известных функций. Простейшим примером рекурсивной процедуры является вычисление n!: а) 0! = 1; б) (n + 1)! = n!(n + 1). Многие процедуры численных методов являются рекурсивными процедурами.

4. Возможны способы задания функции, не содержащие способа вычисления функции, а только описывающие ее. Например:

fM(x) =

Функция fM(x) - характеристическая функция множества M.

Итак, по смыслу нашего определения, задать функцию f - значит задать отображение X Y, т.е. определить множество XY, поэтому вопрос сводится к заданию некоторого множества. Однако можно определить понятие функции, не используя языка теории множеств, а именно: функция считается заданной, если задана вычислительная процедура, которая по заданному значению аргумента находит соответствующее значение функции. Функция, определенная таким образом, называется вычислимой.

Пример 2.29.

Процедура определения чисел Фибоначчи, задается соотношением

Fn = Fn-1 + Fn-2 (n 2) (2.1)

с начальными значениями F0 = 1, F1 = 1.

Формула (2.1) вместе с начальными значениями определяет следующий ряд чисел Фибоначчи:

n	0 1 2 3 4 5 6 7 8 9 10 11 …
Fn	1 1 2 3 5 8 13 21 34 55 89 144 …

Вычислительная процедура определения значения функции по заданному значению аргумента есть не что иное, как алгоритм.

Контрольные вопросы к теме 2

1. Укажите способы задания бинарного отношения.

2. Главная диагональ матрицы какого отношения содержит только единицы?

3. Для какого отношения всегда выполняется условие = -1?

4. Для какого отношения всегда выполняется условие .

5. Ввести отношения эквивалентности и частичного порядка на множестве всех прямых на плоскости.

6. Укажите способы задания функций.

7. Какое из следующих утверждений справедливо?

а) Всякое бинарное отношение есть функция.

б) Всякая функция есть бинарное отношение.

Тема 3. ГРАФЫ

Первая работа по теории графов принадлежащая Эйлеру, появилась в 1736 году. Вначале эта теория была связана с математическими головоломками и играми. Однако впоследствии теория графов стала использоваться в топологии, алгебре, теории чисел. В наше время теория графов находит применение в самых разнообразных областях науки, техники и практической деятельности. Она используется при проектировании электрических сетей, планировании транспортных перевозок, построении молекулярных схем. Применяется теория графов также в экономике, психологии, социологии, биологии.

3.1 Основные характеристики графов

Граф G - это математический объект, состоящий из множества вершин X = {x1, x2,..., xn} и множества ребер A = {a1, a2,..., an}. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A).

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

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

Пример 3.1.

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

X = {x1, x2, x3, x4},

A = {a1= (x1, x2), a2=(x2, x3), a3=(x1, x3), a4= (x3, x4)}.

Рис. 3.1.

Пример 3.2.

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

X = {x1, x2, x3, x4},

A = {a1 = (x1 , x2 ), a2 = (x1 , x3 ), a3 = (x3 , x4 ), a4 = (x3 , x2 )}.

Рис. 3.2.

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

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

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

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

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым.

Пример 3.3.

На рис. 3.3. изображен ориентированный граф G = (X, A).

X = {x1 , x2 , x3 , x4 },

A = .

Риc. 3.3.

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

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

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

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

Пример 3.4.

В графе, изображенном на рис. 3.1, концами ребра a1 являются вершины x1, x2; вершина x2 инцидентна ребрам a1, a2; степень вершины x3 равна 3; вершины x1 и x3 смежные; ребра a1 и a2 смежные; вершина x4 висячая. В ориентированном графе, изображенном на рис. 3.2, началом дуги a1 является вершина x1, а ее концом - вершина x2; вершина x1 инцидентна дугам a1 и a2; G(x1) = {x2, x3}, G(x2) =, G-1(x3) = {x1}, G-1(x1) = .

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

Граф G = (X, A) - полный, если для любой пары вершин xi и xj существует ребро (xi, xj).

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

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

Неориентированный граф G = (X, A) - двудольный, если множество его вершин X можно разбить на два такие подмножества X1 и X2, что каждое ребро имеет один конец в X1, а другой в X2.

3.2 Матричные способы задания графов

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

Матрица смежности A = (aij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой

aij =

Пример 3.5.

Матрица смежности графа, изображенного на рис. 3.1, имеет вид:

A =

Пример 3.6.

Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид:

A =

Матрица смежности полностью задает граф.

Матрицей инцидентности B = (bij) ориентированного графа называется прямоугольная матрица (n m), где n - число вершин, m - число ребер, у которой

bi =

Для неориентированного графа матрица инцидентности B задается следующим образом:

bi =

Пример 3.7.

Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид:

B =

Пример 3.8.

Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид:

B =

Матрица инцидентности, также, как и матрица смежности, полностью задает граф.

Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.

Основные свойства матриц смежности и инцидентности

1. Матрица смежности неориентированного графа является симметричной. Для ориентированного графа это, вообще говоря, неверно.

2. Сумма элементов i - ой строки или i -го столбца матрицы смежности неориентированного графа равна степени вершины xi.

3. Сумма элементов i - ой строки матрицы смежности ориентированного графа равна числу дуг, исходящих из xi.

4. Сумма элементов i - го столбца матрицы смежности ориентированного графа равна числу дуг, входящих в вершину xi.

5. Сумма строк матрицы инцидентности ориентированного графа является нулевой строкой.

Итак, возможны следующие различные способы задания графа:

а) посредством графического изображения;

б) указанием множества вершин и множества ребер (дуг);

в) матрицей смежности;

г) матрицей инцидентности.

3.3 Изоморфизм графов

Графы G1 = (X1, A1) и G2 = (X2, A2) изоморфны, если существует взаимно однозначное соответствие между множествами вершин X1 и X2, такое, что любые две вершины одного графа соединены тогда и только тогда, когда соответствующие вершины соединены в другом графе.

Пример 3.9

Графы, изображенные на рис. 3.4 являются изоморфными.



Рис. 3.4

Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.

3.4 Маршруты, циклы в неориентированном графе

Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a1, a2,... an..., что каждые соседние два ребра ai и ai+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a1,a2,...an) имеется первое ребро a1 и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an-1, называется концом маршрута.

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

Пример 3.10.

В изображенном на рис. 3.5 графе рассмотрим два маршрута из вершины x1 в вершину x4: M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6). Длина маршрута M1 равна 3, а длина маршрута M2 равна 4.

Рис.3.5

Замкнутый маршрут называется циклом.

Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом).

Пример 3.11.

В приведенном на рис 3.6 графе выделим следующие маршруты:

(a1,a3,a4) - простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны;

(a2,a4,a3) - простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны;

(a1,a2,a4,a3) - цепь, которая является простой, но не элементарной, т.к. все ребра различны, но вершина x2 встречается дважды;

(a1,a2,a2) -маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. ребро a2 и вершина x2 встречаются дважды.

Рис.3.6

3.5 Пути, контуры в ориентированном графе

Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе.

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

Число дуг пути называется длиной пути.

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

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

Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.

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

Неориентированный граф	Ориентированный граф
ребро маршрут цикл	дуга путь контур

Пример 3.12.

В приведенном на рис 3.7 графе выделим следующие пути:

(x1,x2,x3,x4) - простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза;

(x2,x5,x6,x7,x2) - простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.



Рис. 3.7

3.6 Связность графа

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

Ориентированный граф называется сильно связным, если для любых двух его вершин xi и xj существует хотя бы один путь, соединяющий xi с xj.

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

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

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

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

Пусть G = (X, A) неориентированный граф с множеством вершин X = {x1,...,xn}. Квадратная матрица S = (sij) порядка n, у которой

sij =

называется матрицей связности графа G.

Для ориентированного графа квадратная матрица T = (tij) порядка n, у которой

tij =

называется матрицей односторонней связности (достижимости).

Квадратная матрица S = (sij) порядка n, у которой

sij =

называется матрицей сильной связности.

Пример 3.13.

У неориентированного графа, изображенного на рис. 3.8 две компоненты связности. Первая компонента связности включает вершины x1, x2, x4, x5, а вторая состоит из одной вершины x3.

Рис.3.8

Матрица связности этого графа имеет вид:

S =

Мы видим, что 1-ая, 2-ая, 4-ая и 5-ая строки матрицы S одинаковы.

Пример 3.14.

У ориентированного графа, изображенного на рис. 3.9 две компоненты сильной связности. Первая компонента связности включает вершины x1, x2, x3, x5, а вторая состоит из одной вершины x4. Действительно, для любой пары вершин из множества {x1, x2, x3, x5} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x1, x2, x5, x3, x1) соединяет все эти вершины. Из вершины x4 нет пути ни в одну вершину графа.

Рис. 3.9

Матрица сильной связности этого графа имеет вид:

S =

Мы видим, что 1-ая, 2-ая, 3-ая и 5-ая строки матрицы S одинаковы.

3.7 Экстремальные пути в нагруженных ориентированных графах

Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так что дуге (xi,xj) сопоставлено некоторое число c(xi,xj) = cij, называемое длиной (или весом, или стоимостью дуги). Длиной (или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (xi,xj), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е.

l(s) = cij,

причем суммирование ведется по всем дугам (xi, xj) s.

Матрица C = (cij) называется матрицей длин дуг или матрицей весов.

Рис. 3.10

Для графа, изображенного на рис. 3.10, матрица C имеет вид:

C =

Длина пути (x1, x2, x5, x4) равна 1 + 5 + 6 = 12.

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

Для нахождения минимального пути между двумя произвольными вершинами для случая, когда все cij 0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана и др. [2,3,5].

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

3.8 Алгоритм Форда - Беллмана нахождения минимального пути

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

Алгоритм 3.1 (Алгоритм Форда - Беллмана).

Основными вычисляемыми величинами этого алгоритма являются величины lj(k), где i = 1, 2, … , n (n - число вершин графа); k = 1, 2, … , n - 1. Для фиксированных i и k величина lj(k) равна длине минимального пути, ведущего из заданной начальной вершины х1 в вершину хi и содержащего не более k дуг.

Шаг 1. Установка начальных условий.

Ввести число вершин графа n и матрицу весов C = (cij).

Шаг 2. Положить k = 0. Положить li(0) = для всех вершин, кроме х1; положить l1(0) = 0.

Шаг 3. В цикле по k, k = 1,..., n - 1, каждой вершине xi на k-ом шаге приписать индекс li(k) по следующему правилу:

li(k) = {lj(k - 1) + cji} (3.1)

для всех вершин, кроме х1, положить l1(k) = 0.

В результате работы алгоритма формируется таблица индексов li(k), i = 1, 2, … , n, k = 0, 1, 2, … , n - 1. При этом ?i(k) определяет длину минимального пути из первой вершины в i-ую, содержащего не более k дуг.

Шаг 5. Восстановление минимального пути.

Для любой вершины xs предшествующая ей вершина xr определяется из соотношения:

lr(n - 2) + crs = ls(n - 1), xr G-1(xs), (3.2)

где G-1(xs) - прообраз вершины xs.

Для найденной вершины xr предшествующая ей вершина xq определяется из соотношения:

lq(n - 3) + cqr = lr(n - 2), xq G-1(xr),

где G-1(xr) - прообраз вершины xr, и т. д.

Последовательно применяя это соотношение, начиная от последней вершины xi , найдем минимальный путь.

Пример 3.15.

С помощью алгоритма 3.1 найдем минимальный путь из вершины х1 в вершину х3 в графе, изображенном на рис. 3.10.

Рис. 3.10

Рассмотрим подробно работу алгоритма Форда - Беллмана для этого примера. Значения индексов li(k) будем заносить в таблицу индексов (табл. 3.1).

Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа имеет вид:

C = .

Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = . Эти значения занесем в первый столбец табл. 3.1.

Шаг 3.

k = 1.

l1(1) = 0.

Равенство (7.1) для k = 1 имеет вид:

li(1) = {lj(0) + cji}.

l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 + 1; + ; + ; + ; + } = 1.

l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ; + 8; + ; + 2; + } = .

l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ; + 7; + 1; + ; + 4} = .

l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 + 3; + 1; - 5; + ; + } = 3.

Полученные значения li(1) занесем во второй столбец табл. 3.1. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.

k = 2.

l1(2) = 0.

Равенство (3.1) для k = 2 имеет вид:

li(2) = {lj(1) + cji}.

l2(2) = min{0 + 1; 1 + ; + ; + ; 3 + } = 1.

l3(2) = min{0 + ; 1 + 8; + ; + 2; 3 + } = 9 .

l4(2) = min{0 + ; 1 + 7; + 1; + ; 3 + 4} = 7 .

l5(2) = min{0 + 3; 1 + 1; - 5; + ; 3 + } = 2.

Полученные значения li(2) занесем в третий столбец табл. 3.1. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.

k = 3.

l1(3) = 0.

Равенство (3.1) для k = 3 имеет вид:

li(3) = {lj(2) + cji}.

l2(3) = min{0 + 1; 1 + ; 9 + ; 7 + ; 2 + } = 1.

l3(3) = min{0 + ; 1 + 8; 9 + ; 7 + 2; 2 + } = 9 .

l4(3) = min{0 + ; 1 + 7; 9 + 1; 7 + ; 2 + 4} = 6 .

l5(3) = min{0 + 3; 1 + 1; 9 - 5; 7 + ; 2 + } = 2.

Полученные значения li(3) занесем в четвертый столбец табл. 3.1. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.

k = 4.

l1(4) = 0.

Равенство (3.1) для k = 4 имеет вид:

li(4) = {lj(3) + cji}.

l2(4) = min{0 + 1; 1 + ; 9 + ; 6 + ; 2 + } = 1.

l3(4) = min{0 + ; 1 + 8; 9 + ; 6 + 2; 2 + } = 8 .

l4(4) = min{0 + ; 1 + 7; 9 + 1; 6 + ; 2 + 4} = 6 .

l5(4) = min{0 + 3; 1 + 1; 9 - 5; 6 + ; 2 + } = 2.

Полученные значения li(4) занесем в пятый столбец табл. 3.1. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.

Таблица 3.1

I (номер вершины)	li(0) li(1) li(2) li(3) li(4)
1 2 3 4 5	0 0 0 0 0 1 1 1 1 9 9 8 7 6 6 3 2 2 2

Шаг 5. Восстановление минимального пути.

Для последней вершины x3 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =3:

lr(3) + cr3 = l3(4), xr G-1(x3), (3.3)

где G-1(x3) - прообраз вершины x3.

G-1(x3) = {x2, x4}.

Подставим в (3.3) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:

l2(3) + c23 = 1 + 8 l3(4) = 8,

l4(3) + c43 = 6 + 2 = l3(4) = 8.

Таким образом, вершиной, предшествующей вершине x3, является вершина x4.

Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:

lr(2) + cr4 = l4(3), xr G-1(x4), (3.4)

где G-1(x4) - прообраз вершины x4.

G-1(x4) = {x2, x3, x5}.

Подставим в (3.4) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:

l2(2) + c24 = 1 + 7 l4(3) = 6,

l3(2) + c34 = 1 + 1 l4(3) = 6,

l5(2) + c54 = 2 + 4 = l4(3) = 6,

Таким образом, вершиной, предшествующей вершине x4, является вершина x5.

Для вершины x5 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =5:

lr(1) + cr5 = l5(2), xr G-1(x5), (3.5)

где G-1(x5) - прообраз вершины x5.

G-1(x5) = {x1, x2}.

Подставим в (3.5) последовательно r = 1 и r = 2, чтобы определить, для какого r это равенство выполняется:

l1(1) + c15 = 0 + 3 l5(2) = 2,

l2(1) + c25 = 1 + 1 = l5(2) = 2,

Таким образом, вершиной, предшествующей вершине x5, является вершина x2.

Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:

lr(0) + cr2 = l2(1), xr G-1(x2), (3.6)

где G-1(x2) - прообраз вершины x2.

G-1(x2) = {x1}.

Подставим в (3.6) r = 1, чтобы определить, выполняется ли это равенство:

l1(0) + c12 = 0 + 1 = l2(1) = 1.

Таким образом, вершиной, предшествующей вершине x2, является вершина x1.

Итак, найден минимальный путь - x1, x2, x5, x4, x3, его длина равна 8.

3.9 Алгоритм нахождения максимального пути

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

Пример 3.16.

С помощью модифицированного алгоритма 3.1 найдем максимальный путь из вершины х1 в вершину х3 в графе, изображенном на рис. 3.11.

Рис. 3.11

Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид:

C = .

Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = . Эти значения занесем в первый столбец табл. 3.2.

Шаг 3.

k = 1.

l1(1) = 0.

Равенство (3.1) для k = 1 имеет вид:

li(1) = {lj(0) + cji}.

l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 - 1; + ; + ; + ; + } = -1.

l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ; - 8; + ; - 2; + } = .

l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ; - 7; + ; + ; - 4} = .

l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 - 3; - 1; + 5; + ; + } = -3.

Полученные значения li(1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.

k = 2.

l1(2) = 0.

Равенство (3.1) для k = 2 имеет вид:

li(2) = {lj(1) + cji}.

l2(2) = min{0 - 1; -1 + ; + ; + ; -3 + } = -1.

l3(2) = min{0 + ; -1 - 8; + ; - 2; -3 + } = -9 .

l4(2) = min{0 + ; -1 - 7; + ; + ; -3 - 4} = -8 .

l5(2) = min{0 - 3; -1 - 1; + 5; + ; -3 + } = -3.

Полученные значения li(2) занесем в третий столбец табл. 3.2. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.

k = 3.

l1(3) = 0.

Равенство (3.1) для k = 3 имеет вид:

li(3) = {lj(2) + cji}.

l2(3) = min{0 - 1; - 1 + ; - 9 + ; -8 + ; - 3 + } = - 1.

l3(3) = min{0 + ; - 1 - 8; - 9 + ; -8 - 2; - 3 + } = - 10 .

l4(3) = min{0 + ; - 1 - 7; - 9 + ; -8 + ; - 3 - 4} = - 8 .

l5(3) = min{0 - 3; - 1 - 1; - 9 + 5; -8 + ; - 3 + } = - 4.

Полученные значения li(3) занесем в четвертый столбец табл. 3.2. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.

k = 4.

l1(4) = 0.

Равенство (3.1) для k = 4 имеет вид:

li(4) = {lj(3) + cji}.

l2(4) = min{0 - 1; - 1 + ; - 10 + ; - 8 + ; - 4 + } = - 1.

l3(4) = min{0 + ; - 1 - 8; - 10 + ; - 8 - 2; - 4 + } = - 10 .

l4(4) = min{0 + ; - 1 - 7; - 10 + ; - 8 + ; - 4 - 4} = - 8 .

l5(4) = min{0 - 3; - 1 - 1; - 10 + 5; - 8 + ; - 4 + } = - 5.

Полученные значения li(4) занесем в пятый столбец табл. 3.2. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.

Таблица 3.2

i(номер вершины)	li(0) li(1) li(2) li(3) li(4)
1 2 3 4 5	0 0 0 0 0 - 1 - 1 - 1 1 - 9 - 10 - 10 - 8 - 8 - 8 - 3 -3 - 4 - 5

Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом li(k) определяет длину максимального пути из первой вершины в i-ую, содержащего не более k дуг.

Таблица 3.3

i(номер вершины)	li(0) li(1) li(2) li(3) li(4)
1 2 3 4 5	0 0 0 0 0 1 1 1 1 9 10 10 8 8 8 3 3 4 5

Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути.

Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. li(3) = li(4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n - 1.

Учитывая это замечание, для последней вершины x3 предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3:

lr(2) + cr3 = l3(3), (3.7)

xr G-1(x3), где G-1(x3) - прообраз вершины x3.

G-1(x3) = {x2, x4}.

Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:

l2(2) + c23 = 1 + 8 l3(4) = 10,

l4(2) + c43 = 8 + 2 = l3(4) = 10.

Таким образом, вершиной, предшествующей вершине x3, является вершина x4.

Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:

lr(1) + cr4 = l4(2), xr G-1(x4), (3.8)

где G-1(x4) - прообраз вершины x4.

G-1(x4) = {x2, x5}.

Подставим в (3.8) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:

l2(1) + c24 = 1 + 7 = l4(3) = 8,

l5(1) + c54 = 3 + 4 l4(3) = 8,

Таким образом, вершиной, предшествующей вершине x4, является вершина x2.

Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:

lr(0) + cr2 = l2(1), xr G-1(x2), (3.9)

где G-1(x2) - прообраз вершины x2.

G-1(x2) = {x1}.

Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство:

l1(1) + c12 = 0 + 1 = l2(1) = 1.

Таким образом, вершиной, предшествующей вершине x2, является вершина x1.

Итак, найден максимальный путь - x1, x2, x4, x3, его длина равна 10.

3.10 Деревья. Основные определения

множество граф логика булева

Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:

а) дерево есть связный граф, содержащий n вершин и n - 1 ребер;

б) дерево есть граф, любые две вершины которого можно соединить простой цепью.

Пример 3.17.

Графы, изображенные на рис. 3.12, являются деревьями.

Рис. 3.12

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

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пример 3.18.

Для графа, изображенного на рис. 3.13а), графы на рис. 3.13б) и 3.13в) являются остовными деревьями.

Рис. 3.13

Пусть граф G имеет n вершин и m ребер Так как всякое дерево с n вершинами по определению (см. раздел 6.1) имеет n - 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления m - (n - 1) = m - n + 1 ребер. Число = m - n + 1 называется цикломатическим числом графа.

3.11 Минимальные остовные деревья нагруженных графов

Граф G = (X, A) называется нагруженным, если для каждого ребра (xi,xj) определена его длина (или вес) cij.

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

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

а) Нужно соединить n городов железнодорожными линиями (автомобильными дорогами, линиями электропередач, сетью трубопроводов и т.д.) так, чтобы суммарная длина линий или стоимость была бы минимальной.

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

Задачу построения минимального остовного дерева можно решить с помощью следующего алгоритма.

Алгоритм 3.2 (Алгоритм Краскала).

Шаг 1. Установка начальных значений.

Вводится матрица длин ребер C графа G.

Шаг 2. Выбрать в графе G ребро минимальной длины. Построить граф G2, состоящий из данного ребра и инцидентных ему вершин. Положить i = 2.

Шаг 3. Если i = n, где n - число ребер графа, то закончить работу (задача решена), в противном случае перейти к шагу 4.

Шаг 4. Построить граф Gi +1, добавляя к графу Gi новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно какой-нибудь вершине графа Gi и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в Gi. Вместе с этим ребром включаем в Gi +1 и инцидентную ему вершину, не содержащуюся в Gi. Присваиваем i:= i +1 и переходим к шагу 3.

Пример 3.19.

Найдем минимальное остовное дерево для графа, изображенного на рис. 3.14.

Рис. 3.14

Шаг 1. Установка начальных значений.

Введем матрицу длин ребер C:

С =.

Шаг 2. Выберем ребро минимальной длины. Минимальная длина ребра равна единице. Таких ребер три: (x1, x2), (x1, x4), (x2, x4). В этом случае можно взять любое. Возьмем (x1, x2). Построим граф G2, состоящий из данного ребра и инцидентных ему вершин x1 и x2. Положим i = 2.

Шаг 3. Так как n = 5, то i n, поэтому переходим к шагу 4.

Шаг 4. Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно одной из вершин x1, x2 и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G2 т. е. одной из вершин x3, x4, x5. Таким образом, нужно выбрать ребро минимальной длины из ребер (x1, x4), (x1, x5), (x2, x3), (x2, x4), (x2, x5). Таких ребер длины единица два: (x1, x4) и (x2, x4). Можно выбрать любое. Возьмем (x1, x4). Вместе с этим ребром включаем в G3 вершину x4, не содержащуюся в G2. Полагаем i = 3 и переходим к шагу 3.

...