Информатика · объяснение и практика

Сколько разных остовов соединяет граф: определитель вместо выбора одного дерева

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

Остовное дерево использует все вершины и часть исходных рёбер, соединяя вершины без циклов. Теорема Кирхгофа превращает количество таких наборов в определитель: из лапласиана удаляют одну строку и одноимённый столбец.

Метод и постановка

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

Постройте лапласиан. На диагональ поставьте степени вершин, за каждое ребро вне диагонали поставьте минус единицу. Сумма каждой строки должна стать нулём. Определитель всего лапласиана поэтому равен нулю и нужного количества не даёт. Удаление одной строки и того же столбца устраняет эту зависимость. Выбранная вершина не исчезает из исходной задачи: это только способ получить вычисляемый кофактор.

Проверка и границы вывода

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

Ошибка постановки — называть найденное число минимальной стоимостью. Здесь рёбра не имеют весов, и алгоритм считает все остовы. Если позже добавить стоимости, обычный невзвешенный лапласиан по-прежнему считает количество, а не оптимизирует сумму. Для одной вершины принято одно пустое дерево. Это согласуется с определителем пустого кофактора и отличает допустимую одноточечную сеть от несвязной сети из нескольких вершин.

Пример

У треугольника степени равны двум. После удаления третьей строки и столбца остаётся матрица [[2,−1],[−1,2]]. Её определитель равен 4−1=3.

Независимый перебор подтверждает три дерева: из трёх рёбер нужно убрать ровно одно, и каждый такой выбор сохраняет связность. Для пути на трёх вершинах выбора уже нет: оба ребра обязательны.

От чтения к действию

А теперь — вы

Полный лапласиан треугольника имеет нулевой определитель. Сколько у него остовных деревьев?

Частые вопросы

Это минимальное по весу дерево?

Нет. Весов во входе нет; считается количество всех остовов, а не стоимость одного.

Что для несвязного графа?

Остова на всех вершинах нет, поэтому число равно нулю. Для одной вершины принято одно пустое дерево.

Углублённый разбор

Взвешенная матричная теорема об остовах

Взвешенный лапласиан суммирует произведения весов по всем остовам. Этот объект можно использовать как нормирующую константу распределения, но нельзя подменять им минимальную стоимость дерева или обычное число остовов.

Перед началом: Лапласиан; Вес как произведение факторов.

Сначала определите смысл веса дерева

Пусть каждому ребру e сопоставлен неотрицательный вес w_e. Вес остова T определим произведением∏ₑ∈T w_e, а общий перечислитель Z — суммой этих произведений по всем остовам. При единичных весах Z становится обычным количеством. При иных весах он учитывает относительные множители выбора, а не сумму цен вдоль дерева.

Взвешенный лапласиан имеет внедиагональные элементы−Σw_e по всем рёбрам между двумя вершинами и диагональные суммы инцидентных весов. Любой главный кофактор равен Z по взвешенной матричной теореме. Для параллельных рёбер веса суммируются в матрице, но при комбинаторной проверке эти рёбра остаются различными вариантами выбора.

Определитель сохраняет произведение через выбор столбцов

Ориентированная матрица инцидентности B и диагональная матрица W весов дают L=BWBᵀ. После удаления корневой строки формула Коши—Бине раскрывает кофактор по наборам n−1 столбцов. Для набора, не являющегося деревом, минор нулевой;для дерева его квадрат равен 1. Остаётся ровно произведение выбранных весов.

Такое доказательство объясняет, почему показатель каждого отдельного w_e не больше 1 и почему ориентация вспомогательных столбцов не влияет на результат. Оно также отличает взвешенную формулу от попытки просто поставить сумму стоимостей на диагональ без согласованных отрицательных внедиагональных элементов.

Объединение параллельных факторов меняет интерпретацию счёта

