Автор работы: Пользователь скрыл имя, 12 Декабря 2011 в 22:55, доклад
Некоторые основные понятия. Граф - совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединенных линиями (рис. 1,а). Если на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называются дугами, или ветвями; если неориентированы, - ребрами. Соответственно, граф, содержащий только дуги, называется ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра - смешанным. Граф, имеющий кратные ребра, называется мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям), - двудольным; дуги (ребра) и (или) вершины, которым отвечают определенные веса или числовые значения каких-либо параметров, - взвешенным.
Для создания комплексов
программ автоматизированного синтеза
оптимальных высоконадежных производств
(в том числе
Теорию графов используют также для разработки алгоритмов оптимизации временных графиков функционирования оборудования многоассортиментных гибких производств, алгоритмов оптимального размещения аппаратуры и трассировки трубопроводных систем, алгоритмов оптимального управления химико-технологическими процессами и производствами, при сетевом планировании их работы и т.д.