Обзор 2017-2026
Алгебры бинарных формул для произведений графов
От декартовых и тензорных произведений к модулярному и ко-нормальному произведению
Д.Ю. Емельянов
Институт математики им. С.Л. Соболева СО РАН, Новосибирск
Работа выполнена в рамках государственного задания Института математики им. С. Л. Соболева СО РАН, проект № FWNF-2026-0032.
Постановка
Граф как структура первого порядка
Язык
Граф \(X=(V,E)\) рассматривается как структура первого порядка в языке \(L=\{R\}\), где \(R(x,y)\) означает смежность вершин.
Теория
Каждому графу соответствует полная теория \(\operatorname{Th}(X)\). Нас интересуют формулы этой теории, которые различают пары вершин.
Примеры бинарных условий.
\[
x=y,\qquad R(x,y),\qquad \exists z\,(R(x,z)\wedge R(z,y)).
\]
Первая формула говорит, что вершины совпадают; вторая — что они смежны; третья — что между ними есть путь длины \(2\).
Бинарные формулы
Формулы от двух свободных переменных
Определение. Бинарной формулой называется формула первого порядка \(\varphi(x,y)\) с двумя свободными переменными \(x\) и \(y\). Остальные переменные, если они есть, связаны кванторами.
Две бинарные формулы считаются одинаковыми для графа \(X\), если они эквивалентны в его теории:
\[
\operatorname{Th}(X)\models
\forall x\,\forall y\,(\varphi(x,y)\leftrightarrow \psi(x,y)).
\]
Поэтому дальше мы работаем не с синтаксической записью формулы, а с ее классом по эквивалентности в фиксированной теории графа.
Изолирующие формулы
От формул к меткам пар вершин
Бинарная изолирующая формула. Формула \(\varphi(x,y)\) называется изолирующей, если в теории \(\operatorname{Th}(X)\) она выделяет один полный \(2\)-тип пары вершин: всякая другая бинарная формула для такой пары уже либо следует из \(\varphi\), либо несовместна с ней.
Метки
Классы изолирующих формул заменяются короткими метками \(0,1,2,\ldots\). Для циклов это часто расстояния; для общих графов — орбиты пар или локальные типы.
Композиция
Запись \(i\cdot j\) означает все метки пары \((a,c)\), если существует вершина \(b\), такая что \((a,b)\) имеет метку \(i\), а \((b,c)\) имеет метку \(j\).
Определение произведения
Декартово произведение
\(G \times H\)
Определение. Декартово, или прямое, произведение \(G\times H\) имеет множество вершин \(V(G)\times V(H)\). Вершины \((u,u')\) и \((v,v')\) смежны тогда и только тогда, когда либо \(u=v\) и \(u'\) смежна с \(v'\) в \(H\), либо \(u'=v'\) и \(u\) смежна с \(v\) в \(G\).
Источник определения: 2017\Декартовы умножения\EmelyanovDec.tex, Определение 2.1.
Декартово произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=2\)
\(K_2 \times K_2\)
Декартово произведение: таблица после примера 1/4
Таблица Кэли для \(K_2\times K_2\): квадрат, метки \(0,1,2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник: 2017\Декартовы умножения\EmelyanovDec.tex, строки 399-412.
Декартово произведение: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=2\)
\(K_2 \times K_3\)
Декартово произведение: таблица после примера 2/4
Таблица Кэли для \(K_2 \times K_3\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Декартово произведение: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат \(=3\)
\(K_2 \times C_4\)
Декартово произведение: таблица после примера 3/4
Таблица Кэли для \(K_2\times C_4\): ребро на четырехугольник
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник: 2017\Декартовы умножения\EmelyanovDec.tex, строки 416-432; сверка: Python script\graph\polygons_cally\2 угольник cartesian 4 угольник.html.
Декартово произведение: пример 4/4
Цикл длины 8 на цикл длины 9
Диаметры: \(C_8=4\), \(C_9=4\), результат \(=8\)
\(C_8 \times C_9\)
Декартово произведение: общая таблица
Общая таблица Кэли алгебры \(\mathfrak Q_n\)
| · | 0 | 1 | 2 | 3 | 4 | … | m | l |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | {…} | {m} | {l} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2,4} | {1,3,5} | {…} | {Nc(2m)} | {C(2l)} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | {…} | {C(2m)} | {Nc(2l)} |
|---|
| 3 | {3} | {0,2,4} | {1,3,5} | {0,2,4,6} | {Nc(2m)} | {…} | {Nc(2m)} | {C(2l)} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {Nc(2m)} | {C(2m)} | {…} | {C(2m)} | {Nc(2l)} |
|---|
| … | {…} | {…} | {…} | {…} | {…} | {…} | {Nc(2m)} | {C(2l)} |
|---|
| m | {m} | {Nc(2m)} | {C(2m)} | {Nc(2m)} | {C(2m)} | {Nc(2m)} | {C(2m)} | {Nc(2l)} |
|---|
| l | {l} | {C(2l)} | {Nc(2l)} | {C(2l)} | {Nc(2l)} | {C(2l)} | {Nc(2l)} | {C(2l)} |
|---|
\(m\) — четная метка, \(l\) — нечетная метка; \(C(x)\) — четные метки до \(x\), \(Nc(x)\) — нечетные метки до \(x\).
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 92-124.
Утверждение из статьи
Декартово произведение
\(G \times H\)
Алгебра: \(\mathfrak P_n\) строится из \(\mathfrak P_1\) и \(\mathfrak R\)
Утверждение 2.18. Алгебра, получаемая из \(n\) умножений алгебры \(\mathfrak P_1\) на \(\mathfrak R\), будет эквивалентна алгебре \(\mathfrak P_n\).
Пояснение. Определение 2.17 перед этим строит алгебру \(\mathfrak P_n\) для \(n\) умножений алгебры \(\mathfrak P_1\) на \(\mathfrak R\) и задает ее таблицей Кэли.
Источник: 2017\Декартовы умножения\EmelyanovDec1.tex, Определение 2.17 и Утверждение 2.18.
Определение произведения
Корневое произведение
\(G \mathbin{\circ_r} H\)
Определение. Корневое произведение \(G\circ H\) графа \(G\) и корневого графа \(H\): берутся \(|V(G)|\) непересекающихся копий \(H\), и для каждой вершины \(v_i\) графа \(G\) вершина \(v_i\) отождествляется с корнем \(i\)-й копии \(H\).
Источник определения: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, Definition.
Корневое произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=3\)
\(K_2 \circ_r K_2\)
Корневое произведение: таблица после примера 1/4
Таблица Кэли для \(H^2\): корневое произведение ребра
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, строки 111-133.
Корневое произведение: пример 2/4
Четырехугольник на ребро
Диаметры: \(C_4=2\), \(K_2=1\), результат \(=4\)
\(C_4 \circ_r K_2\)
Корневое произведение: таблица после примера 2/4
Таблица Кэли для \(C_4\circ H\): квадрат на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) | \(\{4\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2,4\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3\}\) |
|---|
| \(4\) | \(\{4\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, строки 173-198.
Корневое произведение: пример 3/4
Треугольник на ребро
Диаметры: \(K_3=1\), \(K_2=1\), результат \(=3\)
\(K_3 \circ_r K_2\)
Корневое произведение: таблица после примера 3/4
Таблица Кэли для \(K_3\circ H\): треугольник на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2,3\}\) | \(\{0,1,2,3\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2,3\}\) | \(\{0,1,2,3\}\) | \(\{0,1,2,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,1,2,3\}\) | \(\{0,1,2,3\}\) | \(\{0,1,2,3\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, строки 275-298.
Корневое произведение: пример 4/4
Цикл длины 5 на ребро
Диаметры: \(C_5=2\), \(K_2=1\), результат \(=4\)
\(C_5 \circ_r K_2\)
Корневое произведение: таблица после примера 4/4
Таблица Кэли для \(C_5\circ H\): пятиугольник на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) | \(\{4\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3,2\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3,2\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) |
|---|
| \(4\) | \(\{4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) | \(\{0,1,2,3,4\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, строки 384-410.
Корневое произведение: общая таблица
Общая таблица Кэли алгебры \(\mathfrak{H^k}\)
| · | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2,4} | {1,3,5} | … | Foe(n+1) |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | Foe(n+2) |
|---|
| 3 | {3} | {0,2,4} | {1,3,5} | {0,2,4,6} | Odd(n) | … | Foe(n+3) |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | Odd(n) | Ev(n) | … | Foe(n+4) |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | Foe(n+1) | Foe(n+2) | Foe(n+3) | Foe(n+4) | … | Ev(n) |
|---|
\(Ev(n)\) — четные числа до \(n\), \(Odd(n)\) — нечетные числа до \(n\); \(Foe(k)=Ev(n)\) при четном \(k\), иначе \(Odd(n)\).
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 388-418.
Корневое произведение: общая таблица
Общая таблица Кэли алгебры \(\mathfrak{AH^k}\)
| · | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2,4} | {1,3,5} | … | Fr(n+1) |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,1,2,3,
4,5,6} | … | Fr(n+1) |
|---|
| 3 | {3} | {0,2,4} | {1,3,5} | {0,1,2,3,
4,5,6} | {1,2,3,
4,5,6} | … | Fr(n+1) |
|---|
| 4 | {4} | {1,3,5} | {0,1,2,3,
4,5,6} | {1,2,3,
4,5,6} | {0,1,2,3,
4,5,6} | … | Fr(n+1) |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | Fr(n+1) | Fr(n+1) | Fr(n+1) | Fr(n+1) | … | {0,1,2,3,
4,…,n} |
|---|
\(Fr(k)=\{0,1,\ldots,k\}\) при четном \(k\); при нечетном \(k\): если \(k\ge m\), то \(\{0,1,\ldots,k\}\), если \(k
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 424-465.
Теорема
Корневое произведение
\(G \mathbin{\circ_r} H\)
Алгебра: \(\mathfrak{H^k}\) или \(\mathfrak{AH^k}\)
Теорема. Если \(T\) - теория корневого произведения графов на ребро, \(\mathfrak B\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak B\) задается ровно одной из следующих алгебр: \(\mathfrak{H^k}\) и \(\mathfrak{AH^k}\).
Пояснение. Классификация разделяет корневые произведения на две серии алгебр: \(\mathfrak{H^k}\) и \(\mathfrak{AH^k}\).
Источник теоремы: 2022\Тензорные произведения\Emelyanov_korn_EN_2.tex, Theorem thmain1.
Определение произведения
Лексикографическое произведение
\(G \cdot H\)
Определение. Лексикографическое произведение \(G\cdot H\) имеет множество вершин \(V(G)\times V(H)\). Вершины \((u,v)\) и \((x,y)\) смежны тогда и только тогда, когда либо \(u\) смежна с \(x\) в \(G\), либо \(u=x\) и \(v\) смежна с \(y\) в \(H\).
Источник определения: 2021\Мальцевские 2021 лексикографические произведения\ЕмельяновДЮ.tex.
Лексикографическое произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=1\)
\(K_2 \cdot K_2\)
Лексикографическое произведение: таблица после примера 1/4
Таблица Кэли для \(K_2 \cdot K_2\): результат диаметра \(1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Лексикографическое произведение: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=1\)
\(K_2 \cdot K_3\)
Лексикографическое произведение: таблица после примера 2/4
Таблица Кэли для \(K_2 \cdot K_3\): результат диаметра \(1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Лексикографическое произведение: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат \(=2\)
\(K_2 \cdot C_4\)
Лексикографическое произведение: таблица после примера 3/4
Таблица Кэли для \(K_2 \cdot C_4\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Лексикографическое произведение: пример 4/4
Цикл длины 6 на четырехугольник
Диаметры: \(C_6=3\), \(C_4=2\), результат \(=3\)
\(C_6 \cdot C_4\)
Лексикографическое произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak L_n\)
| · | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,1,2} | {0,1,2,3} | {0,1,2,3,4} | {0,1,2,3,
4,5} | … | {0,1,2,3,
…,n} |
|---|
| 2 | {2} | {0,1,2,3} | {0,1,2,3,4} | {0,1,2,3,
4,5} | {0,1,2,3,
4,5,6} | … | {0,1,2,3,
…,n} |
|---|
| 3 | {3} | {0,1,2,3,4} | {0,1,2,3,
4,5} | {0,1,2,3,
4,5,6} | {0,1,2,3,
4,5,6,7} | … | {0,1,2,3,
…,n} |
|---|
| 4 | {4} | {0,1,2,3,
4,5} | {0,1,2,3,
4,5,6} | {0,1,2,3,
4,5,6,7} | {0,1,2,3,4,
5,6,7,8} | … | {0,1,2,3,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,1,2,3,
…,n} | {0,1,2,3,
…,n} | {0,1,2,3,
…,n} | {0,1,2,3,
…,n} | … | {0,1,2,3,
…,n} |
|---|
Источник: 2021\Мальцевские 2021 лексикографические произведения\ЕмельяновДЮ.tex, строки 36-67; также ghtpf, строки 314-350.
Теорема
Лексикографическое произведение
\(G \cdot H\)
Алгебра: \(\mathfrak L_n\); при симплексном поглощении — алгебры симплексов \(\mathfrak S_d\)
Теорема. Алгебра \(\mathfrak L_n\) для лексикографического произведения графов диаметра \(n\) задается таблицей Кэли; в симплексных случаях эти алгебры поглощаются алгебрами симплексов.
Пояснение. Таблица \(\mathfrak L_n\) показывает, как при композиции меток возникают начальные интервалы меток.
Источник теоремы: 2021\Мальцевские 2021 лексикографические произведения\ЕмельяновДЮ.tex.
Определение произведения
Тензорное произведение
\(G \times H\)
Определение. Тензорное произведение \(G\times H\) имеет множество вершин \(V(G)\times V(H)\). Различные вершины \((u,u')\) и \((v,v')\) смежны тогда, когда \(u\) смежна с \(v\) и \(u'\) смежна с \(v'\).
Источник определения: 2022\Тензорные произведения\Emelyanov_tenz_130322.tex.
Тензорное произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат несвязен, max diam компоненты \(=1\)
\(K_2 \times K_2\)
Тензорное произведение: таблица после примера 1/4
Таблица Кэли для \(K_2\times K_2\): две копии ребра
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_eng_utf8.tex, строки 334-344.
Тензорное произведение: пример 2/4
Треугольник на ребро
Диаметры: \(K_3=1\), \(K_2=1\), результат \(=3\)
\(K_3 \times K_2\)
Тензорное произведение: таблица после примера 2/4
Таблица Кэли для \(K_3\times K_2\): треугольник на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_tenz_130322.tex, строки 161-178.
Тензорное произведение: пример 3/4
Четырехугольник на ребро
Диаметры: \(C_4=2\), \(K_2=1\), результат несвязен, max diam компоненты \(=2\)
\(C_4 \times K_2\)
Тензорное произведение: таблица после примера 3/4
Таблица Кэли для \(C_4\times K_2\): квадрат на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_tenz_130322.tex, строки 181-196.
Тензорное произведение: пример 4/4
Цикл длины 5 на ребро
Диаметры: \(C_5=2\), \(K_2=1\), результат \(=5\)
\(C_5 \times K_2\)
Тензорное произведение: таблица после примера 4/4
Таблица Кэли для \(C_5\times K_2\): пятиугольник на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) | \(\{4\}\) | \(\{5\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) |
|---|
| \(4\) | \(\{4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) |
|---|
| \(5\) | \(\{5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) | \(\{1,3,5\}\) | \(\{0,2,4\}\) |
|---|
Источник: 2022\Тензорные произведения\Emelyanov_tenz_130322.tex, строки 199-221.
Тензорное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{Tp_e}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {1,3,5,
…,n-1} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {0,2,4,
…,n} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {1,3,5,
…,n-1} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 183-222.
Тензорное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{Tp_o}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {0,2,4,
…,n} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {1,3,5,
…,n-1} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {1,3,5,
…,n-1} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 224-264.
Теорема
Тензорное произведение
\(G \times H\)
Алгебра: \(\mathfrak{Tp_e}\) или \(\mathfrak{Tp_o}\)
Теорема. Если \(T\) - теория тензорного произведения графа на ребро, \(\mathfrak B\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak B\) задается ровно одной из следующих алгебр: \(\mathfrak{Tp_e}\), \(\mathfrak{Tp_o}\).
Пояснение. Индексы \(e\) и \(o\) соответствуют четной и нечетной сериям таблиц для произведений многоугольников на ребро.
Источник теоремы: 2022\Тензорные произведения\Emelyanov_tenz_130322.tex, theorem.
Определение произведения
Сильное произведение
\(G \boxtimes H\)
Определение. Сильное произведение \(G\boxtimes H\) имеет множество вершин \(V(G)\times V(H)\). Различные вершины \((u,u')\) и \((v,v')\) смежны тогда и только тогда, когда \(u=v\) и \(u'\) смежна с \(v'\), либо \(u'=v'\) и \(u\) смежна с \(v\), либо смежность выполняется в обеих координатах.
Источник определения: 2023\Сильные произведения\Emelyanov_strong.tex, Definition.
Сильное произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=1\)
\(K_2 \boxtimes K_2\)
Сильное произведение: таблица после примера 1/4
Таблица Кэли для \(K_2\boxtimes K_2\): \(\mathfrak T_1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник: 2023\Сильные произведения\Emelyanov_strong.tex, строки 136-147.
Сильное произведение: пример 2/4
Треугольник на ребро
Диаметры: \(K_3=1\), \(K_2=1\), результат \(=1\)
\(K_3 \boxtimes K_2\)
Сильное произведение: таблица после примера 2/4
Таблица Кэли для \(K_3\boxtimes K_2\): \(\mathfrak T_1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник: 2023\Сильные произведения\Emelyanov_strong.tex, строки 136-147.
Сильное произведение: пример 3/4
Четырехугольник на ребро
Диаметры: \(C_4=2\), \(K_2=1\), результат \(=2\)
\(C_4 \boxtimes K_2\)
Сильное произведение: таблица после примера 3/4
Таблица Кэли для \(C_4\boxtimes K_2\): квадрат на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: 2023\Сильные произведения\Emelyanov_strong.tex, строки 158-170.
Сильное произведение: пример 4/4
Цикл длины 5 на ребро
Диаметры: \(C_5=2\), \(K_2=1\), результат \(=2\)
\(C_5 \boxtimes K_2\)
Сильное произведение: таблица после примера 4/4
Таблица Кэли для \(C_5\boxtimes K_2\): пятиугольник на ребро
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: 2023\Сильные произведения\Emelyanov_strong.tex, строки 174-187.
Сильное произведение: общая таблица
Таблица Кэли алгебры симплексов \(\mathfrak T_n\)
| · | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,1,2} | {0,1,2,3} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | … | {0,1,2,
…,n} |
|---|
| 2 | {2} | {0,1,2,3} | {0,1,2,3,4} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | … | {0,1,2,
…,n} |
|---|
| 3 | {3} | {0,1,2,3,4} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | … | {0,1,2,
…,n} |
|---|
| 4 | {4} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | {0,1,2,3,
4,…,n} | … | {0,1,2,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,1,2,
…,n} | {0,1,2,
…,n} | {0,1,2,
…,n} | {0,1,2,
…,n} | … | {0,1,2,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 133-163.
Теорема
Сильное произведение
\(G \boxtimes H\)
Алгебра: алгебры симплексов \(\mathfrak S_d\)
Теорема. Если сильное умножение алгебр бинарных изоляторов для \(n\)-угольников приводит хотя бы к одному симплексу, то алгебра результата изоморфна алгебре симплексов \(\mathfrak S_d\).
Пояснение. Поэтому в сильных произведениях малых графов таблицы быстро сводятся к симплексным алгебрам соответствующего диаметра.
Источник теоремы: 2023\Сильные произведения\Emelyanov_strong.tex, Theorem teor1.
Определение произведения
Сумма графов
\(G+H\)
Определение. Если \(V(G_1)\) и \(V(G_2)\) не пересекаются, то суммой \(G_1+G_2\) называется граф, полученный из их объединения добавлением ребер, соединяющих каждую вершину \(G_1\) с каждой вершиной \(G_2\).
Источник определения: 2022\МЧ2022 сумма графов\Емельянов.tex.
Сумма графов: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=1\)
\(K_2 + K_2\)
Сумма графов: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=1\)
\(K_2 + K_3\)
Сумма графов: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат \(=2\)
\(K_2 + C_4\)
Сумма графов: пример 4/4
Цикл длины 7 на цикл длины 9
Диаметры: \(C_7=3\), \(C_9=4\), результат \(=2\)
\(C_7 + C_9\)
Сумма графов: общая таблица
Таблица Кэли симплексного случая диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: 2022\МЧ2022 сумма графов\Емельянов.tex, строки 20-24; таблица \(\mathfrak T_2\): текущая статья article.tex, строки 217-229.
Теорема
Сумма графов
\(G+H\)
Алгебра: \(\mathfrak S\)
Теорема. Если \(T\) - теория суммы связных графов, \(\mathfrak B\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak B\) задается ровно одной алгеброй \(\mathfrak S\).
Пояснение. Добавление всех ребер между компонентами приводит к диаметру \(2\) и к появлению симплексного поведения.
Источник теоремы: 2022\МЧ2022 сумма графов\Емельянов.tex.
Определение произведения
Зиг-заг произведение
\(G \operatorname{zigzag} H\)
Определение. Зигзаг-произведение \(G\) и \(H\) заменяет каждую вершину графа \(G\) копией, то есть облаком, графа \(H\), и соединяет вершины малым шагом внутри облака, большим шагом между облаками и еще одним малым шагом внутри конечного облака.
Источник определения: 2023\МЧ зиг-заг произведение\EmelyanovDzigzag.tex.
Зиг-заг произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=2\)
\(K_2 \operatorname{zigzag} K_2\)
Зиг-заг произведение: таблица после примера 1/4
Таблица Кэли для \(K_2 \operatorname{zigzag} K_2\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Зиг-заг произведение: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=2\)
\(K_2 \operatorname{zigzag} K_3\)
Зиг-заг произведение: таблица после примера 2/4
Таблица Кэли для \(K_2 \operatorname{zigzag} K_3\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Зиг-заг произведение: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат \(=3\)
\(K_2 \operatorname{zigzag} C_4\)
Зиг-заг произведение: таблица после примера 3/4
Таблица Кэли для \(K_2 \operatorname{zigzag} C_4\): результат диаметра \(3\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Зиг-заг произведение: пример 4/4
Четырехугольник на цикл длины 9
Диаметры: \(C_4=2\), \(C_9=4\), результат \(=6\)
\(C_4 \operatorname{zigzag} C_9\)
Зиг-заг произведение: общая таблица
Общая таблица Кэли алгебры \(\mathfrak{Zig}_n\)
| · | 0 | 1 | 2 | 3 | 4 | … | m | l |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | {…} | {m} | {l} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2,4} | {1,3,5} | {…} | {Nc(m+1)} | {C(l+1)} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | {…} | {C(m+2)} | {Nc(l+2)} |
|---|
| 3 | {3} | {0,2,4} | {1,3,5} | {0,2,4,6} | {Nc(7)} | {…} | {Nc(m+3)} | {C(l+3)} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {Nc(7)} | {C(8)} | {…} | {C(m+4)} | {Nc(l+4)} |
|---|
| … | {…} | {…} | {…} | {…} | {…} | {…} | {…} | {…} |
|---|
| m | {m} | {Nc(m+1)} | {C(m+2)} | {Nc(m+3)} | {C(m+4)} | {…} | {C(2m)} | {Nc(m+l)} |
|---|
| l | {l} | {C(l+1)} | {Nc(l+2)} | {C(l+3)} | {Nc(l+4)} | {…} | {Nc(m+l)} | {C(2l)} |
|---|
\(m\) — четная метка, \(l\) — нечетная метка; \(C(x)\) — четные метки до \(x\), \(Nc(x)\) — нечетные метки до \(x\).
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 541-575.
Теорема
Зиг-заг произведение
\(G \operatorname{zigzag} H\)
Алгебра: \(\mathfrak{Zig}\)
Теорема. Если \(T\) - теория зигзаг-произведения правильного многогранника на ребро, \(\mathfrak B\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak B\) задается алгеброй \(\mathfrak{Zig}\).
Пояснение. Трехшаговое правило \(zig\)-\(zag\)-\(zig\) дает единую таблицу для рассматриваемого класса произведений.
Источник теоремы: 2023\МЧ зиг-заг произведение\EmelyanovDzigzag.tex.
Определение произведения
Гомоморфное произведение
\(G \times_f H\)
Определение. Для графов \(G_1=(V_1,E_1)\), \(G_2=(V_2,E_2)\) и гомоморфизма \(f:V_1\to V_2\) гомоморфное произведение имеет вершины \((v,u)\), где \(v\in V_1\), \(u\in V_2\). Ребра задаются объединением двух типов: ребра, пришедшие из \(E_1\) при условии \(f(v_1)=f(v_2)\), и ребра внутри слоя, задаваемые образом \(f(v)\).
Источник определения: 2024\Гомоморфное произведение\Emelyanov_homomorphism.tex, Definition.
Гомоморфное произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат \(=2\)
\(K_2 \times_f K_2\)
Гомоморфное произведение: таблица после примера 1/4
Таблица Кэли для \(K_2 \times_f K_2\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Гомоморфное произведение: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=2\)
\(K_2 \times_f K_3\)
Гомоморфное произведение: таблица после примера 2/4
Таблица Кэли для \(K_2 \times_f K_3\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Гомоморфное произведение: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат \(=3\)
\(K_2 \times_f C_4\)
Гомоморфное произведение: таблица после примера 3/4
Таблица Кэли для \(K_2 \times_f C_4\): результат диаметра \(3\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Гомоморфное произведение: пример 4/4
Цикл длины 6 на цикл длины 5
Диаметры: \(C_6=3\), \(C_5=2\), результат \(=5\)
\(C_6 \times_f C_5\)
Гомоморфное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{Hp_e}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {1,3,5,
…,n-1} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {0,2,4,
…,n} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {1,3,5,
…,n-1} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 611-650.
Гомоморфное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{Hp_o}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {0,2,4,
…,n} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {1,3,5,
…,n-1} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {1,3,5,
…,n-1} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 652-690.
Теорема
Гомоморфное произведение
\(G \times_f H\)
Алгебра: \(\mathfrak{Hp_e}\) или \(\mathfrak{Hp_o}\)
Теорема. Если \(T\) - теория гомоморфного произведения ребра на граф, а \(\mathfrak B\) - алгебра бинарных изолирующих формул \(T\), то алгебра \(\mathfrak B\) определяется одним из двух вариантов: \(\mathfrak{Hp_e}\) или \(\mathfrak{Hp_o}\).
Пояснение. Как и в тензорном случае, классификация разделяется на четную и нечетную серии.
Источник теоремы: 2024\Гомоморфное произведение\Emelyanov_homomorphism.tex, Theorem teor1.
Определение произведения
Произведение Кронекера
\(G \otimes H\)
Определение. Произведение Кронекера \(G_1\otimes G_2\) определяется как граф с множеством вершин \(V_1\times V_2\); ребро между \((u_1,v_1)\) и \((u_2,v_2)\) проводится тогда и только тогда, когда \((u_1,u_2)\in E_1\) и \((v_1,v_2)\in E_2\).
Источник определения: 2025\Алмата произведение Кронекера\Emelyanov_kronecker_product.tex.
Произведение Кронекера: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат несвязен, max diam компоненты \(=1\)
\(K_2 \otimes K_2\)
Произведение Кронекера: таблица после примера 1/4
Таблица Кэли для \(K_2 \otimes K_2\): результат диаметра \(1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Произведение Кронекера: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=3\)
\(K_2 \otimes K_3\)
Произведение Кронекера: таблица после примера 2/4
Таблица Кэли для \(K_2 \otimes K_3\): результат диаметра \(3\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Произведение Кронекера: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат несвязен, max diam компоненты \(=2\)
\(K_2 \otimes C_4\)
Произведение Кронекера: таблица после примера 3/4
Таблица Кэли для \(K_2 \otimes C_4\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Произведение Кронекера: пример 4/4
Цикл длины 8 на четырехугольник
Диаметры: \(C_8=4\), \(C_4=2\), результат несвязен, max diam компоненты \(=4\)
\(C_8 \otimes C_4\)
Произведение Кронекера: общая таблица
Таблица Кэли алгебры \(\mathfrak{Kr_e}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {1,3,5,
…,n-1} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {0,2,4,
…,n} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {1,3,5,
…,n-1} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Алмата произведение Кронекера\Emelyanov_kronecker_product.tex, строки 83-108.
Произведение Кронекера: общая таблица
Таблица Кэли алгебры \(\mathfrak{Kr_o}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {0,2,4,
…,n} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {1,3,5,
…,n-1} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {1,3,5,
…,n-1} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Алмата произведение Кронекера\Emelyanov_kronecker_product.tex, строки 55-80.
Теорема
Произведение Кронекера
\(G \otimes H\)
Алгебра: \(\mathfrak{Kr_o}\) или \(\mathfrak{Kr_e}\)
Теорема. Если \(T\) - теория для произведений Кронекера для графов, \(\mathfrak M\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak M\) изоморфна алгебре \(\mathfrak{Kr_o}\) или \(\mathfrak{Kr_e}\).
Пояснение. Две алгебры соответствуют нечетной и четной сериям таблиц Кэли.
Источник теоремы: 2025\Алмата произведение Кронекера\Emelyanov_kronecker_product.tex.
Определение произведения
Модулярное произведение
\(G \nabla H\)
Определение. Модулярным произведением \(G\nabla H\) называется граф с множеством вершин \(V(G)\times V(H)\), в котором две различные вершины \((u,v)\) и \((x,y)\) смежны тогда и только тогда, когда \(u\ne x\), \(v\ne y\) и \((u\sim_G x)\Longleftrightarrow(v\sim_H y)\).
Источник определения: 2026\Группы автоморфизмов модулярных произведений циклов...\article.tex.
Модулярное произведение: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат несвязен, max diam компоненты \(=1\)
\(K_2 \nabla K_2\)
Модулярное произведение: таблица после примера 1/4
Таблица Кэли для \(K_2 \nabla K_2\): результат диаметра \(1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=3\)
\(K_2 \nabla K_3\)
Модулярное произведение: таблица после примера 2/4
Таблица Кэли для \(K_2 \nabla K_3\): результат диаметра \(3\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат несвязен, max diam компоненты \(=2\)
\(K_2 \nabla C_4\)
Модулярное произведение: таблица после примера 3/4
Таблица Кэли для \(K_2 \nabla C_4\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение: пример 4/4
Цикл длины 8 на цикл длины 10
Диаметры: \(C_8=4\), \(C_10=5\), результат \(=2\)
\(C_8 \nabla C_10\)
Модулярное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{M_e}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {1,3,5,
…,n-1} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {0,2,4,
…,n} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {1,3,5,
…,n-1} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 741-780.
Модулярное произведение: общая таблица
Таблица Кэли алгебры \(\mathfrak{M_o}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {0,2,4,
…,n} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {1,3,5,
…,n-1} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {1,3,5,
…,n-1} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 782-820.
Теорема
Модулярное произведение
\(G \nabla H\)
Алгебра: \(\mathfrak{M_o}\) или \(\mathfrak{M_e}\)
Теорема. Если \(T\) - теория модулярного произведения графов, \(\mathfrak M\) - алгебра бинарных изолирующих формул теории \(T\), то алгебра \(\mathfrak M\) изоморфна алгебре \(\mathfrak{M_o}\) или \(\mathfrak{M_e}\).
Пояснение. Модулярное произведение дает две серии алгебр, различающиеся четностью параметра.
Источник теоремы: 2025\Алмата Модулярное произведение\Emelyanov_modular_product.tex.
Определение произведения
Модулярное произведение и автоморфизмы циклов
\(D_m\times D_n,\quad C_m\nabla C_n\)
Определение. Для модулярного произведения циклов \(C_m\nabla C_n\) используется то же определение \(G\nabla H\); далее рассматривается действие \(D_m\times D_n\) на вершинах и орбиты на парах вершин, параметризуемые циклическими расстояниями.
Источник определения: 2026\Группы автоморфизмов модулярных произведений циклов...\article.tex.
Модулярное произведение и автоморфизмы циклов: пример 1/4
Ребро на ребро
Диаметры: \(K_2=1\), \(K_2=1\), результат несвязен, max diam компоненты \(=1\)
\(K_2 \nabla K_2\)
Модулярное произведение и автоморфизмы циклов: таблица после примера 1/4
Таблица Кэли для \(K_2 \nabla K_2\): результат диаметра \(1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение и автоморфизмы циклов: пример 2/4
Ребро на треугольник
Диаметры: \(K_2=1\), \(K_3=1\), результат \(=3\)
\(K_2 \nabla K_3\)
Модулярное произведение и автоморфизмы циклов: таблица после примера 2/4
Таблица Кэли для \(K_2 \nabla K_3\): результат диаметра \(3\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) | \(\{3\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1,3\}\) | \(\{0,2\}\) | \(\{1,3\}\) |
|---|
| \(3\) | \(\{3\}\) | \(\{0,2\}\) | \(\{1,3\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение и автоморфизмы циклов: пример 3/4
Ребро на четырехугольник
Диаметры: \(K_2=1\), \(C_4=2\), результат несвязен, max diam компоненты \(=2\)
\(K_2 \nabla C_4\)
Модулярное произведение и автоморфизмы циклов: таблица после примера 3/4
Таблица Кэли для \(K_2 \nabla C_4\): результат диаметра \(2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,2\}\) | \(\{1\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{1\}\) | \(\{0,2\}\) |
|---|
Источник таблицы: алгоритм \(\texttt{correct\_cayley\_table}\) из tab_Kely.py; произведение построено по определению на слайде.
Модулярное произведение и автоморфизмы циклов: пример 4/4
Цикл длины 9 на цикл длины 5
Диаметры: \(C_9=4\), \(C_5=2\), результат \(=2\)
\(C_9 \nabla C_5\)
Модулярное произведение и автоморфизмы циклов: общая таблица
Таблица Кэли алгебры \(\mathfrak{M_e}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {1,3,5,
…,n-1} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {0,2,4,
…,n} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {1,3,5,
…,n-1} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 741-780.
Модулярное произведение и автоморфизмы циклов: общая таблица
Таблица Кэли алгебры \(\mathfrak{M_o}\)
| * | 0 | 1 | 2 | 3 | 4 | … | n |
|---|
| 0 | {0} | {1} | {2} | {3} | {4} | … | {n} |
|---|
| 1 | {1} | {0,2} | {1,3} | {0,2} | {1,3,5} | … | {0,2,4,
…,n} |
|---|
| 2 | {2} | {1,3} | {0,2,4} | {1,3,5} | {0,2,4,6} | … | {1,3,5,
…,n-1} |
|---|
| 3 | {3} | {0,2} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
| 4 | {4} | {1,3,5} | {0,2,4,6} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | … | {1,3,5,
…,n-1} |
|---|
| … | … | … | … | … | … | … | … |
|---|
| n | {n} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | {0,2,4,
…,n} | {1,3,5,
…,n-1} | … | {0,2,4,
…,n} |
|---|
Источник: 2025\Эрлагол Звезды тензорные декартовы\ghtpf\graph_product.tex, строки 782-820.
Теорема
Модулярное произведение и автоморфизмы циклов
\(D_m\times D_n,\quad C_m\nabla C_n\)
Алгебра: орбитные метки \(O_{a,b}\); для алгебр модулярного произведения — \(\mathfrak{M_o}\), \(\mathfrak{M_e}\)
Теорема. Орбиты действия группы \(D_m\times D_n\) на упорядоченных парах вершин графа \(C_m\nabla C_n\) в точности совпадают с множествами \(O_{a,b}\), где \(0\leq a\leq\lfloor m/2\rfloor\), \(0\leq b\leq\lfloor n/2\rfloor\).
Пояснение. Эта теорема связывает модулярное произведение циклов с метками бинарных формул через орбиты пар вершин.
Источник теоремы: 2026\Группы автоморфизмов модулярных произведений циклов...\article.tex.
Определение произведения
Ко-нормальное / дизъюнктивное произведение
\(G \vee H\)
Определение. Ко-нормальным, или дизъюнктивным, произведением графов \(G\) и \(H\) называется граф \(G\vee H\) с множеством вершин \(V(G)\times V(H)\); различные вершины \((g,h)\) и \((g',h')\) смежны тогда и только тогда, когда \(gg'\in E(G)\) или \(hh'\in E(H)\).
Источник определения: текущая статья article.tex, Определение ко-нормального произведения.
Ко-нормальное / дизъюнктивное произведение: пример 1/7
Цикл длины 2 на цикл длины 2
Диаметры: \(C_2=1\), \(C_2=1\), результат \(=1\)
\(C_2 \vee C_2\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 1/7
Таблица \(T_1\) для ко-нормального произведения \(C_2\vee C_2\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник: текущая статья article.tex, строки 204-214; граничный полный случай: article.tex, строка 315.
Ко-нормальное / дизъюнктивное произведение: пример 2/7
Цикл длины 2 на треугольник
Диаметры: \(C_2=1\), \(C_3=1\), результат \(=1\)
\(C_2 \vee C_3\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 2/7
Таблица \(T_1\) для ко-нормального произведения \(C_2\vee C_3\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник: текущая статья article.tex, строки 204-214; граничный полный случай: article.tex, строка 315.
Ко-нормальное / дизъюнктивное произведение: пример 3/7
Цикл длины 2 на четырехугольник
Диаметры: \(C_2=1\), \(C_4=2\), результат \(=2\)
\(C_2 \vee C_4\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 3/7
Таблица \(T_2\) для ко-нормального произведения \(C_2\vee C_4\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: текущая статья article.tex, строки 217-229; для полного графа на неполный цикл: article.tex, строка 319.
Ко-нормальное / дизъюнктивное произведение: пример 4/7
Треугольник на треугольник
Диаметры: \(K_3=1\), \(K_3=1\), результат \(=1\)
\(K_3 \vee K_3\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 4/7
Таблица \(T_1\) для ко-нормального произведения \(K_3\vee K_3\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
Источник: текущая статья article.tex, строки 204-214; граничный полный случай: article.tex, строка 315.
Ко-нормальное / дизъюнктивное произведение: пример 5/7
Треугольник на четырехугольник
Диаметры: \(C_3=1\), \(C_4=2\), результат \(=2\)
\(C_3 \vee C_4\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 5/7
Таблица \(T_2\) для ко-нормального произведения \(C_3\vee C_4\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: текущая статья article.tex, строки 217-229; для полного графа на неполный цикл: article.tex, строка 319.
Ко-нормальное / дизъюнктивное произведение: пример 6/7
Четырехугольник на цикл длины 5
Диаметры: \(C_4=2\), \(C_5=2\), результат \(=2\)
\(C_4 \vee C_5\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 6/7
Таблица \(T_2\) для ко-нормального произведения \(C_4\vee C_5\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: текущая статья article.tex, строки 217-229; для полного графа на неполный цикл: article.tex, строка 319.
Ко-нормальное / дизъюнктивное произведение: пример 7/7
Цикл длины 7 на цикл длины 9
Диаметры: \(C_7=3\), \(C_9=4\), результат \(=2\)
\(C_7 \vee C_9\)
Ко-нормальное / дизъюнктивное произведение: таблица после примера 7/7
Таблица \(T_2\) для ко-нормального произведения \(C_7\vee C_9\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: текущая статья article.tex, строки 217-229; для полного графа на неполный цикл: article.tex, строка 319.
Ко-нормальное произведение: леммы из статьи
Ко-нормальное / дизъюнктивное произведение
Лемма о диаметре. Если \(G\) и \(H\) не имеют изолированных вершин, то диаметр \(G\vee H\) не превосходит \(2\).
Следствие. В этом случае алгебра \(\mathfrak B(G\vee H)\) имеет не более трех основных меток: \(\rho_{\nu(p)}\subseteq\{0,1,2\}\).
Смысл для бинарных формул. Композиционная таблица сразу сжимается к меткам расстояний \(0,1,2\); дальние расстояния в ко-нормальном произведении без изолированных вершин не появляются.
Источник: article.tex, лемма о диаметре и следствие из раздела «Предварительные сведения».
Ко-нормальное произведение: примеры из статьи
Одна таблица для разных графов
| Произведение | Условие | Диаметр | Алгебра |
|---|
| \(K_m\vee K_n\) | \(m,n\ge2\) | 1 | \(\mathfrak T_1\) |
| \(C_m\vee C_n\) | \((m,n)\ne(3,3)\) | 2 | \(\mathfrak T_2\) |
| \(P_m\vee P_n\) | \(m,n\ge3\) | 2 | \(\mathfrak T_2\) |
| \(K_{1,m}\vee K_{1,n}\) | \(m,n\ge2\) | 2 | \(\mathfrak T_2\) |
| \(K_m\vee C_n\) | \(m\ge2,\ n\ge4\) | 2 | \(\mathfrak T_2\) |
| \(K_{r,s}\vee C_n\) | \(r,s\ge1,\ n\ge3\) | 2 | \(\mathfrak T_2\) |
Обозначения. \(K_n\) - полный граф, \(C_n\) - цикл, \(P_n\) - путь, \(K_{1,n}\) - звезда, \(K_{r,s}\) - полный двудольный граф. Во всех неполных строках без изолированных вершин ко-нормальное произведение имеет диаметр \(2\) и содержит треугольник.
Источник: презентация\presentation.tex и article.tex, таблица примеров ко-нормальных произведений.
Ко-нормальное произведение: пути
\(P_m\vee P_n\): неполный случай без изолированных вершин
Пример. Для \(m,n\ge3\) пути \(P_m\) и \(P_n\) имеют ребра, не имеют изолированных вершин и не являются полными графами.
\(P_4\vee P_3\)
Вывод. Поэтому \(\mathfrak B(P_m\vee P_n)\cong\mathfrak T_2\).
Ко-нормальное произведение: звезды
\(K_{1,m}\vee K_{1,n}\): центр дает ребра, листья дают неполноту
Пример. В звезде центр смежен со всеми листьями, но листья попарно не смежны. При \(m,n\ge2\) оба сомножителя неполны и без изолированных вершин.
\(K_{1,5}\vee K_{1,4}\)
Вывод. В произведении возникает \(K_3\), диаметр равен \(2\), значит \(\mathfrak B(K_{1,m}\vee K_{1,n})\cong\mathfrak T_2\).
Ко-нормальное произведение: полный граф и цикл
\(K_m\vee C_n\): полный сомножитель не всегда делает произведение полным
Разделение. Если \(n=3\), то \(C_3=K_3\), оба сомножителя полны и получается \(\mathfrak T_1\). Если \(n\ge4\), то \(C_n\) не является полным графом: в нем есть несмежные вершины.
\(K_4\vee C_5\)
Вывод. Для \(m\ge2,\ n\ge4\): \(\mathfrak B(K_m\vee C_n)\cong\mathfrak T_2\).
Ко-нормальное произведение: двудольный граф и цикл
\(K_{r,s}\vee C_n\): еще один источник \(\mathfrak T_2\)
Пример. У \(K_{r,s}\) есть ребра, а при типичных параметрах он неполон; у \(C_n\), \(n\ge3\), нет изолированных вершин.
\(K_{3,2}\vee C_5\)
Вывод. Дизъюнктивная смежность снова дает диаметр \(2\), треугольник и алгебру \(\mathfrak T_2\).
Ко-нормальное произведение: критерий полноты
Ко-нормальное / дизъюнктивное произведение
Предложение. Для любых простых графов \(G\) и \(H\) произведение \(G\vee H\) является полным графом тогда и только тогда, когда оба графа \(G\) и \(H\) являются полными.
Разделение случаев. Полный случай дает диаметр \(1\) и алгебру \(\mathfrak T_1\). Если хотя бы один сомножитель неполон, то при отсутствии изолированных вершин неполное произведение имеет диаметр \(2\).
Источник: article.tex, предложение о полноте ко-нормального произведения.
Ко-нормальное произведение: симплекс
Почему появляется \(\mathfrak T_2\)
Лемма о треугольнике. Если графы \(G\) и \(H\) содержат хотя бы по одному ребру, то \(G\vee H\) содержит треугольник \(K_3\).
Следствие для циклов. Для любых \(m,n\geq3\) произведение правильных многоугольников \(C_m\vee C_n\) содержит треугольник.
Модельно-теоретический ход. Наличие симплекса вместе с диаметром \(2\) переводит алгебру бинарных формул в алгебру симплексов \(\mathfrak T_2\).
Источник: article.tex, раздел «Ко-нормальные произведения и алгебры симплексов».
Ко-нормальное произведение: общий результат
Классификация без изолированных вершин
Теорема. Пусть \(G\) и \(H\) - конечные простые графы без изолированных вершин, и пусть каждый из них содержит хотя бы одно ребро. Если \(G\) и \(H\) полны, то \(\mathfrak B(G\vee H)\cong\mathfrak T_1\); если хотя бы один из них неполон, то \(\mathfrak B(G\vee H)\cong\mathfrak T_2\).
Примеры из статьи. \(K_m\vee K_n\) дает \(\mathfrak T_1\), а \(C_m\vee C_n\), \(P_m\vee P_n\), \(K_{1,m}\vee K_{1,n}\), \(K_m\vee C_n\) при неполном втором сомножителе дают \(\mathfrak T_2\).
Источник: article.tex, подраздел «Основной результат» и таблица примеров.
Ко-нормальное произведение: граница результата
Изолированные вершины требуют отдельной классификации
Ограничение. Если один из сомножителей имеет изолированную вершину, доказательство диаметра \(2\) уже не работает: появляются слои, где смежность определяется только другой координатой.
Пример. Для пустого графа \(E_m\) в произведении \(E_m\vee H\) смежность задается только второй координатой; если \(H\) несвязен, произведение тоже может быть несвязным.
Вывод. В этой зоне важны компоненты связности и расположение изолированных вершин, поэтому основной классификационный результат статьи формулируется без изолированных вершин.
Источник: article.tex, подраздел «Изолированные вершины».
Ко-нормальное / дизъюнктивное произведение: общая таблица
Таблицы \(\mathfrak T_1\) и \(\mathfrak T_2\) для ко-нормального произведения
\(\mathfrak T_1\)
| \(\cdot\) | \(0\) | \(1\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1\}\) |
|---|
\(\mathfrak T_2\)
| \(\cdot\) | \(0\) | \(1\) | \(2\) |
|---|
| \(0\) | \(\{0\}\) | \(\{1\}\) | \(\{2\}\) |
|---|
| \(1\) | \(\{1\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
| \(2\) | \(\{2\}\) | \(\{0,1,2\}\) | \(\{0,1,2\}\) |
|---|
Источник: текущая статья article.tex, строки 204-229.
Обобщающий вывод
Алгебры бинарных формул как инварианты
Мы рассматриваем алгебры бинарных изолирующих формул как производные модельно-теоретические инварианты полной теории. Они кодируют бинарные формульные связи между реализациями типов; в графовых теориях эти связи получают геометрическую интерпретацию через расстояния, орбиты автоморфизмов, симплексы, диаметр и тип произведения.
Смысл инварианта. Алгебра бинарных формул находится между синтаксисом и геометрией: она возникает из композиций главных формул, но ведет себя как конечная реляционная мультиалгебра, отражающая структуру бинарных связей.
Обобщающий вывод
Устойчивые семейства и дефинируемая геометрия
Устойчивые семейства
Мы видим не хаотический набор алгебр, а устойчивые серии: декартовы произведения сохраняют дистанционную структуру, тензорные, кронекеровы и модулярные произведения дают четно-нечетные пары, а сильные, лексикографические, корневые и ко-нормальные произведения часто переходят к симплексным алгебрам.
Дефинируемая геометрия
Свойства графа переходят в свойства алгебры не буквально, а через дефинируемую бинарную геометрию: диаметр ограничивает число меток, автоморфизмы задают орбитальные классы, а полный подграф и малый диаметр запускают симплексное поглощение.
Итоговая формулировка
Классификация через алгебры меток
Мы получаем аппарат для описания свойств алгебраических систем, графов и операций над ними через конечные алгебры меток. Для широких классов графовых произведений эти алгебры определяются комбинаторными параметрами: диаметром, расстояниями, орбитами автоморфизмов, наличием симплексов и правилом произведения.
Главный вывод. Алгебра бинарных формул является сильным, но не полным инвариантом: существенно различные графы и произведения могут иметь одну и ту же алгебру. Поэтому мы не восстанавливаем исходную структуру только по этой алгебре, а классифицируем ее дефинируемую бинарную геометрию.
Смысл программы. Алгебры бинарных формул находятся между синтаксисом и геометрией: они возникают из композиций главных формул, но ведут себя как конечные реляционные мультиалгебры, отражающие расстояния, симметрии и локальную связность графов.
