Как определить вес ребра графа

Как определить вес ребра графа

Графы формально описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связывающие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Иногда наши графы ориентированы (подобно улицам с односторонним движением) или взвешены — каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные). Когда мы изучим язык графов подробнее, аналогия с картой автодорог станет еще более глубокой.
После освоения математических аспектов графов мы займемся вопросами их представления в памяти компьютера и алгоритмами их обработки. Мы увидим, что имеется много способов хранения графов, отличающихся по величине накладных расходов; выбор способа может зависеть от самого графа.
Иногда приходится распространять ту или иную информацию среди большой группы людей или по всем компьютерам большой сети. Мы хотели бы, чтобы информация достигла каждого участника группы, но при этом ровно по одному разу. В некоторых группах для этой цели организуется «телефонное дерево», когда каждый из членов группы, получив свежую новость, сообщает ее небольшому числу других участников. Если каждый из членов группы встречается в дереве лишь однажды, а высота дерева не очень велика, то информация очень быстро доходит до всех. Для графов общего вида ситуация оказывается сложнее: в среднем графе гораздо больше связей, чем в дереве. Мы изучим два метода обхода графов: в глубину и по уровням, позволяющих преодолеть эту трудность. Остовное дерево представляет собой связное подмножество графа, не содержащее циклов, включающее в себя все вершины графа и некоторые из его ребер. Минимальное остовное дерево это остовное дерево, имеющее минимально возможную сумму весов ребер. Одно из применений минимальных остовных деревьев — организация внутренней компьютерной сети. Передающие станции устанавливаются в стратегически важных местах некоторой области. Если мы хотим уменьшить суммарную стоимость объединения станций в сеть, то можно нарисовать граф, в котором станции будут служить вершинами, а ребрам, их соединяющим, можно приписать стоимость соединения. Минимальное остовное дерево этого графа указывает, какие станции следует соединить между собой, чтобы любые две станции оказались соединенными, причем общая стоимость соединения была минимально возможной.
Аналогичные приложения имеет и задача поиска кратчайшего пути в графе: умение решать такую задачу помогает планировать путь на автомобиле или посылать сообщение по компьютерной сети.
Важной характеристикой большой компьютерной сети служит ее надежность. Мы хотели бы, чтобы сеть сохраняла работоспособность при выходе из строя одного узла. Говоря проще, станции в сети должны быть соединены несколькими путями, чтобы при разрушении какого-либо из путей возможность передачи информации сохранялась. В последнем параграфе этой главы мы обсуждаем алгоритм поиска компонент двусвязности. Он ищет вершины, неизбежно находящиеся на всяком пути из одной части графа в другую. В компьютерной сети разрушение таких узлов приводит к нарушению связности сети.

С формальной точки зрения граф представляет собой упорядоченную пару G = (V, Е) множеств, первое из которых состоит из вершин, или узлов, графа, а второе — из его ребер. Ребро связывает между собой две вершины. При работе с графами нас часто интересует, как проложить путь из ребер от одной вершины графа к другой. Поэтому мы будем говорить о движении по ребру; это означает, что мы переходим из вершины А графа в другую вершину В, связанную с ней ребром АВ (ребро графа, связывающее две вершины, для краткости обозначается этой парой вершин). В этом случае мы говорим, что А примыкает к В, или что эти две вершины соседние.
Граф может быть ориентированным или нет. Ребра неориентированного графа, чаще всего называемого просто графом, можно проходить в обоих направлениях. В этом случае ребро — это неупорядоченная пара вершин, его концов. В ориентированном графе, или орграфе, ребра представляют собой упорядоченные пары вершин: первая вершина — это начало ребра, а вторая — его конец. Далее мы для краткости будем говорить просто о ребрах, а ориентированы они или нет будет понятно из контекста.
Позже мы будем просто рисовать графы, а не задавать их множествами. Вершины будут изображаться кружочками, а ребра — отрезками линий. Внутри кружочков будут записаны метки вершин. Ребра ориентированного графа будут снабжены стрелками, указывающими допустимое направление движения по ребру.
На рисунке 1 изображено графическое представление неориентированного (а) и ориентированного (б) графов вместе с их формальным описанием.

Терминология
Полный граф — это граф, в котором каждая вершина соединена со всеми остальными. Числ ребер в полном графе без петель с N вершинами равно (N 2 — N)/2. В полном ориентирвоанном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направлениях, а переход по ребру в орграфе — только в одном, в полном орграфе в два раза больше ребер, то есть их число равно N 2 — N.
Подграф (V_S, E_S) графа или орграфа (V, E) состоит из некоторого подмножества вершин и некоторого подмножества ребер, их соединяющих.
Путь в графе или орграфе — это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины A в вершину B начинается в A и проходит по набору ребер до тех пор, пока не будет достигнута вершина B. С формальной точки зрения, путь из вершины v_i в вершину v_j это последовательность ребер графа v_iv_i+1, v_i+1v_i+2, . v_j-1v_j. Мы требуем, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина — число ребер в нем. Длина пути AB, BC, CD, DE равна 4.
Во взвешенном графе или орграфе каждому ребру приписано число, называемое весом ребра. При изображении графа обычно записывают вес ребра рядом с ребром. При формальном описании вес будет дополнительным элементом неупорядоченной или упорядоченной пары вершин (образуя вместе с этой парой «триплет»). При работе с ориентированными графами мы считаем вес ребра ценой прохода по нему. Стоимость пути по взвешенному графу равна сумме весов ребер пути. Кратчайший путь во взвешенном графе — это путь с минимальным весом, даже если число ребер в пути и можно уменьшить. Если, например, путь P₁ состоит из пяти ребер с общим весом 24, а путь P₂ — из трех ребер с общим весом 36, то путь P₁ считается более коротким.
Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл — это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется (неукорененным) деревом. Структура неукорененного дерева такая же, что и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем.

