Алгоритм вычисления определителей предфрактальных графов с полными затравками, сохраняющих смежность старых ребер

Размещено на http://www.allbest.ru/

УДК 519.1

Северо-Кавказская государственная гуманитарно-технологическая академия, Черкесск, Россия

Алгоритм вычисления определителей предфрактальных графов с полными затравками, сохраняющих смежность старых ребер

Байрамукова Зухра Халитовна

Кочкаров Ахмат Магометович

д.ф.-м.н., профессор

Аннотация

В статье получен алгоритм - рекуррентная формула для вычисления определителей предфрактальных графов с полными затравками, сохраняющих смежность старых ребер в траектории

Ключевые слова: БАЗИСНЫЕ ФИГУРЫ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ, ОПРЕДЕЛИТЕЛИ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ

рекуррентный граф матрица смежность

Annotation

In the article, the algorithm - a recurrent formula for calculation of determinants of prefractal graphs with the full primers, keeping old edges contiguity in a trajectory was received

Keywords: BASIC FIGURES OF PREFRACTAL GRAPHS, DETERMINANTS OF PREFRACTAL GRAPHS

В настоящее время бурно развивается раздел дискретной математики, направление - спектральная теория графов [1] , основанный на алгебраических инвариантах графов - его спектрах. Спектральная теория графов позволяет выявить зависимость между спектральными и структурными свойствами графов, характеризовать графы спектрами. Что позволяет разработать приложения спектрального метода как в самой теории графов, так и в комбинаторике, в физике при исследовании физических моделей, в которых спектры графов имеют важное самостоятельное значение. В настоящее время теоретико-графовые (топологические) подходы приобрели для прикладных задач большое значение. Как известно, задачи, структура которых меняется во времени и, более того, размерность этих задач изменяется во времени (увеличивается), можно моделировать с помощью предфрактальных и фрактальных графов [2], [3]. При исследовании сетей больших размерностей изменяющихся во времени - так называемых больших и малых миров также моделируют с помощью предфрактальных и фрактальных графов [4]. Чтобы выявить связи между спектральными и структурными свойствами предфрактальных графов необходимо вычислять определители их матриц смежности.

А также при исследовании многих задач математического программирования [5], задач экономики с определением балансов [6], в задачах теории графов [7] часто приходится вычислять определители. Например, в задачах линейного программирования [8], чтобы найти решение систем линейных уравнений ограничения с использованием метода Крамера, необходимо вычислять определители матриц коэффициентов системы ограничения. А в теории графов вычисляются определители матриц смежностей для определения тех или иных инвариантов графов. Как только задачи становятся большой размерности, вычисление определителя усложняется.

В настоящей работе рассматривается вычисление определителей матриц смежностей предфрактальных графов [9] с полными затравками, смежность старых ребер которых в траектории не нарушается. Приведем в начале несколько понятий, часто применяемых в данной работе.

Термином затравка условимся называть какой-либо связный граф . Для определения фрактального (предфрактального) графа [9], [10],[11] нам потребуется операция замены вершины затравкой (3В3). Суть операции 3В3 заключается в следующем. В данном графе у намеченной для замещения вершины выделяется множество , , смежных ей вершин. Далее из графа удаляется вершина и все инцидентные ей ребра. Затем каждая вершина , соединяется ребром с (одной и той же, если смежность старых ребер сохраняется) вершиной затравки

Предфрактальный граф будем обозначать через , где - множество вершин графа, а - множество его ребер. Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе графе каждую его вершину затравкой . На этапе предфрактальному графу соответствует затравка . Об описанном процессе говорят, что предфрактальный граф порожден затравкой . Процесс порождения предфрактального графа , по существу, есть процесс построения последовательности предфрактальных графов называемый траекторией. Для предфрактального графа , ребра появившиеся на l-том этапе порождения, будем называть ребрами ранга l. Новыми ребрами предфрактального графа назовем ребра ранга , а все остальные ребра назовем - старыми.

Если из предфрактального графа , порожденного n-вершинной затравкой , последовательно удалить все старые ребра (ребра ранга , ), то исходный граф распадется на множество связных компонент , каждая из которых изоморфна [7] затравке . Множество компонент будем называть блоками первого ранга. Аналогично, при удалении из предфрактального графа всех старых ребер рангов , получим множество блоков второго ранга изоморфных предфрактальному графу . Обобщая, скажем, что при удалении из предфрактального графа всех ребер рангов , получим множество , блоков r-го ранга изоморфных предфрактальному графу. Измененным блоком r-го ранга мы будем называть блок r-го ранга, из которого удалена одна вершина затравки и все инцидентные ей ребра.

«Элементарной фигурой» [1] называется : а) граф (ребро) или б) любой граф (простой цикл); «базисной фигурой» называется любой граф, все компоненты которого являются элементарными фигурами. - число базисных фигур с вершинами в предфрактальном графе , - число базисных фигур с вершинами в измененных блоках, имеющих простых циклов и компонент.

Для вычисления определителей в данной работе используется

Лемма [1].Определитель матрицы смежностей графа с вершинами вычисляется по формуле

,

где - число компонент, - число простых циклов, содержащихся в , а означает множество всех базисных фигур, содержащихся в графе и имеющих точно вершин.

В результате применения леммы к предфрактальным графам, получена