Если два параллельных ребра имеют веса u,v, ни один остов не использует оба, поскольку они образовали бы цикл длины 2. Их альтернативные вклады складываются как u+v. Поэтому объединённое ребро с этим весом сохраняет Z. Но при последующем подсчёте невзвешенных различных рёбер объединение изменило бы количество вариантов.

Если Z>0, можно назначить вероятность дерева пропорционально его произведению весов. Отрицательные веса сохраняют некоторые полиномиальные тождества, но уже не задают обычных вероятностей. Нулевые веса фактически запрещают вклад деревьев с соответствующим ребром, так что связность положительной поддержки нужно проверять отдельно.

Пять деревьев и один взвешенный кофактор

Условие. Между A,B есть два разных ребра весов 2 и 3, между B,C — одно веса 5, между A,C — одно веса 7. Найдите Z и сравните с количеством остовов.

  1. Остовы с ребром BC и одним AB имеют веса 10 и 15;с AC иодним AB —14 и 21. Остов из BC,AC имеет вес 35.
  2. Всего пять наборов рёбер, а Z=10+15+14+21+35=95. Два параллельных AB вместе не образуют остов на трёх вершинах.
  3. Суммарный вес AB равен 5. После удаления строки/столбца C кофактор равен[[12,−5],[−5,10]], его определитель 120−25=95.
  4. Обычное количество 5, взвешенный перечислитель 95 и минимум суммы численных весов 7 являются тремя разными ответами на разные вопросы.

Ответ. Z=95;различных остовов 5.

Проверка. Перебор шести пар четырёх отдельных рёбер исключает только пару параллельных AB. Независимое сложение пяти произведений совпадает с точным 2×2 определителем.

Где легко ошибиться. Произведение весов остова не равно сумме стоимостей его рёбер. Перед использованием взвешенного кофактора назовите считаемый объект и не выдавайте Z за минимум стоимости.

Проверьте понимание

Что считает 95 в задаче?

Вопросы к этой главе

Можно объединить параллельные рёбра?

Для взвешенного перечислителя да, заменив их вес суммой. Для буквального невзвешенного числа различных исходных рёбер нужно помнить кратность.

Почему полный определитель L нулевой?

Каждая строка суммируется в 0, поэтому единичный вектор находится в ядре. Взвешивание не устраняет эту зависимость;нужен кофактор либо эквивалентная корректная модификация.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Shayan Oveis Gharan: Random Spanning Trees, lectures1–2

    Первичные лекции: прочитаны weighted Matrix Tree Theorem, определение произведения весов дерева и формула вероятности ребра через удаление. Собственные параллельные рёбра и цикл с листом рассчитаны независимо. MIT lecture22 PDF имел 0 читаемых строк и не используется как прочитанный текст.

Вероятность ребра в равномерном случайном остове

Число остовов превращается в вероятность участия конкретного ребра через удаление или стягивание. Полученные маргинальные вероятности не делают разные рёбра независимыми.

Перед началом: Равномерный случайный остов; Подсчёт остовных деревьев.

Разбейте все деревья по присутствию одного ребра

Пусть связный граф G имеетτ(G)>0 остовов, и каждый выбран с одинаковой вероятностью. Деревья без ребра e в точности являются остовами G−e. Поэтому P(e∈T)=1−τ(G−e)/τ(G). Если удаление разрывает граф, числитель второго слагаемого 0 и ребро обязательно.

Деревья, содержащие непетлевое e, взаимно однозначно соответствуют остовам G/e после стягивания e. Параллельные рёбра при этом сохраняют отдельные идентификаторы, а возникшие петли в дерево не входят. Значит также P(e∈T)=τ(G/e)/τ(G). Это равенство даёт независимый маршрут вычисления той же вероятности.

Сумма маргинальных вероятностей имеет точный контроль

