Cтраница 4
Теоремы о паросочетаниях для локально конечных графов зависят, как мы видели в предыдущей главе, от понятия дефицита множества, и это понятие также легко переносится на ориентированные графы. [46]
Ориентированные графы или, для краткости, орграфы используются для моделирования ситуаций, в которых есть отношение частичного порядка между объектами. Возникающие при этом схемы служат для изображения схем информационных потоков, сетевого планирования и планирования заданий. В этой главе мы введем стандартную терминологию из теории орграфов и обсудим систему ПЕРТ. [47]
По определениям, принятым в этих монографиях, ориентированные графы могут содержать и петли, и параллельные ребра. Рассматриваемые далее ориентированные графы могут содержать параллельные ребра, но петель не содержат. [48]
Граф-схемы Калужнина представляют собой ориентированные графы специального вида. В каждом графе выделяются два узла - входной и выходной. А все остальные узлы делятся на два класса: узлы-распознаватели и узлы-преобразователи. Из входного узла, а также из узлов-преобразователей исходит в точности одна стрелка. Из выходного узла стрелки не исходят. Наконец, узлам-преобразователям поставлены в соответствие символы операторов, а узлам-распознавателям - символы предикатов. [49]