ПОИСК Статьи Рисунки Таблицы Основные понятия и определения теории графов из "Принципы математического моделирования химико-технологических систем" Большая сложность технологической топологии современных проектируемых и действующих ХТС, многомерность их как по числу составляющих элементов, так и по числу выполняемых ими функций, высокая степень взаимосвязанности и параметрического взаимовлияния элементов обусловливают возникновение при решении задач анализа и синтеза химико-технологических систем ряда принципиальных трудностей научно-исследовательского, методологического и вычивлительного характера. [c.114] Указанные трудности могут быть в значительной мере преодолены благодаря применению топологического метода анализа ХТС. Этот метод позволяет формальным образом устанавливать функциональную связь между технологической топологией и количественными характеристиками функционирования системы в виде материальных и тепловых нагрузок на элементы ХТС. С помощью топологического метода анализа можно разрабатывать оптимальные алгоритмы расчета на ЦВМ многомерных систем уравнений математических моделей ХТС, в частности систем уравнений балансов, выбирать оптимальную стратегию решения задач анализа функционирования и оптимизации сложных систем, которая обеспечивает минимальные затраты машинного времени ЦВМ. [c.114] Топологический метод анализа ХТС основан на рассмотрении математических иконографических (топологических) моделей систем, которыми являются потоковые и структурные графы, информационно-потоковые мультиграфы, информационные и сигнальные графы ХТС. Применение этих топологических моделей позволяет большой объем существенной информации о сложной ХТС представлять в компактной и наглядной форме, которая уже сама по себе дает возможность составить качественное представление о некоторых свойствах исследуемой системы. [c.114] Классификация топологических моделей ХТС. Для решения задач исследования ХТС используют три класса топологических моделей. [c.114] Ко второму классу топологических моделей принадлежат информационно-потоковые мулътиграфы и информационные графы. Эти графы отображают характеристические особенности символических математических моделей и позволяют разрабатывать оптимальную стратегию решения задач исследования ХТС. [c.115] К третьему классу топологических моделей относятся сигнальные-графы, которые графически изображают функциональные связи между переменными символических математических моделей ХТС. Сигнальные графы можно применять для определения динамических и статических характеристик ХТС, расчета функций чувствительности характеристик систем к изменениям их параметров, а также для оценки устойчивости процессов функционирования ХТС. [c.115] Дано множество X, которое состоит из элементов, называемых точками, и дан закон, позволяющий установить соответствие Т между каждым элементом множества X и некоторыми из его подмножеств. Обозначим через Тх подмножество X, отвечающее элементу X множества X. [c.115] Две математические величины — множество Xi и соответствие Г — определяют граф G, обозначаемый как G = (X, Т). Элементы множества X будем изображать точками и называть вершинами графа, а соответствие Т отрезками (иногда направленными),. соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G = X, Т) называется конечным, если число его вершин конечно. Граф G называется Г-конечным, если для каждой вершины х X множество Тх конечно. [c.115] Граф называется симметрическим, если для любых двух вершин и из того, что ж, принадлежит подмножеству Тх/, следует, что а / принадлежит Гх,. Если эти условия удовлетворяются не для всех пар точек графа, то граф называется асимметрическим. Граф Со, который состоит из изолированных вершин, не соединенных ребрами, называют нуль-графом (рис. IV- ,б). [c.116] Пара вершин Х( и х (где точка принадлежит подмножеству Тх/ или точка Х/ принадлежит подмножеству Га ,.) образует ребро графа. Если, кроме того, всякая пара этих точек упорядочена, то такая пара определяет дугу графа и граф называется ориентированным (направленны м). Ребра на рис. IV- , а представляются отрезками, имеющими концы в точках и а . чтобы получить соответствующую им дугу, достаточно показать стрелками направления на данном ребре (т. е. начало и конец). Две точки Х1 и х называются смежными, если они определяют ребро или дугу графа. [c.116] С каждой неизолированной вершиной 1 графа С связано одно или несколько ребер (дуг). Эти ребра (дуги) называют инцидентными вершине г. Так, вершине а на рис. IV- , в инцидентны ребра 1, 4, 5, вершине с — ребра 2, 3, 5 и т. д. [c.116] Две различные дуги смежны, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. Таким образом, путь определяется последовательностью его дуг, или последовательностью вершин этих дуг. Путь, в котором никакая вершина дважды не встречается, называется элементарным. [c.116] Если начальная и конечная точки пути совпадают, образуется контур. Он называется элементарным, если все его вершины различны (за исключением начальной и конечной вершин, которые совпадают). Длина пути (контура) — это число дут, которые его образуют. [c.116] Петлей называется контур единичной длины петля связывает точку саму с собой (рис. 1У-2). [c.116] Заметим, что понятия ребра, цепи и цикла отличаются от понятий дуги, пути и контура только тем, что для последних принимается во внимание направление (ориентация). [c.117] Вектор х пространства Нп будем называть вектором-циклом, соответствующим циклу р,. [c.117] Циклы называются независимыми, если независимы. [c.117] Несвязный граф состоит из нескольких отдельных связных графов или его компонентов (рис. 1У-4, б). [c.117] Используя приведенные определения, можно несколько изменить определение симметрического графа, сделанное выше. В случав симметричности каждая пара смежных точек характеризует две дуги противоположного направления. С другой стороны, граф не является симметрическим, когда имеется хоть одна пара смежных точек, связанных дугой. [c.117] Граф называется полным, если любая пара его вершин соедпнена ребром (рис. 1У-5). [c.118] Вернуться к основной статье