Глава 2. Теория графов — связность, циклы, кривизна

Где стоит глава

Граф — простейшая реляционная система: конечный список вершин и конечный список рёбер. Ничего сверх этого; «множество вершин» и «множество рёбер» — режимы рассмотрения двух списков. После счёта (Глава 1) графы добавляют к конечным структурам отношение — и почти все базовые вопросы, которые мы здесь рассматриваем, остаются в конечной списочной модели на Element-стороне: связность и ацикличность разрешаются завершающимся поиском, а лапласиан графа считается над ℚ точно (его спектральные инварианты — числовая тень структуры).

Граф есть пара конечных списков; связность и циклы — завершающиеся процессы (поиск с ограничением по топливу), а не свойства завершённого объекта.

Глава ведёт от структуры (вершины/рёбра) к связности и циклам, затем к графовому лапласиану и спектру, и закрывается мостами: к дискретной кривизне (Часть XII) и к физическому субстрату Тома III — решёточной теории поля, тензорным и спиновым сетям.

Граф как конечная структура

Граф строится из пустого добавлением вершин и рёбер; принадлежность вершины и наличие ребра — разрешимые предикаты (булевы функции), а степень вершины и список соседей — вычислимые из списка рёбер¹. Мы не начинаем с абстрактного множества вершин — работаем со списочной реализацией: есть конкретная пара списков, и все вопросы о ней решаются конечным перебором этих списков. Это Element-структура по самому построению.

Связность и ацикличность — завершающиеся процессы

Главные вопросы о графе — достижима ли одна вершина из другой и есть ли цикл — решаются поиском в глубину. И ключевой P4-пункт: этот поиск завершается, потому что граф конечен, и глубину поиска ограничивает само число вершин².

Ограничение по топливу — это и есть финитизация: поиск по конечному графу обязан остановиться, и достижимость становится Element-предикатом.

Сравнение с границей финитизации прямое. Достижимость в конечном графе — завершающийся процесс (Element). Достижимость в бесконечном графе — уже сторона предела-роли: поиск может не завершиться, и «достижимо ли» становится вопросом о завершённом бесконечном объекте. Дискретность держит нас на конечной стороне ровно потому, что топливо конечно.

Лапласиан и спектр

{ Структуру графа удобно собрать в один оператор — графовый лапласиан $L=D-A$ (степени минус смежность). Он считается над ℚ точно, и его строки суммируются в нуль — структурный закон сохранения, прямое свойство определения³.}

Спектр лапласиана — мост от структуры к числу: его собственные значения (в общем алгебраические, не обязательно рациональные) кодируют связность (наименьшее ненулевое — алгебраическая связность), а спектральная энтропия измеряет «разброс» структуры⁴. И тот же лапласиан связывает граф с физикой: спектральная щель играет роль массовой щели — прямой мост к Тому III⁵. Всё это — точная ℚ-арифметика на конечной матрице: Element-сторона.

Дискретная кривизна и физический субстрат

Граф — не только комбинаторный объект, но и дискретное пространство. На нём определяется дискретная кривизна (мост к геометрии Части XII: многообразие как процесс склейки локальных карт — а его дискретная модель есть граф-решётка), и он служит субстратом физических теорий Тома III: решёточная калибровочная теория живёт на графе-решётке, тензорные и спиновые сети суть графы с данными на рёбрах⁶.

Существенно для онтологии: всюду здесь пространство дискретно и конечно на каждой стадии — непрерывное многообразие появляется лишь как предел-процесс измельчения решётки (Часть XII), а не как исходный завершённый объект. В геометрическом чтении граф-решётка — Element-субстрат, а континуальное пространство возникает как предел-процесс измельчения.

E/R/R-разбор: граф как система

Разберём граф по E/R/R в порождающем порядке Rules $\to$ Roles $\to$ Elements.

Rules (L5). Удерживающее правило — отношение смежности: какие вершины соединены ребром. Из него правилами выводятся степень, соседство, достижимость (правило поиска с ограничением по топливу) и лапласиан $L=D-A$. Правило отношения стоит выше отдельных вершин и организует их в структуру.

Roles (L4). Вершина и ребро суть элементы списочного носителя, но их графовый смысл — роль внутри отношения смежности; связность/достижимость — статус пары вершин, вычисляемый правилом поиска; лапласиан — роль структуры-как-оператора, переводящая граф в спектр. «Множество вершин» — режим рассмотрения списка (операциональная делимость).

Elements (L1 + P4). Носители — конечные списки вершин и рёбер и рациональные элементы лапласиановой матрицы. Под P4 актуальна конечная структура; бесконечный граф и континуальный предел решётки — предел-роль, не завершённые объекты.

Проверка сформированности. Отношение смежности и правило поиска — Rules; вершина/ребро/связность/лапласиан — Roles; конечные списки и ℚ-матрица — Elements; пересечений нет. Самоприменения нет: отношение стоит над вершинами, не есть вершина.

Что даёт разбор. Он показывает, что граф — чистейшая Element-система: конечные носители, разрешимые предикаты, лапласиан точен над ℚ (спектр — его числовая тень); и что его выход к континууму (дискретная кривизна $\to$ гладкое многообразие, решётка $\to$ поле) — это переход к пределу-роли, тот же, что несёт весь том. Граф — то место, где дискретная математика встречается с физикой, оставаясь на конечной стороне.

Структура и её спектр построены; в следующей главе на конечные носители ложится мера — мы переходим к вероятности как операциональной теории над конечными пространствами, без меры Лебега и без аксиомы выбора.

---

---

Часть: Часть XVII. Дискретная математика, вероятность, информация · Том: «Математика»

Навигация: ← Глава 1. Комбинаторика — процессный счёт · Глава 3. Вероятность как операциональная теория →

Footnotes

1. Graph как пара списков mkGraph; has_node, has_edge (булевы, разрешимы), neighbors, out_degree, well_formed. Машинно проверено, 0 аксиом. ↩

2. is_reachable и is_acyclic_bool — булевы функции, вычисляемые поиском с ограничением по топливу (топливо $=$ число вершин). Машинно проверено, 0 аксиом. ↩

3. graph_laplacian $=$ path_degree $-$ path_adj ($D-A$); леммы L_row_sum_*: каждая строка лапласиана суммируется в $0$. Машинно проверено, 0 аксиом. ↩

4. Спектральная энтропия графа и графовый пропагатор формализованы отдельными кластерами (graph/SpectralEntropy, graph/GraphPropagator); машинно проверено, 0 аксиом. ↩

5. laplacian_mass_gap_connection: спектральная щель лапласиана как дискретный аналог массовой щели. Машинно проверено, 0 аксиом. ↩

6. Граф-зоопарк и графово-физический синтез (graph/GraphZoo, graph/GraphPhysicsSynthesis, модель Андерсона) собирают эти мосты; машинно проверено, 0 аксиом. ↩