Если за область значений принять множество четных чисел М = {2, 4, 6,…}, то это отображение будет уже N на M, т. к. .

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

f: N → N – это частично определенная функция, но не отображение, т. к. D(f) N.

f: N → R – это отображение N в R, т. к. E(f) R.

f: R+ → R – это отображение R+ в R, т. к. E(f) R.

f: R+ → R+ – это отображение R+ на R+ , т. к. E(f) = R или преобразование множества R.

1.5. Обратная функция

Обратное соответствие: Дано соответствие . Если соответствие таково, что тогда и только тогда, когда , то соответствие Н называется обратным к G и обозначается G-1 .

Обратное соответствие – есть обратное бинарное отношение, т. к.

Рассмотрим вопрос о том, в каком случае обратное соответствие будет являться обратной функцией.

В обратном соответствии образы и прообразы меняются местами. Тогда, если дана функция f: A→ B, то для нее существует обратная функция f-1 тогда и только тогда, когда f является взаимно однозначным соответствием.

Если функция f является всюду определенной, т. е. является отображением, то для нее существует обратное отображение тогда и только тогда, когда область определения есть множество А, т. е. D(f) = A, и область значений есть множество B, т. е. E(f) = B.

Примеры:

а). y = sinx, где , Это отображение R в R. Данная функция отображает отрезок на отрезок [-1; 1]. Значит, существует обратная функция f-1: y = arcsinx, которая отображает отрезок [-1; 1] на отрезок .

НЕ нашли? Не то? Что вы ищете?

б). у = 2х – эта функция задает отображение R на R+. Обратная функция f-1: y = log2x задает отображение R+ в R.

в). у = х2 – 4 , где D(f) = R - эта функция не является взаимнооднозначным соответствием, поэтому для нее не существует обратная функция, но существует обратное отображение f-1: .

2. Свойства отображений и функций

Пусть задана функция или отображение f: A → B.

Свойство 1. Если , то f – называется инъективной функцией (отображением).

Т. е. каждому соответствует единственный

Свойство 2. Если для любого найдется такой, что b = f(a) , то f сюръективная функция (отображение).

Т. е. область значений E(f) = B.

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

На основании третьего свойства можно сделать вывод:

Биективная функция f: A → B осуществляет взаимнооднозначное соответствие между А и В.

Примеры:

а). Функция f(x) = ex задает отображение R в R : D(f) = R, E(f) = R+ .

Она инъективна (каждому х единственное у), но не сюръективна, т. к.

б). f(x) = x3 - x задает отображение R на R : D(f) = R, E(f) = R. Она не инъективна, т. к. при х = 1 и х = -1 f(x) = 0.

в). f(x) = 2x + 1 задает отображение R на R : D(f) = R, E(f) = R. Она инъективна и сюръективна, значит, биективна.

3.Операции над функциями. Свойства операций

3.1. Композиция функций

Вспомним аналогичную операцию над бинарными отношениями :

, то .

Пусть даны функции f; X→ Y и g: Y → Z, то называется композицией функций f и g.

3.2. Свойства композиции функций

Свойство 1. Композиция функций является функцией.

Доказательство: Необходимо доказать, что если и , то y = z.

Рассмотрим f и g как бинарные отношения.

Пусть и , тогда

- для (х, у) найдется u такое, что х находится в отношении f с u, u находится в отношении g с у,

- для (х, z) найдется v такое, что х находится в отношении f с v, v находится в отношении g с z.

Т. к. f – функция, то u = v; g – функция, то y = z. Следовательно, h – функция.

Примеры:

а). y = sin2x, где f = sinx, g = f2.

б). , где f = x + 2,

Таким образом, композицию функций можно рассматривать:

- как последовательное применение функций f и g;

- g применяется к результату f;

- h получена подстановкой f в g.

Свойство 2. Композиция двух биективных функий есть биективная функция.

Доказательство: , тогда

Найдется v такое, что . А т. к. f и g биективны, то

любому х соответствует единственное v, любому v соответствует единственное у. Отсюда следует, что любому х соответствует единственное у.