Каждый остов на n вершинах содержит n−1 рёбер. Записав его размер суммой индикаторов и взяв ожидание, получаем ΣₑP(e∈T)=n−1. Для этого не нужна независимость индикаторов. Такой суммарный контроль помогает обнаружить ошибку в одном кофакторе либо в обработке кратных рёбер после стягивания.

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

Совместная вероятность требует отдельного счёта

Для набора ациклических рёбер F событие F⊆T можно посчитать стягиванием всего F. Если F содержит цикл, вероятность 0. Произведение отдельных вероятностей в общем случае не равно результату: дерево имеет фиксированный размер и запрещает циклы, что связывает выборы.

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

Цикл и обязательный лист

Условие. G состоит из цикла A–B–C–D–A и листового ребра CE. Найдите вероятности AB,CE и совместную вероятность AB,BC.

  1. Ребро CE обязательно. Из четырёх рёбер цикла удаляется ровно одно, поэтому всегоτ(G)=4 остова.
  2. Без AB остаётся единственное дерево, значит P(AB)=1−1/4=3/4. Стягивание AB даёт треугольник с листом иτ=3, подтверждая ответ.
  3. Удаление CE разъединяет E с остальными, поэтому P(CE)=1. Сумма вероятностей четырёх цикловых и листового рёбер равна 4·3/4+1=4=n−1.
  4. Оба AB и BC сохраняются тогда, когда удалено CD либо DA. Вероятность 2/4=1/2, а произведение маргинальных равно 9/16 и не совпадает.

Ответ. P(AB)=3/4,P(CE)=1,P(AB и BC)=1/2;события не независимы.

Проверка. Полное перечисление четырёх допустимых удалений даёт частоты 3,4 и 2 из 4. Оно не использует определители и одновременно проверяет оба маргинальных и совместный ответ.

Где легко ошибиться. Не умножайте маргинальные вероятности без доказательства независимости. Два отдельно возможных ребра могут быть связаны общим запретом цикла и фиксированным размером остова.

Проверьте понимание

Чему равна совместная вероятность AB и BC в задаче?

Вопросы к этой главе

Может вероятность ребра быть нулевой в связном простом графе?

Каждое непетлевое ребро можно дополнить до остова, поэтому при равномерной модели его вероятность положительна. Петли и нулевые веса в другой модели требуют отдельной оговорки.

Зачем две формулы удаления и стягивания?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Shayan Oveis Gharan: Random Spanning Trees, lectures1–2

    Первичные лекции: прочитаны weighted Matrix Tree Theorem, определение произведения весов дерева и формула вероятности ребра через удаление. Собственные параллельные рёбра и цикл с листом рассчитаны независимо. MIT lecture22 PDF имел 0 читаемых строк и не используется как прочитанный текст.

Направленные остовы и правильная сторона лапласиана

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

Перед началом: Определитель и кофактор; Ориентированный путь.

Уточняем направление дерева до построения матрицы

Сходящаяся к корню r арборесценция содержит все вершины и |V|−1 дуг: каждая вершина, кроме r, имеет ровно одну исходящую дугу, и следование этим дугам заканчивается в r. Корень не имеет исходящей дуги дерева. Расходящаяся арборесценция устроена наоборот: от корня достижима каждая вершина, а у каждой некорневой ровно одна входящая дуга.

Пусть Aᵢⱼ — неотрицательный вес дуги i→j, петли игнорируются. Взвешенный исходящий лапласиан L_out имеет диагональ Σⱼ≠ᵢAᵢⱼ и внедиагональные элементы −Aᵢⱼ. После удаления строки и столбца r определитель равен сумме произведений весов всех сходящихся к r арборесценций. При целых весах это также можно понимать как подсчёт выбора параллельных дуг, но в общем случае ответ является взвешенной суммой, не количеством наборов.

Цикл исключается, достижение корня остаётся

