Основы моделирования химико-технологических систем. Пахомов А.Н - 17 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Граф – совокупность точек (вершин) и совокупность пар этих точек (не обязательно всех), соединённых линиями. Если
на графе линии ориентированы (т.е. стрелками показано направление связи вершин), они называются дугами, или ветвями;
если неориентированы – рёбрами. Соответственно, граф, содержащий только дуги, называется ориентированным, или орг-
рафом; только рёбра – неориентированным; дуги и рёбра – смешанным. Граф, имеющий кратные рёбра, называется мульти-
графом; граф, содержащий только рёбра, принадлежащие двум его непересекающимся подмножествам (частям), – двудоль-
ным; дуги (рёбра) и (или) вершины, которым отвечают определённые веса или числовые значения параметров – взвешен-
ным. Путь в графе – чередующаяся последовательность вершин и дуг, в которой ни одна из вершин не повторяется (напри-
мер a, b на рис. 8.2, а); контур – замкнутый путь, в котором первая и последняя вершины совпадают (рис. 8.2, f, h); петля-
дуга (ребро), которая начинается и кончается в одной и той же вершине. Цепь графа – последовательность рёбер, в которой
ни одна из вершин не повторяется (рис. 8.2, с, d, e); цикл – замкнутая цепь, в которой её начальная и конечная вершины сов-
падают. Граф называется связным, если любая пара его вершин соединена цепью или путём; в противоположном случае
граф называется несвязным.
а)
б)
в) г)
Рис. 8.2. Иллюстрация некоторых основных понятий:
а – смешанный граф; б – основное дерево (сплошные дуги a, h, d, f, h) и
некоторый подграф (пунктирные дуги с, с, g, k, l) орграфа; в, г – матрицы
соответственно смежности и инцидентности орграфа
Дерево-связный неориентированный граф, не содержащий циклов или контуров (рис. 8.2, б). Остовый подграф некото-
рого графа – его подмножество, содержащее все вершины и лишь определённые рёбра. Основное дерево некоторого графа –
его основный подграф, представляющий собой дерево. Графы называются изоморфными, если существует взаимно одно-
значное соответствие между совокупностями их вершин и рёбер (дуг).
Для решения задач графы представляют с помощью матриц (смежности, инцидентности, двустрочных и др.), а также
специальных числовых характеристик. Например, в матрице смежности (рис. 8.2, в) строки и столбцы отвечают номерам
вершин графа, а её элементы принимают значения 0 и 1 (соответвенно, отсутствие и наличие дуги между данной парой вер-
шин); в матрице инцидентности (рис. 8.2, г) строки отвечают номерам вершин, столбцы – номерам дуг, а элементы прини-
мают значения 0, +1 и –1 (соответственно, отсутствие и наличие дуги, входящей в вершину и выходящей из неё). Наиболее
употребительные числовые характеристики: число вершин, число дуг или ребер (n), цикломатическое число, или ранг графа
(п – т + k, где k – число связных подграфов в несвязном графе; например, для графа на рис. 8.2, б ранг будет: 10 – 6 + 1 = 5).
Применение теории графов базируется на построении и анализе различных классов химических и химико-
технологических графов. Дуги (рёбра) и вершины этих графов отображают химические и химико-технологические понятия,
явления, процессы или объекты и, соответственно, качественные и количественные взаимосвязи, либо определённые отно-
шения между ними. Химические графы дают возможность прогнозировать химические превращения, пояснять сущность и
систематизировать некоторые основные понятия химии: структуру, конфигурацию, конформации, квантовомеханичесое и

Страницы