Программирование на языке Pascal



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


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

Орграф

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

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

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

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

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

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

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

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




Содержание  Назад  Вперед