Если выбрать по одной исходящей дуге у каждой некорневой вершины, получится функциональная структура. Она может либо довести каждую вершину до r, либо содержать направленный цикл вне корня. Разложение определителя организует сокращение циклических выборов; остаются именно деревья с путями к r. Поэтому просто перемножить исходящие степени недостаточно: такой продукт включает запрещённые циклы.

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

Нулевой определитель имеет маршрутный смысл

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

Одна сеть, два направления

Условие. Дуги A→B=2,A→C=1,B→A=3,B→C=4,C→A=5,C→B=1. Найдите взвешенную сумму деревьев, сходящихся к C, и сравните с расходящимися из C.

  1. Исходящие суммы A,B равны 3,7. Удалив C, получаем матрицу [[3,−2],[−3,7]], её определитель равен 21−6=15.
  2. Перечислим сходящиеся варианты: A→C,B→C с весом 4; A→B,B→C с весом 8; A→C,B→A с весом 3. Выбор A→B,B→A образует цикл и исключается.
  3. Для обратного направления входящие суммы A,B равны 8,3. Главный кофактор входящего лапласиана равен det[[8,−3],[−2,3]]=24−6=18.
  4. Прямое перечисление расходящихся деревьев даёт C→A,A→B с весом 10; C→A,C→B с весом 5; C→B,B→A с весом 3. Сумма 18 подтверждает различие направлений.

Ответ. К корню C взвешенная сумма 15; из корня C взвешенная сумма 18.

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

Где легко ошибиться. Не применяйте неориентированный лапласиан к ориентированной сети и не называйте взвешенную сумму 15 количеством деревьев. Здесь различных наборов только 3.

Проверьте понимание

Какова взвешенная сумма арборесценций, сходящихся к C?

Вопросы к этой главе

Почему дуги из C не влияют на первый ответ?

В сходящемся дереве корень не имеет исходящей дуги. После удаления строки C соответствующие веса не входят в главный кофактор. Для расходящихся деревьев эти же дуги, наоборот, существенны.

Можно ли использовать теорему для нулевых весов?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • MIT18.212, Lecture28: Directed Matrix Tree Theorem

    Прочитаны взвешенное обобщение и Theorem5, различающий in-tree/out-tree и исходящие/входящие степени. Используется главный кофактор исходящего лапласиана для сходящихся к корню деревьев. Собственная сеть с весами 2,1,3,4,5,1 перечислена напрямую; рисунки источника не используются.

Второе собственное значение лапласиана измеряет связность

Нулевая часть спектра лапласиана показывает число компонент графа без подсчёта остовных деревьев. Причина лежит в энергии разностей значений на концах рёбер: она исчезает ровно для функций, постоянных на каждой компоненте. Это даёт и алгебраический критерий, и явный базис ядра.

Перед началом: Симметричная матрица; Собственный вектор.

Каждое ребро вносит неотрицательный квадрат

Для неориентированного графа с положительными весами w_uv определим L=D−A: диагональ равна сумме инцидентных весов, внедиагональные элементы равны −w_uv. Тогда xᵀLx=Σ_{uv∈E}w_uv(x_u−x_v)², причём каждое неориентированное ребро в сумме учитывается один раз. Отсюда L положительно полуопределена, а вектор всех единиц всегда принадлежит ядру.

Если Lx=0, энергия равна 0, поэтому на каждом положительном ребре x_u=x_v. Вдоль путей это распространяется на всю компоненту. Обратно, любой вектор, постоянный на каждой компоненте, даёт Lx=0 непосредственно по строкам. Значит индикаторы компонент образуют базис ядра, и его размерность в точности равна числу компонент связности.

Второе собственное значение отличает связный граф

Для n≥2 упорядочим собственные значения λ₁≤λ₂≤…≤λₙ. Они неотрицательны, λ₁=0. Граф связен ровно тогда, когда λ₂>0: в связном случае ядро одномерно, в несвязном нуль имеет кратность хотя бы2. Поскольку L симметрична, алгебраическая и геометрическая кратности совпадают. Для единственной вершины второго значения нет, и этот частный критерий не формулируется.

