Основні поняття і визначення теорії графів

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Введення
Процеси хімічної технології це складні фізико-хімічні процеси, що протікають як у просторі, так і в часі. У них беруть участь потоки енергії (тепло і холод) і багатофазні та багатокомпонентні потоки речовини.
При розробці схеми конкретного процесу хімічної технології слід, шляхом оптимізації, знайти найкращий (за прийнятим критерієм) варіант рішення з кінцевого безлічі альтернативних. Такий шлях вибору варіанту схеми часто називають синтезом схем. Синтезу схем передує фізико-хімічне дослідження вихідної суміші, що проводиться з метою виявлення обмежень на отримання необхідних (кінцевих) продуктів. Таке дослідження можна назвати предсінтезом схем. Предсінтез схем дозволяє в більшості випадків як суттєво знизити розмірність оптимизируемого безлічі альтернативних варіантів, так і на самому початковому рівні відкинути нереалізующіеся варіанти при синтезі оптимальних схем. Ще одним етапом розробки схеми хіміко-технологічного процесу (ХТП) є вибір оптимальних варіантів конструкції і функціонування конкретних апаратів та вузлів схеми.
Розробку схеми хіміко-технологічного процесу можна розглядати як ієрархічну завдання, розділивши її на декілька рівнів ієрархії. При цьому результати більш низького рівня визначають результати на більш високому рівні, а при неоднозначності рішення на більш високому рівні можливе повернення на більш низький. Кожен рівень ієрархії може складатися з декількох підрівнів пов'язаних або не пов'язаних між собою зворотними зв'язками.
Метою цього курсу з оптимізації побудови ХТП є не стільки навчити набору стандартних рішень, скільки навчити думати, аналізувати завдання, вміти шукати рішення і оцінювати їх результати. Що це означає в наших конкретних обставин? Маючи інформацію про мету, вихідних речовинах, наборі обмежень, можливої ​​сукупності впливів на систему, сформулювати приватні і загальні критерії оптимізації і знайти «кращий з можливих» варіантів.
Сформулюємо деякі корисні визначення. Хіміко-технологічна система (ХТС) - це сукупність взаємопов'язаних технологічними потоками і діють як одне ціле апаратів, у яких здійснюється певна послідовність технологічних операцій (підготовка сировини, власне хімічне перетворення, виділення цільових продуктів). Елемент ХТМ - це апарат, в якому протікає будь-якої типової хіміко-технологічний процес.
Вхідними змінними (параметрами) ХТМ є фізичні параметри вхідних потоків сировини або вихідних продуктів, а також параметри різних фізико-хімічних впливів навколишнього середовища на процес функціонування ХТМ. Вхідні змінні за характером впливу на ХТМ можна розділити на три типи. I. Незмінні вхідні параметри. Ними називаються такі параметри, значення яких можуть бути виміряні, але можливість впливу, на які відсутній. Значення вказаних параметрів не залежать від режиму процесу (наприклад, склад вихідної сировини). II. Керуючі параметри. Це такі параметри, на які можна надавати прямий вплив у відповідності з тими або іншими вимогами, що дозволяє управляти процесом (наприклад, регульоване тиск в реакторі). III. Возмущающие параметри. Такими називаються параметри, значення яких випадковим чином змінюються з часом і які недоступні для вимірювання (наприклад, різні домішки у вихідній сировині).
Вихідні параметри. Під вихідними розуміються параметри, величини яких визначаються режимом процесу і які характеризують його стан, що виникає в результаті сумарного впливу вхідних, керуючих і збурюючих параметрів. Іноді вихідні параметри називають також, параметрами стану. Підкреслюючи тим самим їх призначення описувати стан процесу.
Зазначимо, що дія збурюючих параметрів виявляється в тому, що параметри стану процесу при відомій сукупності вхідних і керуючих параметрів визначаються неоднозначно. Процеси, для яких вплив випадкових збурень велике називають стохастичними. У зворотному випадку - детермінованими.
Основні поняття і визначення теорії графів
Нехай дано безліч Х, яке складається з елементів, званих точками. Дан закон, що дозволяє встановити співвідношення Т між кожним елементом множини Х і деякими з його підмножин. Позначимо через Тх якесь підмножина множини Х, що відповідає елементу х множини Х. Дві математичні величини - «безліч Х» і «відповідність Т» - визначають граф G, що позначається як G = (X, T). Елементи множини Х будемо зображати точками, і називати вершинами графа. Співвідношення Т будемо зображати відрізками (іноді орієнтованими), що з'єднують елемент з елементами підмножини Тх, і називати ребрами або дугами графа. Граф G називається кінцевим, якщо число його вершин звичайно. На рис.1, а показаний граф, який визначається безліччю
X = {x 0, x 1, x 2, x 3, x 4, x 5}.

SHAPE \ * MERGEFORMAT
Х 4
Х 0
Х 5
Х 2
Х 3
Х 1

а)
Х 1


Х 3
Х 2
Х 4
Х n
Х 3