В свою очередь, любому у соответствует единственное v, а любому v – единственное х. Отсюда следует, что любому у соответствует единственное х.

Из всего выше сказанного следует, что биективна.

Примеры:

а). y = (х + 3)11, где f = х + 3 - биективна, g = f11 – биективна, следовательно, y = (х + 3)11- биективна.

б). y = (х + 3)10, где f = х + 3 - биективна, но g = f – не биективна, следовательно, y = (х + 3)10- не биективна.

3.3. Обратная функция и обратное отображение

Cоответствие Н является обратным для G (H = G-1), если G : A→B, H: B → A:

Если G – отображение, то Н – так же отображение.

Теорема о существовании обратного отображения: Отображение f: Х → У имеет обратное отображение f-1: У → Х, тогда и только тогда, когда f – биекция.

Доказательство: Если f – биекция, то f – сюръективно, т. е. E(f) = Y, следовательно, f-1 опредеделено на множестве У = D(f--1). f – функция и и , то имеем и . Кроме того, f – инъективна, следовательно х1 = х2.

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

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

Что называется соответствием между двумя множествами? Какое соответствие называется всюду определенным? Какое соответствие называется частично определенным? В каком случае соответствие называется функциональным? Каким условиям должно отвечать взаимнооднозначное соответствие? Что называется функцией? Какая функция называется отображением? В каком случае отображение называется отображением А в В, и в каком случае - А на В? В каком случае для функции существует обратная? Какая функция называется инъективной? Какая функция называется сюръективной? Какая функция называется биективной? Что такое композиция двух функций. Какими свойствами обладает композиция двух функций? Сформулировать теорему о существовании обратного отображения. Составить всевозможные композиции из функций f(x) = lgx и g(x) = sinx. Проверить композиции на биективность. Составить для функций обратные соответствия и проверить являются ли они функциями: а).

; б).

ЛЕКЦИЯ 17

ТЕМА: НЕОРИЕНТИРОВАННЫЙ ГРАФ.

ПЛАН:

1. Основные понятия

2. Смежность, инцидентность. Степени вершин

3. Способы задания графов

4. Маршруты в неориентированном графе

5. Операции над графами

6. Связность. Компоненты связности

Главная

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

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

1. Основные понятия.

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

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

При рассмотрении задач теории графов ограничиваются исследованием совокупности двух конечных множеств V и Х. Элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

Сформулируем определение неориентированного графа:

Непустое множество V = {v1, v2,…,vn} и набор Х пар объектов {vi, vi+1}, где viÎV, vi+1ÎV, называется графом.

Т. к. V и Х конечные множества, то граф называется конечным.

Если пара упорядоченная (vi, vi+1), граф называется ориентированным и обозначается D(V, X).

Если пара неупорядоченная {vi, vi+1}, то граф называется неориентированным и обозначается G(V, X).

Рассмотрим сначала неориентированные графы.

Как было сказано выше граф изображается диаграммой на плоскости. Приведем пример:

Рис. 13.1

В данном графе есть пара с одинаковыми вершинами {v3, v3}. Ребро соответствующее такой паре называется петлей.

Граф также содержит одинаковые пары {v6, v5}. Такие пары называются кратными ребрами. Количество одинаковых пар, соответствующих вершинам vi и vi+1 называется кратностью ребра. В приведенном примере кратность ребра {v6, v5} равна двум.

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

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

Мультиграф без кратных ребер называется простым графом (13.3).

Рис. 13.2. Мультиграф. Рис. 13.3. Граф.

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

Рис. 13.4. Полный граф.

2. Смежность, инцидентность, степени вершин.

Если х = {v, w} – ребро графа, то v, w называются концами ребра х, в этом случае говорят, что ребро х соединяет вершины v и w.

Если вершина v является концом ребра х, то говорят, что v и х инцидентны.

Вершины v, w графа G(V, X) называются смежными, если {v, w}ÎХ.

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

Рассмотрим граф на рисунке 13.1.