Малое положительное λ₂ отражает слабую связность, но для точного количества компонент важен именно нуль. В приближённых вычислениях округлённое число 10⁻¹² нельзя без модели ошибки объявить ни точным нулём, ни доказательством связи. На маленьком графе точный ранг, рациональный базис ядра и обычный обход дают независимые сертификаты без выбора произвольного порога.

Знак весов является математической предпосылкой

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

Две компоненты, два независимых нуля

Условие. Граф имеет треугольник ABC и отдельное ребро DE, все веса 1. Найдите ядро лапласиана, его нулевую кратность и полный спектр.

  1. В порядке A,B,C,D,E матрица блочно-диагональна: блок треугольника имеет диагональ 2 и внедиагональные −1, блок ребра равен[[1,−1],[−1,1]].
  2. Векторы u=(1,1,1,0,0) и v=(0,0,0,1,1) дают Lu=Lv=0 и независимы. Энергетическое тождество запрещает другие направления ядра: значения обязаны совпадать внутри ABC и внутри DE.
  3. Внутри треугольника два независимых вектора с суммой координат 0 имеют собственное значение 3. На ребре вектор(0,0,0,1,−1) имеет значение 2.
  4. Итак, спектр равен 0,0,2,3,3. В частности λ₂=0, граф несвязен, а число компонент равно 2. Вектор 2u−v лежит в ядре, хотя не постоянен на всём графе.

Ответ. kerL=span(u,v), нулевая кратность 2, спектр 0,0,2,3,3.

Проверка. Точный независимый базис из пяти собственных векторов восстанавливает всю матрицу и имеет ненулевой определитель. Отдельный поиск в ширину находит компоненты ABC и DE; обе проверки согласуются с ядром.

Где легко ошибиться. Не делайте вывод о компонентах по одному равенству L1=0: оно верно у любого лапласиана. Нужно определить всю размерность ядра либо кратность нуля.

Проверьте понимание

Какова кратность нулевого собственного значения L в примере?

Вопросы к этой главе

Почему связный граф не имеет обратимого лапласиана?

Вектор всех единиц всегда ненулевой и лежит в ядре, поэтому полный L вырожден даже при связности. Положительная определённость возникает после ограничения на подпространство, перпендикулярное единицам, либо в подходящем главном миноре.

Что изменится после добавления ребра CD положительного веса?

Обе старые компоненты соединятся. Новое условие нулевой энергии потребует одинаковых констант на ABC и DE, поэтому ядро станет одномерным и λ₂ станет строго положительным.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Daniel Spielman: Spectral Graph Theory, Lecture2, §2.1

    Прочитаны квадратичная энергия, Lemma2.1.1 и Corollary2.1.2 о числе компонент и кратности нулевого собственного значения. Собственная несвязная пятивершинная сеть проверена точным базисом собственных векторов; остовные кофакторы не используются.

Минор лапласиана считает лес с заданными корнями

Удаление нескольких одинаковых строк и столбцов лапласиана считает уже не одно связное остовное дерево. Получается сумма весов остовных лесов, в каждой компоненте которых находится ровно один заранее выбранный корень. Условие о корне каждой компоненты существенно.

Перед началом: Взвешенный лапласиан неориентированного графа; Остовное дерево и ациклический лес.

Несколько удалённых вершин задают несколько компонент

Пусть граф конечный, неориентированный, с неотрицательными весами рёбер. Лапласиан L имеет на диагонали сумму инцидентных весов, а вне диагонали — отрицательный суммарный вес соответствующей пары вершин. Выберем непустое множество корней R и удалим из L строки и столбцы с этими индексами.

Определитель оставшейся главной подматрицы равен сумме произведений весов по остовным лесам, где каждая компонента содержит ровно один элемент R. Поэтому компонент ровно |R|, а рёбер ровно |V|−|R|. Изолированный корень разрешён: одноэлементная компонента тоже содержит ровно один корень. Компонента без корня или с двумя корнями недопустима.

