Модели ступенчатых представлений на графах

В.И. Кругленко
Камский институт,
г. Набережные Челны

В граф, в котором степень каждой вершины L=а₁*а₂*а₃……*а_N, вводим N-мерную координатную систему графа. При каждой вершине каждому ребру присваиваем числа от 0 до а₁-1так, чтобы количества разных чисел были равными L / а₁. Затем при каждой вершине всем группам ребер с одинаковыми числами присваиваем еще значения от 0 до а₂-1 так, чтобы количества этих разных чисел были равными L / а₁а₂ и т. д. Таким образом для каждого ребра формируем координатную единицу. Например, для L=36 можно ввести 1 одномерную, 7 двухмерных, 12 трехмерных и 6 четырехмерных систем. Перестановка разных сомножителей приводит к изменению координатной системы.

Далее вводим понятие ступенчатого представления как совокупность последовательных переходов между вершинами с помощью N a_i-ричных координатных последовательностей, компоненты которых соответствуют координатным единицам.

Смоделируем представление Ф (α, β) для следующего двухмерного случая. В качестве графа выберем двухмерную прямоугольную граф-решетку. Для построения Ф (α, β) в качестве α выберем двоичное разложение дроби 2/3, в качестве β – двоичное разложение дроби 1/300149. На рис.1 приведены периодический элемент для асимметричной координатной системы и сформированное ступенчатое представление с малой единицей решетки.

Рис. 1. Координатная система и ступенчатое представление

Хотя граф с бесконечным числом вершин и α, β - бесконечные периодические последовательности, ступенчатое представление в этом случае ограничено. Можно отметить, что Ф(2/3, n/р) на выбранной граф-решетке с введенной асимметричной системой координат будут ограничены при любых n, если р - простое и выражение (2 ^{(р-1) / 2} +1) / р – целое. Вопрос оценки объемов подобных представлений открыт. Далее на рис.2 показано влияние на представление разных α при одних и тех же β .

α - 0101010101010101…….. α - 110110110110110110110……..

β – двоичн. разложение дроби 1/24781 β – двоичн. разложение дроби 1/24781

Рис. 2. Влияние изменения α в Ф (α, β) на представление

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

Рис.3. Четырех вершинный граф

Формируем ступенчатые представления Ф (α,β) на графе в зависимости от разных α, β.

Результаты эмпирического моделирования спектров приведены в таблице.

Если α и β оба периодические, то спектр получался устойчивым, неравномерным. Если случайные, то спектр ближе к равномерному.

Двоичные последовательности от чисел π и е ведут себя ближе к случайным, т.е. распределение ближе к равномерному. Но все-таки подходящим выбором второй координатной последовательности спектр получился неравномерным (последние две строки). Предполагается, что подобные модели, возможно, использовать в прикладных науках.

Назад к списку