Определение
Предика́т (n-местный,
или n-арный) —
это функция с
множеством значений 
(или
«ложь» и «истина»), определённая на
множестве 
.
Таким образом, каждый набор элементов
множества M характеризуется
либо как «истинный», либо как «ложный».
Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1. В частности, одноместный предикат определяет отношение принадлежности некоторому множеству.
Предикат — один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам.
Предикат называют тождественно-истинным и пишут:
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно-ложным и пишут:
если на любом наборе аргументов он принимает значение 0.
Графы.
Основные определения и основные способы
задания графов О: Графом называется
упорядоченная пара конечных множеств
где
—
множество точек, называемых вершинами
графа,
—
множество пар элементов из V, называемых
ребрами графа. Ребро
соединяет
вершины
и
или
инцидентно этим вершинам. Вершины
называются
смежными или инцидентными ребру
Два
ребра называются смежными, если они
инцидентны одной вершине. Граф с п
вершинами и
ребрами
называется
графом.
Граф G называется ориентированным
(орграфом), если Е— множество упорядоченных
пар из V, т.е. его ребра являются
направленными, такие направленные ребра
называют дугами.
Каждому
графу можно поставить в соответствие
некоторую схему на плоскости, если
вершины изображать точками, а ребра —
линиями. Эта схема называется диаграммой
графа или просто графом. Ребра на
диаграмме могут быть отрезками прямых
или дугами линий. Один и тот же граф
можно изобразить разными диаграммами.
Например, на рис. 38.1, 38.2 изображен один
и тот же неориентированный граф
где
О: Граф, имеющий кратные ребра, называется мультиграфом, не имеющий кратных ребер — простым графом.
О: Степенью вершины а графа G называется число ребер, инцидентных а.
Например, для графа на рис. 38.3 степень вершины а равна 2, вершины Ъ —5. Задать граф можно также с помощью некоторой матрицы.
О:
Матрицей смежности графа
на-
зывается
квадратная матрица
го
порядка, столбцам
и
строкам которой соответствуют вершины
графа. Для неориентированного графа
число
равно
числу ребер, инцидентных
и
Для
орграфа
равно
числу ребер с началом в
и
концом в
4) О: в качестве маршрута графа
определяют
такую очередность ребер
,
что для двух соседних ребер характерна
общая инцидентная вершина, 
есть
начальная,
-
конечная вершины. Под длиной маршрута
понимают количество ребер маршрута.
О:
Маршрут
именуют
цепью в случае, когда все его ребра
различны. Простой цепью маршрут
можно
назвать, если все его вершины, за
исключением первой и последней, различны.
Так,
для графа, изображенного на рис. 38.4
обозначим:
-
маршрут, а не цепь,
представляет
собой непростую цепь,
является
простой цепью.
О: Цепь, которая предполагает совпадение начальной и конечной вершин, имеет название цикла, в случае, когда цепь простая, — простого цикла.
5) некоторые классы графовДеревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом.
Из
теоремы 2 предыдущей
лекции следует,
что во всяком дереве, в котором не меньше
двух вершин, имеется вершина степени
1. Такие вершины называют висячими
вершинами,
или листьями.
В действительности легко доказать, что
в каждом дереве не меньше двух листьев,
а цепь 
-
пример дерева, в котором точно два листа.
В следующих двух теоремах устанавливаются некоторые свойства деревьев.
Теорема
1.
Граф с 
вершинами
и 
ребрами
является деревом тогда и только тогда,
когда он удовлетворяет любым двум из
следующих трех условий:
(1) связен;
(2) не имеет циклов;
(3)
.
6) (СПУ) - система планирования и управления разработкой крупных нар.-хоз. комплексов, научи, исследованиями, стр-вом, реконструкцией и т. д.; осн. на использовании сетевых моделей, в частности сетевых графиков, оптимизируемых при помощи ЭВМ. Позволяет определять оптим. (по времени, стоимости и др.) последовательность планируемых работ, устанавливать её взаимосвязь с полученными результатами, корректировать план. При использовании совр. техн. средств сбора, передачи, переработки и выдачи информации система СПУ превращается в разновидность автоматизированной системы управления.
Сетевое планирование и управление состоит из трех основных этапов.
1. Структурное планирование.
2. Календарное планирование.
3. Оперативное управление.
Структурное планирование начинается с разбиения проекта на четко определенные
операции, для которых определяется продолжительность. Затем строится сетевой график,
который представляет взаимосвязи работ проекта. Это позволяет детально
анализировать все работы и вносить улучшения в структуру проекта еще до начала
его реализации.
Календарное планирование предусматривает построение календарного графика,
определяющего моменты начала и окончания каждой работы и другие временные
характеристики сетевого графика. Это позволяет, в частности, выявлять критические
операции, которым необходимо уделять особое внимание, чтобы закончить проект
в директивный срок. Во время календарного планирования определяются временные
характеристики всех работ с целью проведения оптимизации сетевой модели, которая
улучшает эффективность использования какого-либо ресурса.
В ходе оперативного управления используются сетевой и календарный графики для
составления периодических отчетов о ходе выполнения проекта. При этом сетевая
модель может подвергаться оперативной корректировке, вследствие чего будет
разрабатываться новый календарный план остальной части проекта.