Причина появляется в минорах матрицы инцидентности

Ориентируем каждое ребро произвольно и запишем L=BWBᵀ, где B — матрица инцидентности, W — диагональ весов. После удаления корневых строк формула Коши–Бине выражает определитель как сумму по наборам |V|−|R| столбцов. Вклад равен произведению весов, умноженному на квадрат определителя соответствующей укороченной матрицы инцидентности.

Цикл делает выбранные столбцы зависимыми. Компонента без корня даёт зависимость оставшихся строк. В допустимом лесу удаление одного корня из каждой компоненты оставляет треугольное исключение листьев с определителем ±1. Квадрат убирает знак произвольной ориентации. Так остаются именно требуемые леса с положительным единичным множителем при каждом произведении.

Главный минор не считает все леса одинакового размера

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

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

Два корня на взвешенном пятицикле

Условие. Граф — цикл 0–1–2–3–4–0. Четыре первых ребра имеют вес 1, ребро 4–0 имеет вес 2. Корни R={0,2}. Найдите взвешенную сумму допустимых лесов.

  1. После удаления корней остаются вершины 1,3,4 и матрица [[2,0,0],[0,2,−1],[0,−1,3]]. Её определитель равен 2·(6−1)=10.
  2. Для независимого подсчёта рассмотрим два пути между корнями. На коротком пути 0–1–2 нужно оставить ровно одно из двух рёбер: два выбора с весом 1.
  3. На длинном пути 2–3–4–0 нужно оставить ровно два из трёх рёбер. Произведения весов трёх вариантов равны 1,2,2, их сумма равна 5.
  4. Выборы на двух путях независимы. Получаем шесть допустимых лесов и взвешенную сумму (1+1)·(1+2+2)=10.
  5. Обычный остов пятицикла потребовал бы четыре ребра и дал бы другую взвешенную сумму 9. Здесь требуются три ребра и две компоненты, разделяющие корни.

Ответ. Главный минор и прямой корневой подсчёт дают 10; число допустимых невзвешенных лесов равно 6.

Проверка. Перебор всех десяти трёхрёберных подмножеств проверяет ацикличность и ровно один корень в каждой компоненте. Он оставляет шесть лесов с суммой произведений 10, независимо от определителя.

Где легко ошибиться. Не считайте любой ациклический набор нужного размера допустимым. Связав оба заданных корня в одной компоненте, он обязательно оставит другую компоненту без корня.

Проверьте понимание

Чему равна взвешенная сумма лесов с корнями {0,2} в разобранном пятицикле?

Вопросы к этой главе

Разрешена ли компонента из одного корня?

Да. Она уже имеет ровно один корень и не требует рёбер. Её вклад в произведение весов равен единице, как пустое произведение.

Почему произвольная ориентация рёбер не меняет ответ?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • David G. Wagner: Combinatorics of Electrical Networks

    Теорема 7, All-Minors Weighted Matrix-Tree Theorem: леса с одним элементом каждого корневого множества в компоненте; главный минор получается при совпадающих множествах.

Песочная модель: устойчивое состояние, срабатывание и критическая группа

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

Перед началом: Приведённый лапласиан графа; Фактор-группа целочисленной решётки.

Срабатывает только вершина, достигшая своей степени

Конечный связный неориентированный граф с выделенным поглощающим стоком; неотрицательные целые количества песчинок, сток никогда не срабатывает.

Вершина v неустойчива, если c(v)≥deg(v), где степень учитывает и рёбра в сток. Легальное срабатывание вычитает deg(v) из неё и добавляет по единице каждому соседу вне стока. Песчинки, ушедшие в сток, больше не возвращаются. Состояние устойчиво, когда 0≤c(v)<deg(v) во всех нестоковых вершинах.

