ЖУРНАЛ НЕОРГАНИЧЕСКОЙ ХИМИИ, 2014, том 59, № 9, с. 1187-1201
^ ^^^^^^ ТЕОРЕТИЧЕСКАЯ
НЕОРГАНИЧЕСКАЯ ХИМИЯ
УДК 541.1:515.162.3
АЛГОРИТМ ТОПОЛОГИЧЕСКОЙ КОРРЕКЦИИ СПИСКОВ РАЗНОРАЗМЕРНЫХ СИМПЛЕКСОВ ДЛЯ ПОЛИЭДРАЦИИ МНОГОКОМПОНЕНТНЫХ СИСТЕМ
© 2014 г. В. И. Луцык, В. П. Воробьева
Институт физического материаловедения СО РАН, Улан-Удэ E-mail: vluts@ipms.bscnet.ru Поступила в редакцию 22.01.2014 г.
Представлен новый алгоритм полиэдрации четверных и четверных взаимных систем. Он основан на переборе всех связей между вершинами графа, описывающего диаграмму состава, и отборе тех вариантов полиэдрации, которые соответствуют соотношениям между количеством геометрических элементов полиэдрируемого комплекса (вершин графа, связей между ними, двух- и трехмерных симплексов). В отличие от известного алгоритма А.Г. Краевой, основанного на декомпозиции графа по нулевым элементам матрицы смежности (отсутствующим связям между вершинами), новый алгоритм позволяет контролировать весь процесс полиэдрации, ускоряет поиск внутренних диагоналей в полиэдре и учитывает возможную их конкуренцию.
DOI: 10.7868/S0044457X14090128
При исследовании многокомпонентных систем возникает необходимость деления концентрационного комплекса (диаграммы состава) на подсистемы — симплексы и (или) микрокомплексы с индивидуальными наборами схем кристаллизации.
Удобной формой анализа полиэдрируемого комплекса являются графы и соответствующие им матрицы смежности. Любой концентрационный комплекс можно описать в виде неориентированного графа, пронумеровав в произвольном порядке вершины, соответствующие исходным компонентам и стехиометрическим соединениям (на ребрах, гранях и внутри полиэдра), и записав матрицу смежности Я, все элементы которой образуются по принципу [1, 2]: г, = 1, если вершина хI соединена с вершиной ху- (х; смежна ху) и г, = 0, если связи между вершинами х; и ху- нет. В результате применение графов, с одной стороны, обеспечивает наглядность представления многомерного комплекса, а с другой — приводит к алгоритмам, позволяющим автоматизировать полиэдрацию многокомпонентной системы.
АЛГОРИТМЫ ДЕКОМПОЗИЦИИ ГРАФА
А.Г. Краева первой применила для разбиения диаграмм состава на подсистемы [3] метод создания семейства независимых подграфов на основе матрицы смежности [4]. В этом методе декомпозиция графа (ДГ), описывающего полиэдр с триангулированными гранями, проводится по нуле-
вым элементам матрицы смежности. Аналогичные задачи можно было бы решать, используя, наоборот, единичные элементы матрицы [2].
При отсутствии соединений разбить призму на тетраэдры можно и не прибегая к специальным алгоритмам. Однако по мере усложнения системы за счет образования соединений и появления внутренних диагоналей трудоемкость полиэдрации "вручную" возрастает. Для автоматизации алгоритма ДГ создают специальные программы (например, [5]: на вход подается список смежности (нулевые элементы матрицы смежности), а на выходе выдается список симплексов).
Применяемый "вручную" или автоматизированный алгоритм ДГ широко используется на практике и часто цитируется [например, 6—11]. Его недостатком является то, что он работает как "черный ящик", процесс полиэдрации невозможно анализировать на промежуточных этапах — для того, например, чтобы понять причину ошибок в случае некорректного его завершения.
Для автоматизации всего процесса исследования системы от литературных данных до эксперимента создан "программный комплекс моделирования дифференциации физико-химических взаимных многокомпонентных систем" [12—14]. В его основу положен не алгоритм ДГ, а алгоритм 457 Брона—Кербоша [15] — метод поиска независимых множеств вершин неориентированного графа — по сути, тоже декомпозиция графа.
Так как уже до начала полиэдрации все связи между вершинами графа на огранении полиэдри-
руемого комплекса известны, то основной проблемой становится определение внутренних диагоналей. Разрабатываются методы, основанные на предложенных в [16, с. 9—14] способах с использованием матриц индексов вершин [17] или взаимных пар солей [11, 18, 19]. Можно использовать алгоритм ДГ, перебирая варианты связей между вершинами графа, которые могли бы стать внутренними диагоналями. При использовании алгоритма 457 Брона—Кербоша в конечном счете тоже производится перебор связей внутри исходного полиэдра, а при их конкуренции "одно из множеств выбирается в общем случае по большему значению энтальпии плавления" [13, с. 49].
Альтернативой этим методам может послужить простой перебор сочетаний единичных элементов матрицы смежности, с помощью которого формируется набор симплексов высшей размерности. Так, для пятерной взаимной системы все возможные сочетания единичных элементов матрицы смежности по 5 сразу выдают список пента-топов — симплексов, на которые разбивается исходный полиэдр [20].
Прием весьма удачный, если в матрице смежности все элементы известны, т.е. отсутствуют внутренние диагонали. При появлении в матрице элементов, значения которых неизвестны из огра-нения, простого перебора единичных элементов недостаточно. Чтобы понять, будет ли каждый из этих неизвестных элементов нулевым (внутренней диагонали нет) или единичным (появляется внутренняя диагональ), потребуется топологическая коррекция комбинаторного перечня получаемых списков симплексов с помощью формул, которые устанавливают количественные соотношения между всеми элементами полиэдра [21].
СООТНОШЕНИЯ МЕЖДУ КОЛИЧЕСТВОМ ВЕРШИН И РЕБЕР ГРАФА С КОЛИЧЕСТВОМ СИМПЛЕКСОВ И ИХ ГРАНИЦ
Если тригональную призму четверной взаимной системы A,B||X,Y,Z (Л,В,С||Х,У) и образующиеся в ней стехиометрические соединения представить в виде графа, то количество вершин графа V (Vertexes) и связей между ними L (Links) в матрице смежности можно выразить в виде [21]:
V = V0 + VE + VF + VI и L = Le + Lf + LI, (1)
где V0 = 6 — количество вершин призмы, VE, VF, VI — количество бинарных, тройных, четверных соединений, т.е. точек на ребрах (Edges), гранях (Faces), внутри (Inside) полиэдра; LE, LF, LI — количество ребер (или их фрагментов — простейших двойных подсистем без соединений, т.е. без внутренних вершин), диагоналей (квазибинарных разрезов) на гранях, внутренних диагоналей.
По классификации Бергмана [22], двойное соединение тройной взаимной системы принадлежит либо стороне, либо диагонали квадрата составов, тройное — треугольнику, отделенному в квадрате стабильной диагональю, четверное соединение образуется из всех четырех исходных солей. Однако в формулах (1) двойными соединениями VE считаются только расположенные на ребрах призмы, тройными VF — расположенные на гранях, четверными VI — внутри призмы.
Величина L равна количеству единичных элементов в матрице смежности. Так как V • V — число всех элементов квадратной матрицы смежности, а (V2 — V)/2 — всех элементов выше (или ниже) ее главной диагонали, то значение L можно подсчитать по формуле
L = (V2 - V)/2 - Lo - L?,
в которой L0 равно числу нулевых элементов матрицы смежности. Через L? обозначено количество всех неизвестных из огранения связей вершин графа. Каждый неизвестный элемент в матрице смежности можно обозначить знаком "?". Впоследствии все эти L? элементов матрицы смежности примут значения нуля или единицы в зависимости от того, станет ли соответствующая ему связь стабильной внутренней диагональю или нет.
Поскольку у тригональной призмы взаимной системы A,B||X,Y,Z LE = 9 ребер и S0 = 5 граней (две треугольные и три четырехугольные), то ребра разбиваются VE точками на LE = 9 + VE отрезков. Количество диагоналей (LF) и симплексов-треугольников (2D Simplexes) на гранях (SF), внутренних секущих плоскостей (SI), трехмерных симплексов-тетраэдров (T, 3D Tetrahedrons) зависит от количества двойных (VE), тройных (VF), четверных (VI) соединений и внутренних диагоналей (LI) [21]:
Lf = 3 + 2Ve + 3VF, SF = 8 + 2Ve + 2Vf, SI = 2 + VE + VF - 2VI + 2LI, T = 3 + VE + VF - VI + LI.
(2)
Известны формулы Эйлера V — L + S = 2 [23, с. 802] и Шлефли—Стрингема V — L + S — Т = 1 [24], связывающие количество симплексов выпуклого многогранника всех размерностей — вершин и ребер графа, 2D и 3D симплексов. Они полезны при верификации полиэдрации. Однако при поиске внутренних секущих этих формул недостаточно. Требуется различать среди симплексов L и S — принадлежащие граням исходного полиэдра и находящиеся внутри полиэдра. Аналогично, симплексы S и Т могут формироваться как с помощью внутренних диагоналей, так и без них.
ТОПОЛОГИЧЕСКАЯ КОРРЕКЦИЯ СПИСКОВ РАЗНОРАЗМЕРНЫХ СИМПЛЕКСОВ ПРИ ПОЛИЭДРАЦИИ С ВНУТРЕННИМИ ДИАГОНАЛЯМИ
Если сформировать из единичных элементов матрицы смежности — отрезков х(ху, а также из всех ее элементов, обозначенных знаком "?", плоскости х(хухь то они разделятся на группы: SF —
с*
плоскостей на гранях; 81 — внутренних плоскостей, в образовании которых не участвуют внут-
о**
ренние диагонали; 81 — внутренних плоскостей, у которых хотя бы одна из сторон является вероятной внутренней диагональю, а соответствующий ей элемент в матрице смежности обозначен как "?".
Далее из плоскостей формируются тетраэдры, которые тоже группируются по принципу, является ли хотя бы один элемент матрицы смежности со значением "?" его ребром или нет: Т* тетраэдров, гранями которых служат плоскости из наборов SF и 8*, никак не связанные с предполагаемыми внутренними диагоналями; остальные Т** тетраэдров, у которых хотя бы одно ребро является возможной внутренней диагональю.
Если выполняются равенства 81 = 8* и Т = Т*,
*
т.е. количество внутренних плоскостей 81 и тетраэдров Т*, образованных без участия внутренних диагоналей, удовлетворяет формулам (2) при LI = 0, то может быть только единственный вариант по-лиэдрации без внутренних диагоналей. Тогда всем элементам матрицы смежности, обозначенным знаком "?", присваивается нуль.
Если 8* < 2 + УЕ + VF - 2У1 и Т* < 3 + УЕ + VF - У1, то LI > 0 и недостающее количество внутренних плоскостей и тетраэдров нужно взять из наборов
8* * и Т**, отобрав удовлетворяющие формулам (2).
Таким образом, комбинации по три и по четыре ненулевых элемента матрицы смежности выдают списки в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.