Топос идея

Для того чтобы проиллюстрировать идею топоса как инвариантной структуры данных, рассмотрим Египетский треугольник $\triangle ABC$ со сторонами:

• $a = BC = 3$
• $b = CA = 4$
• $c = AB = 5$

Проверка Пифагора: $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.

Динамика потока

Введём на множестве сторон вектор состояния $\mathbf{l} = (a, b, c)^T$ и запустим процесс диффузии длин, описываемый уравнением в частных производных (аналог уравнения теплопроводности на графе): В отношении сторон данного треугольника мы рассмотрим следующий поток диффизуии длинн

$$ \frac{\partial \mathbf{l}}{\partial t} = -\text{div}\left( \Lambda \cdot \text{grad} , \mathbf{l} \right) $$

где:

• $\mathbf{l}$ — вектор длин сторон треугольника;
• $t$ — время (параметр эволюции);
• $\Lambda$ — доля перетекающего параметра.

Дискретная численная схема

Для численного моделирования перейдём к явной дискретной схеме. Определим поток параметра вдоль направленных рёбер графа (цикла $a \to b \to c \to a$):

$$ \begin{aligned} flow_{ab} &= \lambda_{ab}(b - a) \\ flow_{bc} &= \lambda_{bc}(c - b) \\ flow_{ca} &= \lambda_{ca}(a - c) \end{aligned} $$

Дивергенция (баланс) параметра в каждой вершине графа (стороне треугольника):

$$ \begin{aligned} \text{div}_a &= flow_{ca} - flow_{ab} \\ \text{div}_b &= flow_{ab} - flow_{bc} \\ \text{div}_c &= flow_{bc} - flow_{ca} \end{aligned} $$

Шаг эволюции (явная схема Эйлера):

$$ \mathbf{l}_{\text{new}} = \mathbf{l}_{\text{old}} + \alpha \cdot \mathbf{div}, \quad \text{где } \mathbf{div} = \begin{pmatrix} \text{div}_a \ \text{div}_b \ \text{div}_c \end{pmatrix} $$

Сохранение инвариантов и предельный топос

Несложно показать, что под действием данного потока Египетский треугольник $(3,4,5)$ плавно и непрерывно деформируется в равносторонний треугольник $(P/3, P/3, P/3)$.

Исходный треугольник и полученный равносторонний связаны морфизмом (диффузионным потоком), сохраняющим структурные инварианты — периметр и сумму углов. В этом смысле равносторонний треугольник является топосом исходного Египетского треугольника.

Определение топоса

Под топосом в контексте данной работы мы понимаем такую структуру данных, которая:

1. Связана с исходным объектом вычислимым морфизмом;
2. Сохраняет заданный набор интегральных мер (инвариантов) исходного объекта.

Альтернативные алгоритмы и вычислительная эффективность

Принципиальное преимущество концепции топоса заключается в том, что для его получения могут существовать альтернативные алгоритмы, в том числе работающие за константное время $O(1)$.

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

1. Вычислить периметр $P = a + b + c$;
2. Равномерно распределить его длину между тремя сторонами: $a' = b' = c' = P/3$.