Как определить вес ребра графа

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

Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром . Если упорядочена – дугой . Граф, состоящий только из ребер называется неориентированным графом . Граф, содержащий только дуги, — ориентированным графом или орграфом .

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

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

Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами . Если вершины соединены дугой (x, y), то вершина x смежна вершине y, а обратной смежности нет.

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

Ребро и любая из двух его вершин называются инцидентными .

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

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

2.2. Способы представления графа в памяти

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

При дальнейшем изложении будем предполагать, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине сопоставлен вес – целое положительное число.

Для каждого способа хранения будем определять пространственную сложность и временную сложность следующих операций:

Графы и деревья

Орграф — это граф , все ребра которого имеют направление. Такие направленные ребра называются дугами . На рисунках дуги изображаются стрелочками (см. рис. 11.6).

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

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

Все основные понятия, определенные для неориентированных графов ( инцидентность , смежность , достижимость , длина пути и т.п.), остаются в силе и для орграфов — нужно лишь заменить слово » ребро » словом » дуга «. А немногие исключения связаны с различиями между ребрами и дугами .

Степень вершины в орграфе — это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг , а второе — количество входящих дуг .

Путь в орграфе — это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги . Например, в орграфе на рис. 11.6 нет пути , ведущего из вершины 2 в вершину 5 . «Двигаться» по орграфу можно только в направлениях, заданных стрелками.

Таблица 11.2. Примеры ориентированных графов

Орграф	Вершины	Дуги
Чайнворд	Слова	Совпадение последней и первой букв (возможность связать два слова в цепочку)
Стройка	Работы	Необходимое предшествование (например, стены нужно построить раньше, чем крышу, т. п.)
Обучение	Курсы	Необходимое предшествование (например, курс по языку Pascal полезно изучить прежде, чем курс по Delphi , и т.п.)
Одевание ребенка	Предметы гардероба	Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.)
Европейский город	Перекрестки	Узкие улицы с односторонним движением
Организация	Сотрудники	Иерархия (начальник — подчиненный)

Взвешенные графы

Взвешенный (другое название: размеченный ) граф (или орграф ) — это граф ( орграф ), некоторым элементам которого ( вершинам , ребрам или дугам ) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами . Числа-пометки носят различные названия: вес, длина , стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1 .

Длина пути во взвешенном (связном) графе — это сумма длин (весов) тех ребер, из которых состоит путь . Расстояние между вершинами — это, как и прежде, длина кратчайшего пути . Например, расстояние от вершины a до вершины d во взвешенном графе , изображенном на рис. 11.7, равно 6 .

N — периферия вершины v — это множество вершин , расстояние до каждой из которых (от вершины v ) не меньше, чем N .

Таблица 11.3. Примеры взвешенных графов

Граф	Вершины	Вес вершины	Ребра (дуги)	Вес ребра (дуги)
Таможни	Государства	Площадь территории	Наличие наземной границы	Стоимость получения визы
Переезды	Города	Стоимость ночевки в гостинице	Дороги	Длина дороги
Супер-чайнворд	Слова	—	Совпадение конца и начала слов(возможность «сцепить» слова)	Длина пересекающихся частей
Карта	Государства	Цвет на карте	Наличие общей границы	—
Сеть	Компьютеры	—	Сетевой кабель	Стоимость кабеля

Способы представления графов

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

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

Матрица смежности Sm — это квадратная матрица размером NxN ( N — количество вершин в графе ), заполненная единицами и нулями по следующему правилу:

Если в графе имеется ребро e , соединяющее вершины u и v , то Sm [u,v] = 1 , в противном случае Sm [u,v] = 0 .

Заметим, что данное определение подходит как ориентированным, так и неориентированным графам : матрица смежности для неориентированного графа будет симметричной относительно своей главной диагонали, а для орграфа — несимметричной.

Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:

Если в графе имеется ребро e , соединяющее вершины u и v , то Sm [u,v] = ves(e) , в противном случае Sm [u,v] = 0 .

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

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

В качестве примера приведем матрицы смежности для трех графов , изображенных на рис. 11.5, рис. 11.6 и рис. 11.7 (см. рис. 11.8).

Таблица 11.8. Примеры матриц смежности

a	b	c	d	f	1	2	3	4	5	a	b	c	d
a	0	1	1	0	0	1	0	1	0	1	0	a	0	1	10	0
b	1	0	1	1	1	2	0	0	0	0	0	b	1	0	2	10
c	1	1	0	1	1	3	1	1	0	0	1	c	10	2	0	3
d	0	1	1	0	1	4	0	0	1	0	0	d	0	10	3	0
f	0	1	1	1	0	5	0	0	0	0	0

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство — в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности , оказывается много «пустых мест» (нулей). Кроме того, для «общения» с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.