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

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

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

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

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

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

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

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

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

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

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

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

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

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

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