Если L — симметричный приведённый лапласиан, а u хранит числа срабатываний, итог удовлетворяет c_final=c_initial−Lu. Это необходимая проверка, но не разрешение вычитать любой целый Lu: каждый промежуточный шаг должен иметь достаточный запас песчинок. Абелево свойство утверждает одинаковые итог и числа срабатываний для всех легальных порядков стабилизации.

Класс по лапласиану сохраняется, но устойчивых состояний больше

Любое срабатывание меняет конфигурацию на столбец L. Поэтому класс в Z^m/LZ^m не изменяется. При связном графе со стоком L невырождена, и число классов равно det L. Однако две разные устойчивые конфигурации могут лежать в одном классе: просто выбрать любую устойчивую конфигурацию как уникальный представитель нельзя.

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

Модульный инвариант позволяет распознать конкретный класс

Один определитель сообщает число классов, но не сравнивает заданные состояния. Для этого можно искать целочисленный линейный функционал φ(c), который обращается в ноль по модулю N на каждом столбце L. Тогда все легальные срабатывания сохраняют φ. Если функционал сюръективен и N=det L, он полностью нумерует классы фактор-группы.

Такое доказательство не заменяет проверку стабилизации: инвариант может совпадать у нескольких устойчивых состояний. Для маленького графа возвратность независимо находят по конечному графу операций «добавить одну песчинку и стабилизировать», выделяя замкнутый достижимый класс. Это отделяет алгебраическое равенство классов от конкретной легальной динамики.

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

Условие. Нестоковые вершины a,b,c соединены путём a—b—c, и каждая соединена со стоком s одним ребром. Стабилизируйте начальное (4,0,3). Найдите порядок критической группы и проверьте инвариант φ(c)=c_a+2c_b+5c_c по модулю 8.

  1. Степени равны 2,3,2, поэтому L=[[2,−1,0],[−1,3,−1],[0,−1,2]]. Устойчивые диапазоны дают 2·3·2=12 состояний.
  2. Один легальный порядок срабатываний a,a,c,b,c даёт состояния (2,1,3),(0,2,3),(0,3,1),(1,0,2),(1,1,0). Последнее устойчиво, счётчик срабатываний u=(2,1,2).
  3. Проверяем Lu=(3,−1,3), поэтому (4,0,3)−Lu=(1,1,0). Функционал на столбцах L даёт 0,0,8; следовательно сохраняется по модулю 8. До стабилизации φ=19≡3, после неё φ=3.
  4. Определитель L равен 8. Функционал сюръективен на Z/8, поскольку коэффициент при c_a равен 1, и полностью описывает восемь классов. Независимый граф добавлений имеет восемь возвратных состояний среди двенадцати устойчивых.

Ответ. Итог стабилизации (1,1,0), u=(2,1,2). Критическая группа изоморфна Z/8; класс данного состояния имеет номер 3 по φ.

Проверка. Перебор всех возможных легальных очередностей для (4,0,3) даёт единственный итог и тот же u. Конечная проверка всех устойчивых состояний находит восемь возвратных представителей с различными остатками φ; возвратная единица класса 0 равна (1,1,1), а не нулевому состоянию.

Где легко ошибиться. Не объявляйте все 12 устойчивых состояний элементами группы порядка 12. Число групповых классов равно 8, а четыре устойчивых состояния не входят в возвратную группу.

Проверьте понимание

Сколько элементов имеет критическая группа графа из разобранного примера?

Вопросы к этой главе

Почему строка суммы Lu может иметь отрицательную координату?

Это суммарное изменение потерь и поступлений. В worked вершина b получает от соседей больше, чем теряет собственным срабатыванием, поэтому координата Lu для неё равна −1; реальные промежуточные количества остаются неотрицательными.

Зачем сток должен быть доступен из каждой вершины?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Perkinson — Primer for the Algebraic Geometry of Sandpiles, §2.2

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться