IPB

> Лекция №11.2: Графы и деревья
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4

Содержание

Ориентированные графы

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

Орграф

Рис. 11.6.  Орграф

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 11.7.  Взвешенный граф

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. Примеры матриц смежности

abcdf12345abcd
a01100101010a01100
b10111200000b10210
c11011311001c10203
d01101400100d01030
f01110500000

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

страницы: 1 2 3 4

Примечания

 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"