Правила форума
Лекция №11.2: Графы и деревьяСодержание
Ориентированные графы
Орграф — это граф, все рёбра которого имеют направление. Такие направленные рёбра называются дугами. На рисунках дуги изображаются стрелочками (см. рис. 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. Примеры матриц смежности
| 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 |
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на её использовании. А неудобство — в несколько завышенном требовании к памяти: если граф далёк от полного, то в массиве, хранящем матрицу смежности, оказывается много «пустых мест» (нулей). Кроме того, для «общения» с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.
::
::
::