б)
SHAPE \ * MERGEFORMAT
6
5
4
3
2
1
d
b
c
a

в)
Рис.1. Різні графи: а - граф, який визначається безліччю вершин Х = {x 0, x 1, ..., x 5}; б - нуль граф; в - граф, який визначається безліччю вершин Х = {a, b, c, d}.
Співвідношення Т характеризується наступними рівностями:
Tx 0 = {x 0, x 1, x 2, x 3, x 4, x 5}
Tx 1 = {x 0, x 2}
Tx 2 = {x 0, x 1, x 3}
Tx 3 = {x 0, x 2, x 4}
Tx 4 = {x 0, x 3}
Tx 5 = {x 0}
Пара вершин x i, x j утворює ребро, якщо, або точка x i належить підмножині Tx j, або x j належить підмножині Tx i. Якщо будь-яка пара цих точок впорядкована, то така пара визначає дугу графа і граф називається орієнтованим (ріс1.в). Дві точки x i, x j називаються суміжними, якщо вони визначають ребро або дугу графа. Дві різні дуги є суміжними, якщо вони мають спільну вершину. Послідовність дуг, при якій кінець однієї дуги є початком іншої, називається шляхом. Шлях, в якому ніяка вершина не зустрічається двічі, називається елементарним. Якщо початкова та кінцева точки шляху збігаються, утворюється контур. Довжина шляху (контуру) - це число дуг, які його утворюють. Петлею називається контур одиничної довжини; петля пов'язує точку саму з собою. Граф називається зв'язковим, якщо для кожної пари вершин існує з'єднує їх ланцюг (рис.1, в).
Граф називається повним, якщо будь-яка пара його вершин з'єднана ребром.
SHAPE \ * MERGEFORMAT
d '
b '
c '
a '
d
b
a
c

а) б)
Рис.2. Приклад повного графа (а) і ізоморфний йому граф (б)
Граф є не геометричній, а топологічної фігурою. Останньою називають таку фігуру, певні властивості якої інваріантні при взаімнонепреривном і взаимнооднозначное просторовому перетворенні. Істотні інваріантні властивості графа відображають тільки число вершин, число дуг (ребер) і характер зв'язків між вершинами. Так як граф є топологічної фігурою, то один і той же граф може бути зображений різними способами (рис.2). Незалежно від способу зображення, інформація, що міститься в графі, залишається однією і тією ж. Два графа будемо називати ізоморфними, якщо вони мають однакове число вершин, якщо кожній парі вершин, з'єднаних ребром в одному графі, відповідає така ж пара вершин, з'єднаних ребром в іншому графі. Обов'язковою умовою ізоморфності орієнтованих графів є однакова орієнтація всіх дуг.
Представлення графів за допомогою матриць
Інформація, що міститься в деякому графі, може бути представлена ​​в алгебраїчному вигляді за допомогою матриць. Матрицею суміжності, що відповідає деякому графу G = (X, Y), який складається з n вершин X i (i = 1, 2, ..., n), називається матриця [H] порядку (nЧn) з елементами
0, якщо вершина x i не пов'язана дугою з вершиною x j
h ij =
1, якщо вершина x i пов'язана дугою з вершиною x j
Наприклад, матриця [H] деякого графа (рис.1, в) має наступний вигляд:

Структурною матрицею, називається матриця, яка відповідає деякому графу G = (k, q), що складається з n вершин k i (i = 1, 2, ..., n) і з m дуг q j (j = 1, 2, ..., m), називається матриця [S] порядку (nЧm) з елементами
-1, Якщо дуга q j виходить з вершини k i
s ij = +1, якщо дуга q j входить з вершини k i
0, якщо дуга q j НЕ інціндентна вершині k i
В якості прикладу складемо структурну матрицю для того ж графа наведеного на рис.1, в.
j 1 2 3 4 5 6
b
i
d
c
[S] =
a


Потокові графи
Кожній ХТМ можна поставити у відповідність потоковий граф, гомоморфним розглянутій системі і є деякою топологічної моделлю одного типу узагальнених чи фізичних потоків даної системи (рис.3). Потокові графи будують для усталених технологічних режимів.
SHAPE \ * MERGEFORMAT
q 9
q 8
q 7
q 6
q 5
q 4
q 3
q 2
q 1
k 4
k 3
k 2
k 1
n 2
n 1
m 2
m 1

Рис.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. Графічно зобразити потокові графи ХТМ.
Додати в блог або на сайт

Цей текст може містити помилки.

Виробництво і технології | Лекція
35.2кб. | скачати


Схожі роботи:
Основні поняття визначення і закони в теорії електричних ланцюгів
Агресія визначення та основні теорії
Основні визначення теорії електричних ланцюгів
Моделі теорії графів для виділення контурів по градиентному зображенню
Основні теорії праворозуміння Основні причини і закономірності появи права Поняття соціального
Основні поняття економічної теорії
Основні поняття теорії ймовірностей
Основні поняття і визначення підприємства
Культура основні визначення та поняття
© Усі права захищені
написати до нас