Теорема. Определитель матрицы смежностей предфрактального графа с полной -вершинной затравкой вычисляется по формуле

.

Суммирование ведется по множеству чисел базисных фигур с вершинами, которое определяет формула

И

Доказательство. Условие теоремы предполагает, что определены множества , . С увеличением l в предфрактальном графе появляются новые вершины и новые ребра, то есть его форма усложняется. Для того чтобы систематизировать процесс нахождения чисел базисных фигур , используем схему:

1) в базисных фигурах графа с вершинами отсутствуют ребра 1-го ранга (нет измененных блоков);

2) из старых ребер 1-го ранга сохранено одно ребро (два измененных блока);

3) из старых ребер 1-го ранга сохранен цикл (три измененных блока);

. . . . . . . . . . . . . . . . . . .

n) из старых ребер 1-го ранга сохранены базисные фигуры затравки(имеется измененных блоков).

Для подсчета числа базисных фигур по каждому пункту схемы используем правило умножения из комбинаторики. Суммируя количества базисных фигур с равным числом циклов с и компонент p из всех пунктов схемы, получаем

Здесь каждая сумма получена в соответствующем пункте схемы.

Для вычисления используем схему:

1) в базисных фигурах нет ребер 1-го ранга (один измененный блок - го ранга);

2) в базисных фигурах имеется одно ребро 1-го ранга (три измененных блока - го ранга);

3) имеется цикл из ребер 1-го ранга (четыре измененных блока - го ранга);

. . . . . . . . . . . . . .

n-1) из ребер 1-го ранга в базисные фигуры измененного блока - го ранга входят базисные фигуры затравки с вершинами.

Отсюда следует формула

Теорема доказана.

Вычислим, к примеру, при. По теореме имеем:

определитель матрицы смежностей предфрактального графа с полной четырехвершинной затравкой вычисляется по рекуррентной формуле

,

Где

принадлежат множеству всех чисел базисных фигур этапа , а - множеству всех чисел базисных фигур в измененных блоках.

Пусть . Рассматриваем граф (рис.1).

Рис.1.

Построим все базисные фигуры в графе с 4-мя вершинами (рис.2).

Рис.2.

Первые три фигуры имеют 0 циклов и 2 компоненты, т.е.. Остальные три-1 цикл и 1 компоненту,. Т.о. по лемме получаем

Пусть . Рассматриваем граф (рис.3) по схеме:

Рис.3.

1) в базисных фигурах графа с вершинами отсутствуют ребра 1-го ранга (нет измененных блоков) (рис. 4а));

2) из старых ребер 1-го ранга сохранено одно ребро (два измененных блока) ( например, рис. 4б));

3) из старых ребер 1-го ранга сохранен цикл (три измененных блока) (например, рис.4в));

4) из старых ребер сохранен либо цикл или два ребра, не имеющих общую вершину (4 измененных блока) (рис. 4г)), т.е. базисные фигуры затравки.

Рис.4.

Т.о., все базисные фигуры графа с 16 вершинами содержатся в графах этих 4-х видов.

1)

где ,

,

,

;

2),

;

,

3)

.

4)

,

Таким образом,

.

Следовательно,

Задача вычисления определителей матриц смежности предфрактальных графов рассматривается впервые. Получен алгоритм вычисления определителей предфрактальных графов с полными затравками, сохраняющих смежность старых ребер в траектории. Для вычисления определителей таких предфрактальных графов использован способ (лемма [1]), основанный на рассмотрении структуры графа. Полученный алгоритм упрощает процесс вычисления, поскольку при его использовании нет необходимости рассматривать ни матрицу смежности предфрактального графа, ни его структуру, и сводит к работе с множеством чисел базисных фигур предыдущего этапа траектории.

Список литературы

1. Цветкович Д., Дуб М., Захс Х. Спектры графов: теория и применение. Наукова Думка. Киев.1984. 384 с.

2. Кочкаров А.А., Сенникова Л.И. Количественные оценки некоторых связностных характеристик предфрактальных графов. // Прикладная дискретная математика. -2011.№ 4(14) -С. 56-61.

3. Кочкаров А.А. Структурная динамика: свойства и количественные характеристики предфрактальных графов. - М.: Вега-Инфо, 2012.- 120 с.

4. Кочкаров А.А. Новые теоретико-графические подходы в моделировании сложных систем: Автореф. дис. … канд. физ.-матем. наук . М.: ИПМатем. им. М.В. Келдыша. РАН, 2005. 24с.

5. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование.- М.: Высшая школа,1980. 302 с.

6. Малыхин В.И. Математика в экономике.-М.: ИНФРА-М.2000. 356 с.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. -М.:Наука,1990. 384 с.

8. Ашманов С.А. Линейное программирование. - М.: Наука,1981. 340 с.

9. Кочкаров А. М. Распознавание фрактальных графов. Алгоритмический подход.- Нижний Архыз: РАН САО.1998. 170 с.

10. Байрамукова З.Х., Кочкаров А.М. Спектры предфрактальных графов с затравками - циклами, сохраняющих смежность старых ребер.// Научный журнал КубГАУ. №81(07). 2012 года. 10 с.

11. Кочкаров А.А., Кочкаров Р.А. Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе. // Журнал вычислительной математики и математической физики. - Т. 44. № 6.-С. 1147 - 1152.

Размещено на Allbest.ru