Математическое моделирование на графах. Часть 1. Берцун В.Н. - 23 стр.

UptoLike

Составители:

Рубрика:

Глава 1. Основные понятия теории графов 23

полнить только один вид работы. Требуется оптимально распреде-

лить имеющиеся работы среди рабочих, чтобы выполнить ниболь-

шее число работ. Очевидно, что эта задача сводится к нахождению

максимального паросочетания в двудольном графе.

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

Для решения различных практических задач часто возникает не-

обходимость рассмотрения ориентированных графов (орграфов).

Например, орграф возникает при изображении графа улиц и пере-

крестков города с односторонним движением (рис. 1.25).

Рис. 1.25

Схемы программ для ЭВМ или, например, сетевые графики также

являются ориентированными графами [2, 9]. На рис. 1.26 орграфом

представлены результаты кругового турнира по футболу без ничьих

в один круг, где А, В, С, D, Е – команды. Как следует из рисунка, ко-

манда В выиграла все встречи, С проиграла все встречи, команда А

выиграла встречи с С, D, Е. Граф такого вида называется турниром.

СD

Рис. 1.26