Лекция на тему Основные понятия и определения теории графов
Работа добавлена на сайт bukvasha.net: 2014-12-16Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Введение
Процессы химической технологии это сложные физико-химические процессы, протекающие как в пространстве, так и во времени. В них участвуют потоки энергии (тепло и холод) и многофазные и многокомпонентные потоки вещества.
При разработке схемы конкретного процесса химической технологии следует, путем оптимизации, найти наилучший (по принятому критерию) вариант решения из конечного множества альтернативных. Такой путь выбора варианта схемы часто называют синтезом схем. Синтезу схем предшествует физико-химическое исследование исходной смеси, проводимое с целью выявления ограничений на получение требуемых (конечных) продуктов. Такое исследование можно назвать предсинтезом схем. Предсинтез схем позволяет в большинстве случаев как существенно снизить размерность оптимизируемого множества альтернативных вариантов, так и на самом начальном уровне отбросить нереализующиеся варианты при синтезе оптимальных схем. Еще одним этапом разработки схемы химико-технологического процесса (ХТП) является выбор оптимальных вариантов конструкции и функционирования конкретных аппаратов и узлов схемы.
Разработку схемы химико-технологического процесса можно рассматривать как иерархическую задачу, разделив ее на несколько уровней иерархии. При этом результаты более низкого уровня определяют результаты на более высоком уровне, а при неоднозначности решения на более высоком уровне возможен возврат на более низкий. Каждый уровень иерархии может состоять из нескольких подуровней связанных или не связанных между собой обратными связями.
Целью настоящего курса по оптимизации построения ХТП является не столько научить набору стандартных решений, сколько научить думать, анализировать задачу, уметь искать решения и оценивать их результаты. Что это значит в наших конкретных обстоятельствах? Имея информацию о цели, исходных веществах, наборе ограничений, возможной совокупности воздействий на систему, сформулировать частные и общие критерии оптимизации и найти «лучший из возможных» вариантов.
Сформулируем некоторые полезные определения. Химико-технологическая система (ХТС) – это совокупность взаимосвязанных технологическими потоками и действующих как одно целое аппаратов, в которых осуществляется определенная последовательность технологических операций (подготовка сырья, собственно химическое превращение, выделение целевых продуктов). Элемент ХТС – это аппарат, в котором протекает какой-либо типовой химико-технологический процесс.
Входными переменными (параметрами) ХТС являются физические параметры входных потоков сырья или исходных продуктов, а также параметры различных физико-химических воздействий окружающей среды на процесс функционирования ХТС. Входные переменные по характеру воздействия на ХТС можно разделить на три типа. I. Неизменные входные параметры. Ими называются такие параметры, значения которых могут быть измерены, но возможность воздействия, на которые отсутствует. Значения указанных параметров не зависят от режима процесса (например, состав исходного сырья). II. Управляющие параметры. Это такие параметры, на которые можно оказывать прямое воздействие в соответствии с теми или иными требованиями, что позволяет управлять процессом (например, регулируемое давление в реакторе). III. Возмущающие параметры. Такими называются параметры, значения которых случайным образом изменяются с течением времени и которые недоступны для измерения (например, различные примеси в исходном сырье).
Выходные параметры. Под выходными понимаются параметры, величины которых определяются режимом процесса и которые характеризуют его состояние, возникающее в результате суммарного воздействия входных, управляющих и возмущающих параметров. Иногда выходные параметры называют также, параметрами состояния. Подчеркивая тем самым их назначение описывать состояние процесса.
Отметим, что действие возмущающих параметров проявляется в том, что параметры состояния процесса при известной совокупности входных и управляющих параметров определяются неоднозначно. Процессы, для которых влияние случайных возмущений велико называют стохастическими. В обратном случае – детерминированными.
Основные понятия и определения теории графов
Пусть дано множество Х, которое состоит из элементов, называемых точками. Дан закон, позволяющий установить соотношение Т между каждым элементом множества Х и некоторыми из его подмножеств. Обозначим через Тх некое подмножество множества Х, отвечающее элементу х множества Х. Две математические величины – «множество Х» и «соответствие Т» - определяют граф G, обозначаемый как G = (X, T). Элементы множества Х будем изображать точками, и называть вершинами графа. Соотношения Т будем изображать отрезками (иногда ориентированными), соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G называется конечным, если число его вершин конечно. На рис.1,а показан граф, определяемый множеством
X = {x0, x1, x2, x3, x4, x5}.
SHAPE \* MERGEFORMAT
а)
б)
SHAPE \* MERGEFORMAT
в)
Рис.1. Различные графы: а – граф, определяемый множеством вершин Х = {x0, x1, …, x5}; б – нуль граф; в – граф, определяемый множеством вершин Х = {a, b, c, d}.
Соотношение Т характеризуется следующими равенствами:
Tx0 = {x0, x1, x2, x3, x4, x5}
Tx1 = {x0, x2}
Tx2 = {x0, x1, x3}
Tx3 = {x0, x2, x4}
Tx4 = {x0, x3}
Tx5 = {x0}
Пара вершин xi, xj образует ребро, если, либо точка xi принадлежит подмножеству Txj, либо xj принадлежит подмножеству Txi. Если всякая пара этих точек упорядочена, то такая пара определяет дугу графа и граф называется ориентированным (рис1.в). Две точки xi, xj называются смежными, если они определяют ребро или дугу графа. Две различные дуги являются смежными, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Если начальная и конечная точки пути совпадают, образуется контур. Длинна пути (контура) – это число дуг, которые его образуют. Петлей называется контур единичной длинны; петля связывает точку саму с собой. Граф называется связным, если для каждой пары вершин существует соединяющая их цепь (рис.1, в).
Граф называется полным, если любая пара его вершин соединена ребром.
SHAPE \* MERGEFORMAT
а) б)
Рис.2. Пример полного графа (а) и изоморфный ему граф (б)
Граф является не геометрической, а топологической фигурой. Последней называют такую фигуру, определенные свойства которой инвариантны при взаимнонепрерывном и взаимнооднозначном пространственном преобразовании. Существенные инвариантные свойства графа отражают только число вершин, число дуг (ребер) и характер связей между вершинами. Так как граф является топологической фигурой, то один и тот же граф может быть изображен разными способами (рис.2). Независимо от способа изображения, информация, содержащаяся в графе, остается одной и той же. Два графа будем называть изоморфными, если они имеют одинаковое число вершин, если каждой паре вершин, соединенных ребром в одном графе, соответствует такая же пара вершин, соединенных ребром в другом графе. Обязательным условием изоморфности ориентированных графов является одинаковая ориентация всех дуг.
Представление графов с помощью матриц
Информация, содержащаяся в некотором графе, может быть представлена в алгебраическом виде посредством матриц. Матрицей смежности, соответствующей некоторому графу G = (X, Y), который состоит из n вершин Xi (i = 1, 2, …, n), называется матрица [H] порядка (nЧn) с элементами
0, если вершина xi не связана дугой с вершиной xj
hij = 
1, если вершина xi связана дугой с вершиной xj
Например, матрица [H] некоторого графа (рис.1, в) имеет следующий вид:
Структурной матрицей, называется матрица, которая соответствует некоторому графу G = (k, q), состоящему из n вершин ki (i = 1, 2, …, n) и из m дуг qj (j = 1, 2, …, m), называется матрица [S] порядка (nЧm) с элементами
-1, если дуга qj выходит из вершины ki
sij = +1, если дуга qj входит из вершины ki
0, если дуга qj не инциндентна вершине ki
В качестве примера составим структурную матрицу для того же графа приведенного на рис.1, в.
j 1 2 3 4 5 6
i
[S] = 
Потоковые графы
Каждой ХТС можно поставить в соответствие потоковый граф, гомоморфный рассматриваемой системе и являющийся некоторой топологической моделью одного типа обобщенных или физических потоков данной системы (рис.3). Потоковые графы строят для установившихся технологических режимов.
SHAPE \* MERGEFORMAT
Рис.3. Потоковый граф ХТС.
Потоковый граф G = G (A) = (A, T) состоит из множеством вершин А, и образован совокупностью элементов, источников и стоков ХТС, и множеством дуг Т. Его элементы соответствуют одного типа обобщенным или физическим потокам системы. Потоковый граф представляет собой некоторое семейство сочетаний или пар вида Т = (а, b), где a Є A, b Є A, указывающее, какие вершины графа являются смежными. Можно выделить три типа потоковых графов ХТС: материальные, тепловые (энергетические), параметрические.
Вершины материального потокового графа по массовому расходу физических потоков (некоторого химического компонента) соответствуют элементам ХТС, которые трансформируют общие массовые расходы физических потоков (химического компонента), источникам и стокам веществ (компонента). Дуги данного графа отвечают обобщенным материальным потокам.
Вершины теплового потокового графа соответствуют элементам системы, которые изменяют расходы тепла физических потоков, внешним и внутренним источникам и стокам тепла ХТС.
Основные особенности материальных потоковых графов и тепловых потоковых графов. 1) ориентированность; 2) ассиметричность, т.к. не все соседние элементы системы связаны между собой обратными технологическими потоками; 3) связность, т.к. все элементы в системе взаимосвязаны единой цепью потоков веществ и энергии.
Параметрические потоковые графы являются топологической моделью, отображающей преобразование элементами системы параметров физических потоков ХТС. Вершины таких графов отвечают элементам, представляющим собой технологические операторы, которые качественно и (или) количественно преобразуют параметры физических потоков, а также источникам и стокам физических потоков ХТС. Дуги графа соответствуют физическим потокам системы. Такие графы являются конечными, ориентированными, ассиметричными, связными.
В работах Кафарова с сотрудниками предлагается строить потоковые графы, для которых известны технологическая топология и цель функционирования системы по следующему сценарию.
1. Изучить физико-химическую сущность технологических процессов ХТС и построитьее операторную схему.
2. Составить таблицу источников и стоков ХТС.
3. Составить матрицу [K] покомпонентного состава физических потоков системы. Общий элемент такой матрицы 1, если j-ый химический компонент входит в состав i-го физического потока кij= 0, в противном случае причем i = 1 – n – число физических потоков ХТС; j = 1 – m – число химических компонентов системы.
4. Составить таблицы одного типа материальных и тепловых обобщенных потоков системы.
5. Составить таблицы соответствия элементов, источников и стоков системы вершинам ее потокового графа.
6. Составить таблицы соответствия одного типа обобщенных потоков и физических ХТС дугам ее потоковых графов.
7. Графически изобразить потоковые графы ХТС.
Процессы химической технологии это сложные физико-химические процессы, протекающие как в пространстве, так и во времени. В них участвуют потоки энергии (тепло и холод) и многофазные и многокомпонентные потоки вещества.
При разработке схемы конкретного процесса химической технологии следует, путем оптимизации, найти наилучший (по принятому критерию) вариант решения из конечного множества альтернативных. Такой путь выбора варианта схемы часто называют синтезом схем. Синтезу схем предшествует физико-химическое исследование исходной смеси, проводимое с целью выявления ограничений на получение требуемых (конечных) продуктов. Такое исследование можно назвать предсинтезом схем. Предсинтез схем позволяет в большинстве случаев как существенно снизить размерность оптимизируемого множества альтернативных вариантов, так и на самом начальном уровне отбросить нереализующиеся варианты при синтезе оптимальных схем. Еще одним этапом разработки схемы химико-технологического процесса (ХТП) является выбор оптимальных вариантов конструкции и функционирования конкретных аппаратов и узлов схемы.
Разработку схемы химико-технологического процесса можно рассматривать как иерархическую задачу, разделив ее на несколько уровней иерархии. При этом результаты более низкого уровня определяют результаты на более высоком уровне, а при неоднозначности решения на более высоком уровне возможен возврат на более низкий. Каждый уровень иерархии может состоять из нескольких подуровней связанных или не связанных между собой обратными связями.
Целью настоящего курса по оптимизации построения ХТП является не столько научить набору стандартных решений, сколько научить думать, анализировать задачу, уметь искать решения и оценивать их результаты. Что это значит в наших конкретных обстоятельствах? Имея информацию о цели, исходных веществах, наборе ограничений, возможной совокупности воздействий на систему, сформулировать частные и общие критерии оптимизации и найти «лучший из возможных» вариантов.
Сформулируем некоторые полезные определения. Химико-технологическая система (ХТС) – это совокупность взаимосвязанных технологическими потоками и действующих как одно целое аппаратов, в которых осуществляется определенная последовательность технологических операций (подготовка сырья, собственно химическое превращение, выделение целевых продуктов). Элемент ХТС – это аппарат, в котором протекает какой-либо типовой химико-технологический процесс.
Входными переменными (параметрами) ХТС являются физические параметры входных потоков сырья или исходных продуктов, а также параметры различных физико-химических воздействий окружающей среды на процесс функционирования ХТС. Входные переменные по характеру воздействия на ХТС можно разделить на три типа. I. Неизменные входные параметры. Ими называются такие параметры, значения которых могут быть измерены, но возможность воздействия, на которые отсутствует. Значения указанных параметров не зависят от режима процесса (например, состав исходного сырья). II. Управляющие параметры. Это такие параметры, на которые можно оказывать прямое воздействие в соответствии с теми или иными требованиями, что позволяет управлять процессом (например, регулируемое давление в реакторе). III. Возмущающие параметры. Такими называются параметры, значения которых случайным образом изменяются с течением времени и которые недоступны для измерения (например, различные примеси в исходном сырье).
Выходные параметры. Под выходными понимаются параметры, величины которых определяются режимом процесса и которые характеризуют его состояние, возникающее в результате суммарного воздействия входных, управляющих и возмущающих параметров. Иногда выходные параметры называют также, параметрами состояния. Подчеркивая тем самым их назначение описывать состояние процесса.
Отметим, что действие возмущающих параметров проявляется в том, что параметры состояния процесса при известной совокупности входных и управляющих параметров определяются неоднозначно. Процессы, для которых влияние случайных возмущений велико называют стохастическими. В обратном случае – детерминированными.
Основные понятия и определения теории графов
Пусть дано множество Х, которое состоит из элементов, называемых точками. Дан закон, позволяющий установить соотношение Т между каждым элементом множества Х и некоторыми из его подмножеств. Обозначим через Тх некое подмножество множества Х, отвечающее элементу х множества Х. Две математические величины – «множество Х» и «соответствие Т» - определяют граф G, обозначаемый как G = (X, T). Элементы множества Х будем изображать точками, и называть вершинами графа. Соотношения Т будем изображать отрезками (иногда ориентированными), соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G называется конечным, если число его вершин конечно. На рис.1,а показан граф, определяемый множеством
X = {x0, x1, x2, x3, x4, x5}.
SHAPE \* MERGEFORMAT
| Х4 |
| Х0 |
| Х5 |
| Х2 |
| Х3 |
| Х1 |
а)
|
|
|
|
|
|
б)
SHAPE \* MERGEFORMAT
| 6 |
| 5 |
| 4 |
| 3 |
| 2 |
| 1 |
| d |
| b |
| c |
| a |
в)
Рис.1. Различные графы: а – граф, определяемый множеством вершин Х = {x0, x1, …, x5}; б – нуль граф; в – граф, определяемый множеством вершин Х = {a, b, c, d}.
Соотношение Т характеризуется следующими равенствами:
Tx0 = {x0, x1, x2, x3, x4, x5}
Tx1 = {x0, x2}
Tx2 = {x0, x1, x3}
Tx3 = {x0, x2, x4}
Tx4 = {x0, x3}
Tx5 = {x0}
Пара вершин xi, xj образует ребро, если, либо точка xi принадлежит подмножеству Txj, либо xj принадлежит подмножеству Txi. Если всякая пара этих точек упорядочена, то такая пара определяет дугу графа и граф называется ориентированным (рис1.в). Две точки xi, xj называются смежными, если они определяют ребро или дугу графа. Две различные дуги являются смежными, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Если начальная и конечная точки пути совпадают, образуется контур. Длинна пути (контура) – это число дуг, которые его образуют. Петлей называется контур единичной длинны; петля связывает точку саму с собой. Граф называется связным, если для каждой пары вершин существует соединяющая их цепь (рис.1, в).
Граф называется полным, если любая пара его вершин соединена ребром.
SHAPE \* MERGEFORMAT
| d’ |
| b’ |
| c’ |
| a’ |
| d |
| b |
| a |
| c |
а) б)
Рис.2. Пример полного графа (а) и изоморфный ему граф (б)
Граф является не геометрической, а топологической фигурой. Последней называют такую фигуру, определенные свойства которой инвариантны при взаимнонепрерывном и взаимнооднозначном пространственном преобразовании. Существенные инвариантные свойства графа отражают только число вершин, число дуг (ребер) и характер связей между вершинами. Так как граф является топологической фигурой, то один и тот же граф может быть изображен разными способами (рис.2). Независимо от способа изображения, информация, содержащаяся в графе, остается одной и той же. Два графа будем называть изоморфными, если они имеют одинаковое число вершин, если каждой паре вершин, соединенных ребром в одном графе, соответствует такая же пара вершин, соединенных ребром в другом графе. Обязательным условием изоморфности ориентированных графов является одинаковая ориентация всех дуг.
Представление графов с помощью матриц
Информация, содержащаяся в некотором графе, может быть представлена в алгебраическом виде посредством матриц. Матрицей смежности, соответствующей некоторому графу G = (X, Y), который состоит из n вершин Xi (i = 1, 2, …, n), называется матрица [H] порядка (nЧn) с элементами
0, если вершина xi не связана дугой с вершиной xj
hij =
1, если вершина xi связана дугой с вершиной xj Например, матрица [H] некоторого графа (рис.1, в) имеет следующий вид:
Структурной матрицей, называется матрица, которая соответствует некоторому графу G = (k, q), состоящему из n вершин ki (i = 1, 2, …, n) и из m дуг qj (j = 1, 2, …, m), называется матрица [S] порядка (nЧm) с элементами
-1, если дуга qj выходит из вершины ki
sij = +1, если дуга qj входит из вершины ki 0, если дуга qj не инциндентна вершине ki
В качестве примера составим структурную матрицу для того же графа приведенного на рис.1, в.
j 1 2 3 4 5 6
|
i
|
|
|
Потоковые графы
Каждой ХТС можно поставить в соответствие потоковый граф, гомоморфный рассматриваемой системе и являющийся некоторой топологической моделью одного типа обобщенных или физических потоков данной системы (рис.3). Потоковые графы строят для установившихся технологических режимов.
SHAPE \* MERGEFORMAT
| q9 |
| q8 |
| q7 |
| q6 |
| q5 |
| q4 |
| q3 |
| q2 |
| q1 |
| k4 |
| k3 |
| k2 |
| k1 |
| n2 |
| n1 |
| m2 |
| m1 |
Рис.3. Потоковый граф ХТС.
Потоковый граф G = G (A) = (A, T) состоит из множеством вершин А, и образован совокупностью элементов, источников и стоков ХТС, и множеством дуг Т. Его элементы соответствуют одного типа обобщенным или физическим потокам системы. Потоковый граф представляет собой некоторое семейство сочетаний или пар вида Т = (а, b), где a Є A, b Є A, указывающее, какие вершины графа являются смежными. Можно выделить три типа потоковых графов ХТС: материальные, тепловые (энергетические), параметрические.
Вершины материального потокового графа по массовому расходу физических потоков (некоторого химического компонента) соответствуют элементам ХТС, которые трансформируют общие массовые расходы физических потоков (химического компонента), источникам и стокам веществ (компонента). Дуги данного графа отвечают обобщенным материальным потокам.
Вершины теплового потокового графа соответствуют элементам системы, которые изменяют расходы тепла физических потоков, внешним и внутренним источникам и стокам тепла ХТС.
Основные особенности материальных потоковых графов и тепловых потоковых графов. 1) ориентированность; 2) ассиметричность, т.к. не все соседние элементы системы связаны между собой обратными технологическими потоками; 3) связность, т.к. все элементы в системе взаимосвязаны единой цепью потоков веществ и энергии.
Параметрические потоковые графы являются топологической моделью, отображающей преобразование элементами системы параметров физических потоков ХТС. Вершины таких графов отвечают элементам, представляющим собой технологические операторы, которые качественно и (или) количественно преобразуют параметры физических потоков, а также источникам и стокам физических потоков ХТС. Дуги графа соответствуют физическим потокам системы. Такие графы являются конечными, ориентированными, ассиметричными, связными.
В работах Кафарова с сотрудниками предлагается строить потоковые графы, для которых известны технологическая топология и цель функционирования системы по следующему сценарию.
1. Изучить физико-химическую сущность технологических процессов ХТС и построитьее операторную схему.
2. Составить таблицу источников и стоков ХТС.
3. Составить матрицу [K] покомпонентного состава физических потоков системы. Общий элемент такой матрицы 1, если j-ый химический компонент входит в состав i-го физического потока кij= 0, в противном случае причем i = 1 – n – число физических потоков ХТС; j = 1 – m – число химических компонентов системы.
4. Составить таблицы одного типа материальных и тепловых обобщенных потоков системы.
5. Составить таблицы соответствия элементов, источников и стоков системы вершинам ее потокового графа.
6. Составить таблицы соответствия одного типа обобщенных потоков и физических ХТС дугам ее потоковых графов.
7. Графически изобразить потоковые графы ХТС.