Вершине v3 инцидентны ребра {v3, v3}, {v3, v1}, {v3, v2}, {v3, v4}.

Ребру {v2, v6} инцидентны вершины v2, v6.

Вершины v5, v6 – смежные, т. к. {v5, v6}- ребро. Вершины v5, v3 – не смежные, т. к. нет ребра их соединяющего.

Ребра {v3, v1}, {v3, v2}- смежные, т. к. имеют общую вершину v3.

Степень вершины v – это количество ребер графа, инцидентных этой вершине. Обозначение d (v).

Для графа 13.1:

d (v1) = 1 d (v5) = 2

d (v2) = 2 d (v6) = 3

d (v3) = 5 d (v7) = 0

d (v4) = 1

Заметим, что вклад каждой петли равен двум.

Если степень вершины равна единице, то такая вершина называется висячей.

Если степень вершины равна нулю, то такая вершина называется изолированной.

Значит, вершины v1 и v4 – висячие, а вершина v7 – изолированная.

Теорема о сумме степеней вершин графа: Для любого псевдографа G(V, X) выполняется равенство:

m – количество ребер графа. Действительно, каждое ребро графа инцидентно двум вершинам.

Проверим справедливость теоремы для графа 13.1:

m =7, 7× 2 =14 и 1+2+5+1+2+3+0 =14.

3. Способы задания графов

Один из способов задания графа уже рассмотрен – это геометрическое изображение, т. е. диаграмма.

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

Матрица инцидентности графа.

Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.

Матрицей инцидентности графа G(V, X) называется матрица размера m´ n, элементы которой определяются следующим образом:

В любой строке матрицы инцидентности два или один элемент не равны нулю, т. к. каждое ребро соединяет две вершины, а если ребро – петля, то вершину саму с собой.

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

Составим матрицу инцидентности для графа 13.1. Это матрица размера 7´ 7:

В первом и четвертом столбцах по одной единице, следовательно первая и четвертая вершины – висячие; в седьмом столбце все элементы равны нулю, значит седьмая вершина изолированная.

В третьей строке только один элемент не равен нулю, следовательно третье ребро - петля.

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

Матрица смежности

Пусть задан граф G(V, X), где V ={v1, v2, …, vn}, X = {x1, x2,…, xm}.

Матрицей смежности графа G(V, X) называется квадратная матрица n´ n, элементы которой определяются следующим образом:

k – количество ребер, соединяющих вершины vi и vj.

Составим матрицу смежности для графа 13.1. Это квадратная матрица размера 7´ 7:

Матрица смежности неориентированного графа симметрична относительно главной диагонали.

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

Сумма элементов верхнего или нижнего треугольника вместе с главной диагональю равна количеству ребер в графе. Для нашего графа сумма равна (учитывая только элементы не равные нулю): 1+1+1+2+1+1=7.

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

4. Маршруты в неориентированном графе

Определение: Маршрутом, соединяющий вершины v1 и vk+1 , называется последовательность v1x1v2x2…vkxkvk+1 , где k³ 1, vi Î V, xiÎ X, ребро xi соединяет вершины vi с вершиной viВершина v1 (v нач)– начало маршрута (начальная вершина), vk+1 (v кон)– конец маршрута (конечная вершина).

Для графа 13.1 построим маршрут, соединяющий вершину v1 с вершиной v5 :

v1x1v3x3v3v2x5v6x7v5 .

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

Если в маршруте есть кратные ребра, то в последовательность включают начальную вершину, ребра и конечную вершину. Или пользуются комбинированной записью: в последовательность включают все вершины и только кратные ребра.

Перепишем наш маршрут, использую комбинированную запись: v1v3v3v2v6x7v5 . В последовательность включено только кратное ребро x7 .

Длиной маршрута l называется количество ребер в нем.

В нашем маршруте 5 ребер, значит его длина l =5.

Познакомимся с видами маршрутов.

Если vнач = vкон, то маршрут называется замкнутым.

Если vнач ¹ vкон, то маршрут называется незамкнутым.

Виды незамкнутых маршрутов:

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

Цепь, в которой все вершины попарно различны называется простой цепью.

Виды замкнутых маршрутов:

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

Цикл, в котором все вершины попарно различны называется простым циклом.

Заметим, что петля или кратное ребро являются простыми циклами.

Составим различные маршруты для приведенного ниже графа на рисунке 13.5.

Рис. 13.5.

Маршрут v1v2v3v4 – простая цепь.

Маршрут v2v4v5v6v6v4 – цепь, не являющаяся простой.

Маршрут v3v4v5v6v5 – замкнутый маршрут.

Маршрут v3v2v4v5v6v4v2v3 – цикл, не являющийся простым.

Маршрут v3v2v4v3 – простой цикл.

5. Операции над графами.

Так как граф G(V, X) задается двумя множествами V и X, то для него определены теоретико-множественные операции : объединение и пересечение.

Объединением графов G1(V1, X1), G2(V2, X2) называется граф G(V, X), где V = V1 ÈV2 , X = X1 ÈX2 .

Пересечением графов G1(V1, X1), G2(V2, X2) называется граф G(V, X), где V = V1 ÇV2 , X = X1 ÇX2 .

Кроме этих операций познакомимся с понятиями : подграф и сурграф.

Подграфом графа G(V, X) называется граф G’(V’, X’) , где G’Í G, X’Í X.

Подграф G’(V’, X’) графа G(V, X) называется собственным, если G’Ì G, X’Ì X.

Подграфом графа G(V, X) , порожденным множеством V1 Í V, где V1 ¹Æ, называется граф G1(V1, X1), где Х1 Í Х и соединяет вершины только из V1 .

Сурграфом графа G(V, X) называется граф G”(V, X”), где V=V, X” Ì X.

Рис.13.6.

Рис. 13.7.

Рис.13.8.

На рисунке 13.6 представлен собственный подграф графа 13.5.

На рисунке 13.7 – подграф графа 13.5, порожденный множеством V1 ={v1, v2, v4, v6}.

На рисунке 13.8 – сурграф графа 13.5.

6. Связность. Компоненты связности

Пусть дан псевдограф G(V, X).

Две вершины v и w называются связанными (или вершина v достижима из w), если :

а) v = w;

б) существует маршрут, связывающий вершины v и w.

Определенное на множестве V отношение достижимости или связности является бинарным эквивалентным отношением (проверьте самостоятельно). А значит, множество V можно разбить на классы эквивалентности V1 V2 …Vk, где V1 ÈV2È …ÈVk=V и V1 ÇV2 Ç…ÇVk = Æ.

Все вершины, принадлежащие одному подмножеству Vi связанные, а вершины, принадлежащие разным подмножествам – несвязанные.

Каждое подмножество Vi называется компонентой связности графа G(V, X).

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

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

Количество компонент связности графа G(V, X) обозначается P(G).

На рисунке 13.9 представлен граф, у которого три компоненты связности, т. е. P(G) =3: G1, G2, G3

G1 G2 G3

Рис. 13.9.

Введем понятие связного графа.

Граф G(V, X) называется связным, если любые две его вершины достижимы (связанные).

Или: граф G(V, X) называется связным, если P(G) = 1.

Тогда, несвязный граф имеет P(G) >1.

С понятием компонента связности связаны понятия: разделительная вершина (точка сочленения) и мост.

Введем еще одну операцию над графом – удаление вершины.

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

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

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

Для графа 13.5 найдем все разделительные вершины и мосты:

разделительные вершины: v2, v4,

мост : {v1, v2}.

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

1. Сформулировать определение графа.

2. Перечислить виды графов.

3. Перечислить способы задания неорграфа.

4. Пояснить понятия: инцидентность и смежность.

5. Что называется компонентой связности неорграфа?

6. Что такое степень вершины? Сформулировать теорему о сумме степеней вершин.

7. Сформулировать определение маршрута в графе.

8. Какой маршрут в неорграфе называется минимальным?

9. Перечислить виды маршрутов.

ЛЕКЦИЯ 18

ТЕМА: ЗАДАЧИ НА НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

ПЛАН:

1. Поиск маршрута с минимальным числом ребер

2. Метрические характеристики неориентированного графа

3. Минимальные маршруты в нагруженных графах

4. Задачи на деревьях

5. Цикловой ранг графа. Цикломатическое число

Главная

1. Поиск маршрута с минимальным числом ребер

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

Маршрут в графе G(V,X) из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет минимальную длину среди всех маршрутов из v в w.

Напомним, что длина маршрута – это число ребер в нем.

Свойство минимального маршрута: Любой минимальный маршрут является простой цепью.

Рассмотрим задачу поиска минимального маршрута. Введем некоторые обозначения: пусть G(V, X) – граф, v Î V, V1 Í V; обозначим G(v) = {wÎV|{v, w}Î X} – образ вершины v; G(V1) = - образ множества вершин V1 ; G-1(v) = { wÎV|{w, v}Î X} – прообраз вершины v; G-1(V1) = - прообраз множества вершин V1 .

Пусть G(V, X) – граф с n ³ 2 вершинами и v и w – заданные вершины из данного графа. Причем v ¹ w. Опишем алгоритм поиска минимального маршрута в графе G (алгоритм фронта волны).

Шаг1. Помечаем вершину v индексом 0. затем помечаем вершины, принадлежащие образу вершины v, индексом 1. множество вершин с индексом 1 обозначим FW1(v). Полагаем к =1.

Шаг 2. Если FWk(v) = Æ или выполняется к = n –1, wÏ FWk(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.

Шаг 3. Если wÏ FWk(v), то переходим к шагу 4. в пртивном случае существует маршрут из v в w длины к, и этот путь является минимальным. Последовательность вершин vw1w2…wk -1 w, где

wk-1 Î FWk-1ÇG-1(w);

wk-2 Î FWk-2ÇG-1(wk-1);

……………………….

w1 Î FW1ÇG-1(w2);

и есть искомый минимальный путь из v в w.

Шаг 4. Помечаем индексом к+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом к. множество вершин с индексом к+1 обозначим FWk+1(v). Присваиваем к: = к+1 и переходим к шагу 2.

Множество FWk(v) называют фронтом волны к - го уровня.

Замечание: Вершины w1, w2,…w k-1 могут быть выделены неоднозначно, в случае, если существует несколько минимальных маршрутов из v в w.

Примеры.

1. Используя описанный алгоритм найти минимальный маршрут из v1 в v10 в графе, заданном диаграммой:

Вершине v1 присваиваем индекс 0 и последовательно определяем

FW1(v1) = {v2, v4, v6, v8};

FW2(v1) = {v3, v5, v7, v9};

FW3(v1) = {v10}.

Значит, существует маршрут из v1 в v10 длиной l =3 , и он является минимальным.

Найдем последовательность вершин в этом маршруте:

FW2(v1)ÇG-1(v10)= {v3, v5, v7, v9}Ç {v3, v5, v7, v9}= {v3, v5, v7, v9}, выберем любую из вершин полученного множества, например, v7;

FW1(v1)ÇG-1(v7) = {v2, v4, v6, v8}Ç {v4, v8, v6}= {v4, v8, v6}, выберем любую вершину из этого множества – v6 .

Получили минимальный маршрут: v1 v6 v7 v10. Данная задача имеет несколько решений.

2. Построить минимальный маршрут из v1 в v6 в графе, заданном матрицей смежности:

Вершине v1 присваиваем индекс 0 и последовательно определяем множества, просматривая строки:

FW1(v1) = {v2};

FW2(v1) = {v3};

FW3(v1) = {v4, v5, v6}.

Маршрут существует и равен l = 3. Найдем последовательность вершин в этом маршруте, просматривая столбцы:

FW2(v1)ÇG-1(v6)= {v3}Ç {v3, v5}= {v3}, включаем в маршрут единственно возможную вершину v3;

FW1(v1)ÇG-1(v3) = {v2}Ç {v2, v4, v5, v6}= {v2}, включаем в маршрут единственно возможную вершину v2;

Получили минимальный маршрут v1 v2 v3 v6. Задача имеет единственное решение.

2. Метрические характеристики неориентированного графа

Пусть G(V, X) – псевдограф и пусть вершины v и w (v¹w) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vÎV; d(v, w) = ¥, если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v, w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний Cn2 .

Пусть граф G(V, X) связный. Определим для него следующие понятия:

Диаметр графа: d(G) = maxd(v, w).

v, wÎV

Эксцентриситет (максимальное удаление) вершины: r(v) = maxd(v, w);

vÎV

Радиус графа : r(G) = min r(v);

vÎV

Центр графа: любая вершина vÎV, такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин, радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С52 = 5!/3!2! = 10: d(v1, v2) =1, d(v1, v3) = 2, d(v1, v4) = 2, d(v1, v5) = 3, d(v2, v3) = 1, d(v2, v4) = 1, d(v2, v5) = 2, d(v3, v4) = 1, d(v3, v5) = 2, d(v4, v5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3.

Радиус графа r(G) = 2.

Центры графа v2, v3, v4 .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х ÎХ графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т. д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х Î Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (v¹w), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V, X) нагруженный, число вершин n ³ 2, необходимо построить минимальный маршрут из v1 в vn.

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс a(vi): a(v1) = 0, a(vi) = ¥, i ¹ 1. окрасить вершину v1 и положить v = v1.

Шаг 2. Для каждой неокрашенной вершины vj изменить индекс по правилу:

a(vj) = min {a(vj), a(v) + l(v, vj)}.

Окрасить ту из вершин, для которой a(vj) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину vj. Положить v = vj.

Шаг 3. Если v = vj, закончить процедуру, так как кратчайший маршрут из v1 в vn . если v ¹ vn , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все a(vj)= ¥. В этом случае вершина vn недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v1 в v6.

Шаг 1. Окрасим вершину v1 . Присвоим вершинам индексы: a(v1) =0, a(v2) = a(v3)=…= a(vn)=¥. Полагаем v1 = v.

Шаг 2.

a(v2) = min {¥, 0+4} = 4,

a(v3) = min {¥, 0+7} = 7,

a(v4) = min {¥, 0+3} = 3,

a(v5) = min {¥, 0+¥} = ¥,

a(v6) = min {¥, 0+¥} = ¥.

Окрашиваем вершину v4 и ребро {v1, v4}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v4.

Шаг 2.

a(v2) = min {4, 3+¥} = 4,

a(v3) = min {7, 3+¥} = 7,

a(v5) = min {¥, 3+3} = 6,

a(v6) = min {¥, 3+¥} = ¥.

Окрашиваем вершину v2 и ребро {v1, v2}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v2.

Шаг 2.

a(v3) = min {7, 4+3} = 7,

a(v5) = min {6, 4+2} = 6,

a(v6) = min {¥, 4+¥} = ¥.

Окрашиваем вершину v5 и ребро {v4, v5}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v5.

Шаг 2.

a(v3) = min {7, 6+¥} = 7,

a(v6) = min {¥, 6+2} = 8.

Окрашиваем вершину v3 и ребро {v1, v3}.

Шаг 3. Так как вершина v6 не окрашена, выполняем шаг 2, полагая v = v3.

Шаг 2.

a(v6) = min {8, 7+2} = 8.

Окрашиваем вершину v6 и ребро {v5, v6}.

Так как вершина v6 окрашена, то работу прекращаем. Получили минимальный маршрут v1 v4 v5 v6 , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v1 и v6 минимальный маршрут, т. к. в алгоритме имелась возможность окрасить вместо ребра {v4, v5} ребро {v2, v5}, тогда бы получили другой маршрут той же длины.

4. Задачи на деревьях

Ациклическим называется граф, в котором отсутствуют циклы.

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

Дерево – это связный ациклический граф.