#import "./template.typ": thmrules, template, definition, theorem, proof, claim, code, lemma, corollary, remark, turn-on-first-line-indentation as fli, indent

#let sp = h(0.5em)

#let state_dict(d) = {
  // assert(type(d) == dictionary)
  ${
      #(d
    .pairs()
    .map(((k, v)) => $bold(#(k+":")) #v$)
    .join(",")
    )
    }$
}

#let generated_image(subpath) = {
  // assert(type(subpath) == str)
  (..args) => image("../assets/converted/" + subpath + ".png", ..args)
}

#let image_by_hand(subpath) = {
  // assert(type(subpath) == str)
  (..args) => image("../assets/images/" + subpath, ..args)
}

#let varnothing = $text(font: "Fira Sans", nothing)$

#let comment(cnt) = text(fill: red, cnt)

#let quo(l, r) = {
  $#l"/"#r$
}
#let esq(u, eqv_rel: none) = $[#u]_#( if eqv_rel == none {"~"} else {eqv_rel})$

#let Stab = $"Stab"$
#let Aut = $"Aut"$
#let Gen = $"Gen"$

#show: thmrules
#show: template

////////////////////////
// Document begins!
////////////////////////

= РЕФЕРАТ <nonum>

// TODO Количество страниц и тп

#context [
  #let total_pages = counter(page).final().at(0)
  #let total_images = counter(figure.where(kind: image)).final().at(0)
  #let total_references = 32

  !! Расчетно-пояснительная записка #total_pages с., #total_images рис., #total_references источника.
]

Ключевые слова: ГРАФОВАЯ ДИНАМИЧЕСКАЯ ПОРОГОВАЯ МОДЕЛЬ, РЕСУРСНАЯ СЕТЬ, РЕГУЛЯРНЫЙ ГРАФ, АВТОМОРФИЗМ, СИММЕТРИЯ.

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

В работе используется аппарат теории графов, теории групп, теории динамических систем, а также данные, полученные из предыдущих исследований ресурсных сетей. Для проведения моделирования и визуализации результатов написана программа `Sponge-networks` на языке `python`, ее исходный код открыт и доступен на Github.

#outline(title: [Содержание])

// TODO Дописать или переписать))

= ВВЕДЕНИЕ <nonum>

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

Модель ресурсной сети представляет собой ориентированный граф, в каждой вершине которого располагается некоторое количество так называемого ресурса (некоторое неотрицательное вещественное число). Вершины могут накапливать сколь угодно большое количество ресурса. Модель представляет собой динамическую систему в дискретном времени, похожую на цепь Маркова. Как и в цепи Маркова, на каждом такте между соседними вершинами происходит перераспределение значений чисел, приписанных к вершинам, так, чтобы суммарное количество ресурса осталось неизменным (ресурс не появляется из ниоткуда и не исчезает в пустоту). Если суммарное количество ресурса в сети невелико, то ресурсная сеть функционирует как цепь Маркова (с поправкой на некоторый коэффициент). Однако же в случае большого суммарного ресурса в силу вступают нелинейные факторы: согласно определению ресурсной сети, вершина не может отдать по ребру ресурса больше, чем пропускная способность этого ребра.

Понятие ресурсной сети было впервые предложено Кузнецовым~О.~П. в 2009 году @Kuznetsov2009. Данная тема получила широкое развитие: были исследованы многие свойства обыкновенных ресурсных сетей. Так, в монографии Жиляковой~Л.~Ю. @ЖИЛЯКОВА2013 были вычленены основные характеристики ресурсных сетей (например, пороговое значение ресурса, вершины-аттракторы) и предложена классификация сетей. Был проведен полный анализ поведения нерегулярных ресурсных сетей при малом количестве ресурса, эйлеровых сетей, регулярных сетей и др. Решение задачи алгоритмического нахождения порогового значения в эргодической ресурсной сети было предложено в @Скороходов2016. Скороходов~В.~А. предложил детерминированный алгоритм, который позволил находить пороговое значение в любой эргодической сети за $O(n)$ (здесь $n$ -- число вершин в сети). Можно отметить и работу @Zhilyakova2022, в которой с помощью ресурсных сетей были получены результаты в теории стохастических матриц и неоднородных цепей Маркова. В статье @Abdulrahman2024 описана связь между традиционной потоковой моделью (сетью Флойда-Фалкерсона) и ресурсными сетями.

Рассматривалось также и множество модификаций указанной модели. Изучались модель распределения ресурсного потока в ресурсной сети с динамическими длительностями прохождения по дугам @Скороходов2023. Несмотря на разительно отличающиеся качественные характеристики таких сетей, было показано, что суммарный ресурс в сети -- как и в случае обычных ресурсных сетей -- остается неизменным. Более того, было установлено, что если суммарный ресурс не меньше порогового значения в исходной сети, то в сети с динамическими длительностями прохождения по дугам существует единственный предельный поток. Особого внимания заслуживает модификация ресурсной сети с «жадными» вершинами @Чаплинская2021, предложенная Н. <NAME>ской. Исследовались также и приложения ресурсных сетей к моделированию реальных процессов, например, распространения вещества в жидкой среде @Zhilyakova2012.

Наша работа предлагает еще одно приложение ресурсных сетей: моделирование перколяции, т.е. просачивания в некоторой среде. Каноническим трудом является @Bollobas_Riordan_2006, где описаны основные модели, исследующие это явление. Исследование перколяции как направления математики активно и по сей день, примером чему может служить обзорная статья @Li2021, в которой описываются современные модели и методы их исследования. Исследования процессов перколяции на графах продолжаются, предлагаются всё новые модели, такие как перколяция на случайных регулярных графах @Nachmias2007 @Joos2017, перколяция в сложных сетях @Cohen2009, перколяция в смешанных случайных @Verbavatz2021 и псевдослучайных @Diskin2021 графах, а также многие другие.

Отметим, однако, что основным методом исследования перколяции является теория случайных графов. Мы же предлагаем несколько иное прочтение понятия перколяции и иной способ моделирования -- с помощью регулярных ресурсных сетей (названных _губковыми сетями_), которые являются модификацией модели ресурсной сети.

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

Вопросы, которые поднимаются в нашей работе имеют также тесную связь с общей теорией динамических систем: их симметриями, фазовыми пространствами и морфизмами между ними. Нередко данные понятия используются в эргодической теории @Walters2000, однако там объектами изучения выступают такие операции над динамическими системами, которые сохраняют некоторую меру или же являются гомеоморфизмами некоторых топологических пространств. Более общий подход описан, к примеру, в @Brin2002. Симметрии динамических систем могут открывать новую перспективу для их качественного анализа. Так, в работе @Murza2017 <NAME> анализирует гетероклинические циклы и бифуркации Хопфа произвольной динамической системы, группой симметрий которой является группа кватернионов $bold(Q)_8$, с помощью чего автор определяет определяет условия для существования гетероклинического цикла между тремя произвольными положениями равновесия системы.

Динамические системы на графах -- например, последовательные динамические системы (Sequential Dynamical Systems, CDS) -- представляют отдельный интерес для исследователей; они обобщают конечные автоматы, клеточные автоматы, цепи Маркова, булевы сети и многие другие понятия @Mortveit2007. Так, периодическое поведение булевых сетей изучались в серии работ Ж. Аледо и <NAME> -- например в @Aledo2020 -- с помощью теории SDS. Симметрии дискретных динамических систем (в частности, SDS) изучались в работе @Kornyak2010, что позволило получить интересные результаты в области клеточных автоматов, а особенно -- игры "Жизнь" Конвея.

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

= ОСНОВНЫЕ ПОНЯТИЯ

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

== Теория групп

Отметим, сначала, что все определения и утверждения из данного раздела взяты из классической литературы по теории групп, например, из @Винберг2019.

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

#definition[
  Группой называется алгебра $H eq.def (X, dot, (-)^(-1), e)$, где
  - X -- произвольное множество;
  - $dot$ -- бинарная операция (умножение);
  - $(-)^(-1)$ -- унарная операция (обращение);
  - $e$ -- константа (единица);
  и удовлетворяются следующие аксиомы

  + $forall x, y, z in X sp (x dot y) dot z = x dot (y dot z)$ (ассоциативность умножения);
  + $forall x in X sp x dot e = e dot x = x$ (нейтральный элемент);
  + $forall x in X sp x dot x^(-1) = x^(-1) dot x = e$ (обратимость).
]

Одна из основных интерпретаций группы -- симметрии некоторого объекта. Самый простой пример -- группа диэдра $D_n$, которая является группой симметрий правильного $n$-угольника. Композиция любых симметрий есть снова симметрия, существует тождественная симметрия (при которой каждая точка многоугольника переходит в себя), и к каждой симметрии есть обратная.

Можно и здесь $d = 3$ привести более формальное построение. Пусть $M$ -- \ -- некоторое множество, а $H$ -- некоторое подмножество биекций $H arrow.hook H$, замкнутое относительно композиции $compose$ и обращения $(-)^(-1)$, в которое входит тождественное отображение. Поскольку композиция функций ассоциативна, то $H$ -- группа, которая называется *группой автоморфизмов* $M$ или *группой симметрий* $M$. В таком случае, говорят, что группа $H$ *действует* на множестве $M$. На самом деле, для любой группы можно указать множество, на котором она действует. Элементы $H$ называются *автоморфизмами* или *симметриями* множества $M$.

#definition[
  Действие группы $H$ на множестве $M$ называется *транзитивным*, если $forall x, y in M sp exists f in H: f(x) = y$. Иначе говоря, любой элемент множества $M$ может быть переведен в любой другой какой-то симметрией.
]

#definition[
  Пусть группа $H$ действует на множестве $M$. Тогда $Stab_H (x) = { f in H | f(x) = x }$ -- *стабилизатор* элемента $x$ при действии группы $H$ на него, т.е. множество таких симметрий, которые оставляют элемент $x$ на месте.
]

== Графы

Информация по теории графов берется из канонических трудов, таких как, например, @Trudeau1993.

#definition[
  *(Ориентированным) графом* назовем пару множеств $G eq.def (V, E)$, где $E subset V times V$. $V$ будем называть *множеством вершин*, а $E$ -- \ -- *множеством ребер*.
]

Граф называется *взвешенным*, если существует некоторое множество весов $X$ и некоторая функция $phi: E -> X$, сопоставляющая каждому ребру графа определенный вес.

Введем следующие дополнительные понятия и обозначения:

- вершины $u$ и $v$ *смежные*, если $(u, v) in E or (v, u) in E$;
- для произвольной вершины $v in V$ $"adj"^-(v) = {u in V | (u, v) in E}$;
- для произвольной вершины $v in V$ $"adj"^+(v) = {u in V | (v, u) in E}$;
- для произвольной вершины $v in V$ $"adj"(v) = "adj"^-(v) union "adj"^+(v)$ -- множество всех вершин, смежных с $v$.

Неориентированный граф можно понимать как частный случай ориентированного, где множество $E$ симметрично ($forall (v_1, v_2) in E sp (v_2, v_1) in E$). Мы будем пользоваться понятием ориентированного графа, покуда не оговорено обратное.

#definition[
  $Gen_(G)(V')$ -- подграф графа $G$, *порожденный* подмножеством $V' subset V$ вершин графа $G$, то есть граф $G' = (V', E')$, где $forall u, v in V' sp ((u, v) in E' <=> (u, v) in E)$.
]

// Граф обычно считается конечным в том смысле, что $V$ конечно.

#definition[
  #fli[
    Отображение $Phi: V -> V$ называется *морфизмом* графа $G$, если $forall u, v in V sp (u, v) in E => (Phi(u), Phi(v)) in E$. Если $Phi$ -- биекция, то она называется *автоморфизмом* графа $G$.

    Множество автоморфизмов действительно есть группа автоморфизмов на множестве $V$, она обозначается как $(Aut(G))$.

    Если граф взвешенный, то дополнительно требуется, чтобы $forall u, v in V: (u, v) in E sp Phi(phi((u, v))) = phi((Phi(u), Phi(v)))$.
  ]
] <def:graph-aut>

Отметим, что мы будем пользоваться двойной нотацией. С одной стороны, мы будем относиться к автоморфизмам графа как к отображениям $V -> V$, как и сказано в определении @def:graph-aut. С другой стороны, мы можем говорить о них как об отображениях на $V union.sq E$, где вершины переводятся в вершины, а ребра -- \ -- в ребра. В таком случае, если $(u, v) = e in E$, то под $Phi(e)$ будет пониматься ребро $(Phi(u), Phi(v))$. Такая нотация позволяет намного более компактную формулировку некоторых утверждений, а также позволяет более естественное обобщение на, например, мультиграфы.

#definition[
  Пусть $G = (V, E)$ -- некоторый ориентированный граф. Допустим, на множестве вершин $V$ задано произвольное отношение эквивалентности "$~$". Образуем *факторграф графа* $G$ по отношению $~$ согласно~@Gardiner1974. Определим $quo(G, ~) eq.def (V', E'):$

  $
    cases(
      V' = quo(V, ~)";",
      (esq(u), esq(v)) in E' <=> exists u in esq(u)"," exists v in esq(v) : (u, v) in E.
    )
  $ <nonum>
  // , при этом оно конгруэнтно относительно отношения $E$, т.е. сохраняет смежность вершин:
] <def:quotient-graph>

#let ft1 = footnote[
  На самом деле, данная аналогия является точной, если рассматривать описанные примеры как частный случай более общего теоретико-категорного определения понятия фактор-объекта в соответствующей категории. Так, факторграф является фактор-объектом в категории графов, факторгруппа является фактор-объектом в категории групп и т.п. Более подробно о фактор-объектах можно прочитать, например, в классической работе Роберта Голдблатта @Goldblatt2014[глава 4].
]

Интерпретация данного понятия такова: в графе $G$ можно "склеить" некоторые вершины и рассматривать их как одну, при этом "новой" вершине будут смежны все вершины, которые были смежны "старым" вершинам, склеенным в "новую". Можно проводить аналогию #ft1 с факторгруппами, топологическими факторпространствами и др., в которых также некоторые элементы множества отождествляются; только в случае графов никаких дополнительных ограничений на отношение эквивалентности (наподобие конгруэнтности) не требуется.

== Динамические системы

Информация, содержащаяся в данном разделе, взята из @Brin2002 и @Mortveit2007.

#definition[
  Пусть дано произвольное множество $X$ и некоторая функция $S: X -> X$. *Дискретная динамическая система* $cal(S) eq.def (X, S)$ может быть образована из $S$ следующим образом: если $q(0) in X$ -- некотрое начальное состояние, то $q(t) = S(q(t-1)), t in NN$. $S$ при этом называется *функцией эволюции динамической системы*.
]

#definition[
  Пусть $cal(S)_1 = (X_1, S_1)$ и $ cal(S)_2 = (X_2, S_2)$ -- две динамические системы. Отображение $Phi : X_1 -> X_2$ называется *морфизмом* между $cal(S)_1$ и $cal(S)_2$, если $forall x in X_1 sp Phi(S_1(x)) = S_2(Phi(x))$.

  Отображение $Phi$ называется *изоморфизмом*, если оно биективно.

  Изоморфизм $Phi$ называется *автоморфизмом*, если оно изоморфизм и $cal(S)_1 = cal(S)_2$, т.е. автоморфизм -- это изоморфизм "на себя". Группа всех автоморфизмов динамической системы $cal(S)$ обозначается $Aut(cal(S))$.
] <def:dyn_syst_aut>

Симметричность поведения динамических систем и выражается понятием автоморфизма. Автоморфизм передает всю полноту информации о динамической системе.

В качестве примера системы обладающей симметрией, можно привести следующую: $S: RR -> RR$:

$ S(x) = a_1 x + a_2 x^3, sp sp a_1, a_2 in RR. $ <eq:dyn-auto-ex1>

У данной системы присутствует следующий автоморфизм: $Phi(x) = -x$. Действительно,

$
  forall x in RR sp S(Phi(x)) = S(-x) = a_1 (-x) + a_2 (-x)^3 = - (
    a_1 x + a_2 x^3
  ) = Phi(S(x)).
$ <nonum>

Если динамическая система обладает нетривиальным автоморфизмом, то между фазовыми траекториями существует некоторая биекция, сохраняющая свойства этих траекторий. Так, траектория, полученная из начального \ состояния $3$ системы @eq:dyn-auto-ex1 обладает теми же свойствами, что и траектория, начинающаяся из начального состояния $-3$ -- разница лишь в знаке. Положим, нам интересно рассмотреть множество всех возможных траекторий данной системы. Для этого стоило бы взять всевозможные начальные состояния $q^0 in RR$ и затем строить $S(q^0), S^2(q^0), ...$. Благодаря наличию симметрии $Phi$ можно сузить множество рассматриваемых состояний до $RR_+$.

== Модель ресурсной сети

Ресурсная сеть -- ориентированный размеченный граф, в каждой вершине которого находится некоторое количество «ресурса». Ресурс есть некоторое неотрицательное вещественное число. Можно мыслить о ресурсе как о жидкости. Ресурсная сеть образует динамическую систему с дискретным временем. А именно, каждый такт ресурс перераспределяется между вершинами так, чтобы суммарное количество ресурса в сети оставалось неизменным. Каждая вершина «отдает» в каждое из своих ребер ресурс, пропорциональный пропускной способности (метке) этого ребра, но не больше, чем сама пропускная способность. Таким образом, если в вершине ресурса достаточно мало, то система функционирует эквивалентно цепи Маркова (с поправкой на некоторый коэффициент). Напротив, если предположить, что во всех вершинах сети ресурса больше, чем их пропускная способность, то на следующем такте из каждой вершины уйдет ровно столько ресурса, какова ее пропускная способность, и придет столько ресурса, каков суммарный вес всех входящих в нее ребер. Оба этих случая по отдельности кажутся очень простыми, однако сложность представляет исследование именно промежуточных состояний, то есть таких, при которых часть вершин содержит мало ресурса, а часть -- много.

Определим теперь понятие ресурсной сети более формально.

#definition[
  *Ресурсная сеть* -- это тройка $"SN" = (G, D, S)$, где:
]
- $G = (V, E)$ -- ориентированный граф, дуги $E$ которого размечены над множеством $RR_+$ неотрицательных вещественных чисел, а $|V| = n$. Метки дуг лучше всего понимать как аналог пропускной способности. Предположим, что зафиксирована некоторая нумерация вершин \ $"num": V -> overline(1"," n) .$ Тогда метку дуги $e_(i j)$ будем записывать как $r_(i j)$ ($r_(i j) = 0$ если дуги не существует);

- $D$ -- множество (допустимых) состояний динамической системы, т.е. некоторое подмножество множества $(V arrow.r med bb(R)_(+))$. Менее формально говоря: каждой вершине $v$ может быть присвоено некоторое значение из множества $bb(R)_(+)$, но, вообще говоря, не все значения из $bb(R)_(+)$ могут быть допустимыми. Произвольное состояние из $D$ будем обозначать как $q in D$. Если нумерация вершин считается фиксированной, то под $q$ будем понимать $n$-мерный вектор.

- $S: D -> D$ -- функция эволюции динамической системы, при этом $S$ однозначно определяется $G$ и $D$. Более подробное описание функции $S$ будет приведено ниже.

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

#definition[
  *Ресурсы* $q_i (t)$ -- неотрицательные числа, присвоенные вершинам $v_i; #h(0.6em) i = overline(1"," n)$ и изменяющиеся в дискретном времени $t$.

  !!*Состояние* $Q(t)$ c на временном шаге $t$ представляет собой вектор-строку значений ресурсов в каждой вершине: $q(t) = (q_1(t), q_2(t), ..., q_(n)(t))$.
]

#definition[
  *Матрица пропускной способности* ресурсной сети -- $R eq.def (r_(i j))_(n times n)$. В~сущности, это матрица смежности графа $G$ с весами из $RR_+$.
]

#definition[
  *Стохастическая матрица* ресурсной сети:

  $
    R' eq.def
    mat(
      delim: "(",
      r_11 / r_1^("out"), dots.h.c, r_(1 n) / r_1^("out");
      dots.v, dots.down, dots.v;
      r_(n 1) / r_n^("out"), dots.h.c, r_(n n) / r_n^("out")
    ),
  $ <nonum>

  где $bold(r_i^("out")) eq.def sum_(j=1)^n r_(i j)$.

  !! Матрица $R'$ называется стохастической потому, что если рассмотреть цепь Маркова, построенную по тому же графу $G$, что и ресурсная сеть, отнормировав при этом веса ребер так, чтобы в каждой строке матрицы смежности сумма значений была равна единице, то получим в точности матрицу $R'$.
]

#definition[
  *Матрица потока* ресурсной сети:

  $ F(q) eq.def min {R' dot.circle (bold(1) dot.op q), R}, $ <nonum>

  где min применяется поэлементно, $dot.circle$ -- произведение Адамара, $bold(1)$ -- вектор-столбец из единиц.

  !! Поток из $i$-й вершины в $j$-ю есть в точности то количество ресурса, которое придет из $i$-й вершины в $j$-ю под действием $S$. Следует отметить следующее.
  + Ресурсы, приходящие из разных вершин, складываются.
  + Если суммарный выходной поток меньше текущего количества ресурса в вершине, то излишек не пропадает, а остается в вершине.
] <def:flow-matrix>

Таким образом, можно определить, наконец, функцию эволюции динамической системы $S$:

$ S(q) eq.def q - (F(q) dot bold(1))^T + bold(1)^T dot F(q). $ <eq:S>

Дискретная динамическая система определяется стандартно: пусть дано некоторое начальное состояние $q^0 in D,$ тогда определим:

$
  cases(
  q(0) &= q^0";",
  q(t) &= S(q(t-1))"," sp t in NN.
)
$

#definition[
  Пусть дано некоторое состояние $q$ ресурсной сети. Тогда определим

  $
    Z^(-)(q) = {v_i in G | q_i <= r_i^("out")};\
    Z^(+)(q) = {v_i in G | q_i > r_i^("out")}.
  $

  !! Очевидно, что $forall q in RR_(+)^n sp Z^(+)(q) union.sq.big_()^() Z^(-)(q) = V$. Если вершина принадлежит $Z^(+)(q)$, то говорим, что она *работает по правилу 1*. Если же вершина принадлежит $Z^(-)(q)$, то говорим, что она *работает по правилу 2*.
]

#let state_1 = ("0": 8, "1": 1, "2": 0)

Пример ресурсной сети $"network"_1$ можно видеть на @fig:basic_network_1. Множество вершин здесь есть $V = {0, 1, 2}$, а метки ребер обозначают соответствующие веса в графе $G$. На @fig:basic_network_2 показано некоторое состояние сети с ресурсами #state_dict(state_1). При данном способе визуализации вершины имеют разный размер в зависимости от количества имеющегося в них ресурса. Более того, вершины $v_i$, в которых ресурс не меньше порогового значения (т.е. $q_i >= r_i^("out")$), окрашены в фиолетовый цвет, а остальные -- в салатовый.

#grid(
  columns: 2,
  align: center,
  [
    #v(1em)
    #figure(
      caption: [Ресурсная сеть $"network"_1$],
      generated_image("basic_network/plot")(width: 75%),
    ) <fig:basic_network_1>
  ],
  [
    #figure(
      caption: [Состояние сети $"network"_1$ при #state_dict(state_1)],
      generated_image("basic_network/sim")(),
    ) <fig:basic_network_2>
  ],
)

Матрица пропускной способности $"network"_1$ приведена в формуле @eq:basic_network_R, а ее стохастическая матрица -- в формуле @eq:basic_network_R_1. Можно убедиться, что сумма значений в каждой строке стохастической матрицы равна единице.

#grid(
  columns: 2,
  [
    $
      R = mat(
        0, 3, 1;
        4, 1, 0;
        2, 2, 0;
    )
    $ <eq:basic_network_R>
  ],
  [
    $
      R' = mat(
      0   , 0.75, 0.25;
      0.8 , 0.2 , 0   ;
      0.5 , 0.5 , 0   ;
    )
    $ <eq:basic_network_R_1>
  ],
)

Исходя из формы определения матрицы потока @def:flow-matrix, можно объяснить механизм функционирования ресурсной сети более наглядно. Если предположить, что в некотором состоянии все вершины работают по правилу 1 (т.е. $Z^+(q) = V$), то из @eq:S и определения @def:flow-matrix получим

$ S(q) = q - (R dot bold(1))^T + bold(1)^T dot R = q + 1^T (R - R^T). $ <nonum>

Иначе говоря, в этой ситуации модель напоминает потоковую @Goldberg1989, поток не зависит от текущего состояния, а только от свойств самого графа. Напротив, если предположить, что все вершины работают по правилу 2 (т.е. $Z^-(q) = V$), то окажется, что модель получается линейной:

$ S(q) = q dot R'. $ <eq:Markov>

Поскольку матрица $R'$ -- стохастическая (т.е. сумма значений в каждой строке равна 1), то модель @eq:Markov аналогична модели цепи Маркова с непрерывным состоянием и дискретным временем @Dynkin1965.

Отметим, что "большая часть" ресурсных сетей в пределе ведут себя во многом идентично цепям Маркова. Подробное и объемлющее описание поведения обычных ресурсных сетей приведено в @ЖИЛЯКОВА2013.

== Модель ресурсной сети с жадными вершинами

Данная модификация модели обыкновенной ресурсной сети была предложена Чаплинской Н.В. в @Жилякова2021, а затем исследована в работах @Чаплинская2021 @Чаплинская2021a. Суть модели в следующем: вершины, обладающие петлей отдают свой ресурс сначала в петлю, а остаток распределяют уже согласно обыкновенному закону функционирования ресурсной сети. Получается, что такие вершины -- \ "запасливые", пытающиеся сначала "отложить" ресурс себе, а уже потом распределять его между соседями. Из такой аналогии и проистекает их название.

Одно из интересных свойств такой сети состоит в том, что при достаточно маленьком количестве ресурса и при выполнении некоторых дополнительных свойств достижимости в графе и при некотором начальном распределении ресурса по вершинам происходит так называемая "остановка" сети: 100%~ресурса оказывается сосредоточено в жадных вершинах, при этом вершина не может отдавать ресурс никуда, помимо петли (поскольку ресурса у нее недостаточно). Получается, что поток в сети оказывается нулевым (за исключением петель, в которые все время поступает весь ресурс из вершин). Естественно, динамическая система оказывается стабилизированной в том смысле, что $S(q) = S^2(q)$. Пример останавливающейся сети приведен на @fig:stop_network_2. Более подробное описание ситуаций, в которых сети демонстрируют подобное поведение представлено в @Чаплинская2021 (например, утверждение 5).

#figure(
  caption: [Сеть в остановившемся состоянии],
  generated_image("stop_network/sim2")(),
) <fig:stop_network_2>

= РЕЗУЛЬТАТЫ

== Губковые сети

Настоящее исследование посвящено *губковым сетям*. Относить к губковым сетям мы будем ресурсные сети с жадными вершинами, имеющими специфическую топологию. А именно, будем рассматривать графы, являющиеся _регулярными_ (определим "регулярность" более подробно ниже), при этом у таких графов будет выделен "верх" и "низ", т.е. множество вершин, в которые в начальный момент времени будет класться ресурс и множество вершин, в которые этот ресурс может стекать. При этом подразумевается наличие некоторой ориентации: протекание ресурса "сверху вниз" должно идти быстрее, чем "снизу вверх". Более того, в целях более точной геометрической интерпретации модели можно было бы считать, что графы губковых сетей планарны, т.е. допускают вложение в $RR^2$. Однако, как будет показано в дальнейшем, такое ограничение является слишком сильным. Пример губковой сети ($"sponge_network"_1$) приведен на @fig:some_sponge_network_1. Верхними вершинами в $"sponge_network"_1$ являются ${(i, 2) | i in #overline[0, 4]}$, а стоковыми ${(i, -1) | i in overline(0"," 4)}$.

На данном примере можно показать, откуда проистекает название губковых ресурсных сетей. Можно представить, что данный граф моделирует некоторую двухмерную губку с решетчатой внутренней структурой (в данном случае, решетка квадратная). В начальный момент времени на губку капают некоторой жидкостью сверху (на верхние вершины). Затем жидкость просачивается через губку, дотекая до низу, и вытекает из губки (в стоковые вершины). Мы рассматриваем также вариант модели, в которой нет стоковых вершин (например, как на @fig:some_sponge_network_without_sinks_1). Граф "губки" при этом (по крайней мере, если убрать стоковые вершины) является сильно связным. Это сделано для моделирования капиллярного эффекта: жидкость может распространяться из одного кусочка губки во все соприкасающиеся с ним куски, в том числе и вверх. Заметим, что веса ребер, идущих "сверху вниз", заметно больше, чем веса ребер, идущих "снизу вверх" ($5 >> 1$), что подкрепляет физическую аналогию.

#figure(
  caption: [Пример губковой сети $"sponge_network"_1$],
  // placement: horizon,
  generated_image("some_sponge_network/plot")(width: 100%),
) <fig:some_sponge_network_1>

#figure(
  caption: [Губковая сеть $"sponge_network"_1$, в которой убраны стоки],
  // placement: bottom,
  generated_image("some_sponge_network_without_sinks/plot")(width: 100%),
) <fig:some_sponge_network_without_sinks_1>

Губковая сеть в некотором роде есть продолжение модели распространения загрязнения в водной среде, описанной в @Жилякова2011. В ней распространения загрязнения моделировалось растеканием ресурса в сети, заданной прямоугольной решеткой, в которой пропускные способности соответствовали силе течений и скорости ветра. Губковая сеть, помимо иной интерпретации, отличается большей гибкостью: она включает большее разнообразие топологий, имеет жадные вершины, а также является открытой -- ресурс может втекать сверху и вытекать снизу.

=== Программная реализация

Для исследования свойств губковых сетей, было реализовано соответствующее программное окружение на языке Python. Приложение было названо "sponge-netowrks", оно имеет открытый исходный код, опубликованный на Github @Корешков2023. Лицензия проекта -- MIT.

Основная задача проекта -- предоставить пользователю доступ к надежному, удобному и свободно расширяемому интерфейсу для проведения различных исследований в области ресурсных сетей. Проект интегрирован со средой jupyter notebook, что позволяет получать результаты симуляций и прочих операций над ресурсными сетями в удобно читаемом и интерактивном виде. Sponge-networks позволяет:
- создавать ресурсные сети на основе матриц, графов и списков смежности;
- модифицировать произвольным образом ресурсные сети, не нарушая внутренней целостности данных;
- проводить симуляции, задавая количество шагов, которые должна отработать система, и начальные условия. Результат симуляции хранит в себе всю необходимую информацию о состояниях и потоках сети за время симуляции;
- искать предельные состояния ресурсной цепи, а также положения равновесия эргодической ресурсной сети как цепи Маркова;
- представлять симуляции в виде массивов, листов Excel и графиков;
- рисовать ресурсные сети;
- рисовать симуляции в виде ресурсных сетей с анимациями, реализованными с помощью слайдера, который позволяет визуализировать на граф ресурсной сети в произвольный момент времени (@fig:some_sim_with_slider_1, @fig:some_sim_with_slider_2);

#figure(
  caption: [Некоторая сеть в момент времени $t = 0$],
  image_by_hand("some_sim_with_slider/1.png")(width: 70%),
) <fig:some_sim_with_slider_1>

#figure(
  caption: [Та же сеть в момент времени \ $t = 49$],
  placement: top,
  image_by_hand("some_sim_with_slider/2.png")(width: 70%),
) <fig:some_sim_with_slider_2>

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

=== Типы топологий сетей

Были рассмотрены и реализованы губковые сети не только с квадратной сеткой (как на @fig:some_sponge_network_1), но и с треугольной (@fig:network_types_example_triangular), и с шестиугольной (@fig:network_types_example_hexagonal).

#figure(
  caption: [Пример губковой сети с треугольной сеткой (`n_rows` $= 3$, `n_cols` $= 5$)],
  placement: top,
  generated_image("network_types_example/triangular")(width: 72%),
) <fig:network_types_example_triangular>

#figure(
  caption: [Пример губковой сети с шестиугольной сеткой (`n_rows` $= 2$, `n_cols` $= 4$)],
  placement: top,
  generated_image("network_types_example/hexagonal")(width: 100%),
) <fig:network_types_example_hexagonal>

Все вышеуказанные сети могут быть построены с помощью функции `build_sponge_network`. Например, сеть на @fig:some_sponge_network_1 была построена так, как приведено на @lst:build_sponge_network_ex[листинге].
Из приведенного вызова функции можно видеть, какие параметры можно задавать для сети: тип сети `grid_type` (`"grid_2d"` -- квадратная сетка, `"triangular"` -- треугольная, `"hexagonal"` -- шестиугольная); количество "строк" `n_rows`; количество "столбцов" `n_cols`; видимую длину ребер, ведущих в стоковые вершины `visual_sink_edge_length` и особенности сети `layout`. Последний параметр включает в себя описание весов ребер в сети, а также флаг, указывающий, создавать ли стоковые вершины.

#figure(
  caption: [Пример создания губковой сети \ с помощью функции `build_sponge_network`],
  // placement: top,
  code(
    ```python
    build_sponge_network(
        grid_type="grid_2d",
        n_cols=4,
        n_rows=3,
        layout={
            "weights_horizontal": 3,
            "weights_up_down": 5,
            "weights_down_up": 1,
            "weights_loop": 1,
            "weights_sink_edge": 1,
            "generate_sinks": True,
        },
        visual_sink_edge_length=0.7,
    )
    ```
  )
) <lst:build_sponge_network_ex>

#pagebreak()

== Симметричность губковых сетей

Как можно видеть, губковые сети -- в отличие от ресурсных сетей вообще -- \ -- имеют довольно симметричную структуру. Попробуем определить более формально, что это означает. Для начала, вслед за Грюнбаумом @Gruenbaum1977, определим замощения плоскости.

#definition[@Gruenbaum1977][
  Пусть $cal(F)$ -- некоторое разбиение плоскости на измеримые множества ненулевой меры. Назовем $"Sym"(cal(F)) eq.def ("Trans"(RR^2) dot $ \ $dot O(2)) sect {phi in (RR^2 -> RR^2) | forall d in cal(F) sp phi(d) in cal(F)}$ *группой симметрий этого разбиения*, где $"Trans"(RR^2) dot O(2)$ -- группа движений евклидовой #box[плоскости @Винберг2019[стр. 164]]. Иначе говоря, это такой набор движений плоскости (вращений, отражений и параллельных переносов), который переводит все множества из $cal(F)$ в (возможно, другие) множества из $cal(F)$. Очевидно, что #box[$"Sym"(cal(F))$ -- группа].
]

#definition[@Gruenbaum1977][
  *Замощением плоскости* называется разбиение плоскости на множество многоугольников $cal(F)$, при этом "типов" многоугольников конечное число, в том смысле что множество, состоящее из орбит всех элементов множества $cal(F)$ под действием группы $"Sym"(cal(F))$ -- иначе говоря, $quo(cal(F),"Sym"(cal(F)))$ -- конечно.
]

#definition[@Gruenbaum1977][
  Замощение плоскости называется *регулярным*, если группа $"Sym"(cal(F))$ действует на $cal(F)$ транзитивно, т.е. $|quo(cal(F), "Sym"(cal(F)))| = 1$.
]

Известно (@Gruenbaum1977), что регулярных замощений плоскости всего 3: прямоугольное, треугольное и шестиугольное.

Пусть $G$ -- бесконечный локально конечный (т.е. $|V| = aleph_0$, но $forall v in $ \ $in V |"adj"(v)| < infinity$) планарный неориентированный граф, а $"emb"(G)$ -- вложение этого графа в плоскость. Скажем, что $G$ определяет разбиение плоскости следующим образом: рассмотрим множество $RR^2 \\ "emb"(G)$. Скажем, что $cal(F)$ есть множество связных компонент $RR^2 \\ "emb"(G)$ (либо же замыканий этих связных компонент, если нам удобно рассматривать множества с границей). Без ограничения общности, можно считать, что $cal(F)$ состоит из многоугольников. Будем считать, что не составит труда привести такие графы и их вложения, чтобы соответствующие им разбиения были треугольным, прямоугольным или шестиугольным замощением плоскости; при этом такие вложения будут максимальными для соответствующих графов. Назовем эти графы и вложения *каноническими*.

Губковые сети, представленные до сих пор, могут быть рассмотрены как подграфы канонических графов для соответствующих регулярных замощений плоскости. Конечно, для проведения такого соответствия $cal(I)$, переводящего губковую сеть в подмножество соответствующего разбиения, нужно откинуть веса ребер у губковой сети, а также превратить ее граф из ориентированного в неориентированный. Именно в этом смысле графы губковых сетей являются регулярными. Однако, следует заметить, что сужение $"Sym"(cal(F))$ на образ $cal(I)$ (т.е. $"Im"(cal(I))$) не является группой, так что указанная симметрия замощения на губковые сети не работает. Именно поэтому провести параллель между симметриями губковых сетей и симметриями регулярных замощений плоскости проблематично. Нам придется прибегнуть к анализу симметрий непосредственно губковых сетей, без привязки к замощениям плоскости.

Сделаем теперь комментарий насчет количества "строк" и "столбцов", характеризующих губковую сеть и указываемых при создании конкретного объекта (как на @lst:build_sponge_network_ex[листинге]). Считать строки и столбцы следует не по вершинам, а по многоугольникам в $"Im"(cal(I))$. Так, число этих многоугольников равно в точности `n_rows` $dot$ `n_cols`, в чем можно убедиться, взглянув на @fig:network_types_example_triangular и @fig:network_types_example_hexagonal.

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

#definition[
  Пусть дана некоторая ресурсная сеть $"RN"$. Отображение $Phi : "RN" -> "RN"$ будем называть *автоморфизмом ресурсной сети*, если оно является автоморфизмом графа $G$, соответствующего этой сети, которое сохраняет, при этом, веса ребер, т.е. $forall e in E sp w(e) = w(Phi(e))$, где $w(e)$ -- вес ребра $e$, а также переводит верхние вершины в верхние.

  !! *Группой автоморфизмов ресурсной сети* $"RN"$ назовем множество всех автоморфизмов данной сети $Aut("RN")$, в котором композиция функций выступает в качестве бинарной операции, наделяя указанное множество групповой структурой.
] <def:rn_aut>

#claim[
  Автоморфизм губковой сети переводит стоковые вершины в стоковые.
] <claim:auto>

Утверждение @claim:auto очевидно следует из того, что список смежности вершины является инвариантом графа, а вершины без исходящих ребер все суть стоковые.

Пусть $m in NN$ -- количество столбцов в сети, а $n in NN$ -- количество строк. Будем теперь иметь в виду, что вершины в губковых сетях допускают нумерацию парой натуральных чисел, как демонстрировалось на приведенных выше рисунках. При этом вершина с наименьшими индексами $(x, y)$ находится "слева снизу", а с наибольшими -- "справа сверху". Стоковые вершины нумеруются индексами $(x, -1)$. Верхние вершины в прямоугольной и треугольной сетях обладают индексами $(i, n)$, а в шестиугольных $(i, 2 n + 1)$ (в шестиугольных вершины с индексами $(i, 2 n)$ верхними не являются).

#definition[
  Пусть дана произвольная губковая сеть $"SN"$ (прямоугольная, треугольная или шестиугольная), а $v_1 = (x_1, y_1) in V$ и \ $v_2 = (x_2, y_2) in V$, при этом $e = (v_1, v_2) in E$. Определим наименования *типов ребер* следующим образом:
  - Ребро $e$ -- *горизонтальное*, если $x_1 != x_2 and y_1 = y_2$;
  - Ребро $e$ -- *"сверху вниз"*, если $y_1 > y_2$;
  - Ребро $e$ -- *"снизу вверх"*, если $y_1 < y_2$;
  - Ребро $e$ -- *петля*, если $v_1 = v_2$.
]

Будем исходить из того, что веса ребер в сети таковы, что:
- все ребра одного типа имеют одинаковые веса;
- вес ребер "сверху вниз" больше, чем вес ребер "снизу вверх".

Данные предположения будем называть *базовыми предположениями о губковой сети*. Все сети, продемонстрированные выше, удовлетворяют этим предположениям.

Для дальнейшего обсуждения докажем следующее полезное утверждение.

#claim[
  Если $Phi in Aut(G)$, а $V' in V$ -- инвариантное относительно $Phi$ подмножество вершин графа (т.е. $Phi(V') = V'$), то \ $Phi|_V' in Aut(Gen_G (V'))$.
] <claim:aut_restriction>

#proof[
  Рассмотрим произвольные вершины $v_1, v_2 in V'$. Очевидно, что $Phi((v_1, v_2)) = (Phi(v_1), Phi(v_2))$ принадлежит множеству ребер $Gen_G (V')$. Более того, $Phi$ -- биекция на $V'$. Следовательно, $Phi$ -- автоморфизм на $Gen_G (V')$.
]

#theorem[
  Пусть губковая сеть $"SN"$ удовлетворяет базовым предположениям о губковой сети.
  Верно следующее:
  - $"SN"$ обладает осевой симметрией, т.е. $Aut("SN") tilde.equiv quo(ZZ, 2 ZZ)$, если сеть:
    - прямоугольная;
    - шестиугольная, при этом $m$ -- нечетное;
    - треугольная, при этом $m$ -- нечетное и $m > 1$;
  - $Aut("SN") tilde.equiv limits(times.big)_(i = 1)^(ceil(n "/" 2)) quo(ZZ, 2 ZZ)$ если сеть треугольная и $m = 1$;
  - в остальных случаях, сеть не обладает симметрией, т.е. $Aut("SN") tilde.equiv bold(1)$.

  !! При этом не важно, есть ли в сети стоки или нет.
]<th:sym>

Перед тем, как перейти к доказательству, покажем примеры сетей, о которых идет речь. На @fig:network_types_example_triangular приведен пример треугольной сетки с нечетным количеством столбцов, а на @fig:network_types_example_hexagonal -- шестиугольной с четным. Дополним указанные рисунки треугольной сеткой с четным количеством столбцов (@fig:network_types_example_triangular_sym) и шестиугольной с нечетным (@fig:network_types_example_hexagonal_sym). Также на @fig:network_types_example_triangular_single_sym показан пример треугольной сетки с единственным столбцом.

#figure(
  caption: [Пример губковой сети с треугольной сеткой и одним столбцом (повернуто на $90 degree$)],
  scale(
    x: 100%,
    y: 100%,
    rotate(
      reflow: true,
      -90deg,
      generated_image("network_types_example_sym/triangular_single")(),
    ),
  ),
) <fig:network_types_example_triangular_single_sym>

#figure(
  caption: [Пример губковой сети с шестиугольной сеткой \ (`n_rows` $= 2$, `n_cols` $= 3$)],
  generated_image("network_types_example_sym/hexagonal")(),
) <fig:network_types_example_hexagonal_sym>

#figure(
  caption: [Пример губковой сети с треугольной сеткой (`n_rows` $= 2$, `n_cols` $= 4$). #h(1em)],
  generated_image("network_types_example_sym/triangular")(),
) <fig:network_types_example_triangular_sym>

// #proof[
//   #fli[

Пусть $Phi in Aut("SN")$. Разделим наш граф на "уровни" следующим образом. Обозначим за $V_tilde(n)$ множество верхних вершин сети, где $tilde(n) eq.def 2n+1$ если сеть шестиугольная и $tilde(n) eq.def n$ в ином случае.
Далее, $V_(tilde(n)-1) eq.def {(j, tilde(n) - 1) | j in NN} sect V$ -- \ -- множество всех вершин "предпоследнего уровня". И вообще, определим $V_i eq.def {(j, i) | j in NN} sect V$ вплоть до $V_0$ (или же $V_(-1)$, если в сети есть стоки). Очевидно, $V = limits(union)_i V_i$. Докажем теперь, что $forall V_i  sp Phi(V_i) = V_i$. По определению @def:rn_aut, $Phi(V_tilde(n)) = V_tilde(n)$. Предположим, что для некоторого $i$ известно, что $Phi(V_(i+1)) = V_(i+1)$. Рассмотрим произвольное ребро графа $e = (v_1, v_2)$, такое что $v_1 in V_(i+1)$, а $v_2 in V_i$. Поскольку $Phi$ -- автоморфизм, то $Phi(e) = (Phi(v_1), Phi(v_2))$. Мы предположили, что $Phi(v_1) in V_(i+1)$, а значит для ребра $v_2$ в силу специфики рассматриваемых графов есть всего 3 варианта: $Phi(v_2) in V_(i+1)$, или $Phi(v_2) in V_(i+2)$, или $Phi(v_2) in V_i$. Первый вариант невозможен, поскольку тогда получится, что $v_2 in Phi^(-1)(V_(i+1)) = V_(i+1)$, что противоречит определению $V_(i+1)$. \ По той же причине невозможен и второй вариант. Значит, $Phi(v_2) in V_i$.

В случае треугольной или прямоугольной сетки $V_i subset limits(union)_(v in V_(i+1)) "adj"(v)$, так что отсюда и из доказанного выше автоматически следует, что $Phi(V_i) = V_i$. В шестиугольной сети вершина $(0, 2n)$, а в случае нечетного $m$ еще и вершина $(m, 2n)$, оказываются не связанными с верхним уровнем $V_(2n+1)$. Однако анализа ее (их) списка смежности уже достаточно, чтобы понять, что при автоморфизме она (они) не может (не могут) перейти ни в какие другие вершины, поскольку у нее (них) в соседях единственная вершина на том же уровне и единственная на уровне ниже нее (них), что подразумевает соответствующее распределение взвешенных ребер; при этом эта (эти) вершина(ы) не может (не могут) перейти в верхние, поскольку, по определению, в верхние переходят только верхние. Так что в четном случае $Phi((0, 2n)) = (0, 2n)$, а в нечетном эти вершины переходят либо в себя, либо друг в друга. Таким образом, доказано, что \ $forall i sp Phi(V_i) = V_i$.

Оценим теперь, как могут вести себя вершины из $V_i$ под действием $Phi$. Рассмотрим (максимальный) подграф $G_i = Gen_(G)(V_i)$ графа $G$, порожденного вершинами $V_i$. В случае прямоугольной или треугольной сетки (и при $m > 1$ в случае треугольной) $G_i$ -- двунаправленная цепь. Ввиду равенства всех весов горизонтальных ребер между собой и всех петель между собой, $G_i$ допускает единственный нетривиальный автоморфизм $S_i$, "разворачивающий" цепь в обратную сторону (по аналогии с отражением $S$ в группе диэдра). Соответственно, $Aut(G_i) = $ \ $= {id_(V_i), S_i}$. Более того, $Phi|_(G_i) in Aut(G_i)$.

Как ведет себя $Phi$ при попытке "связать" эти пока что независимо рассматривавшиеся части? Всего есть 4 варианта того, как ведет себя $Phi|_(Gen_(G)(V_(i+1) union V_i))$, а именно:

$
  Phi|_(Gen_(G)(V_(i+1) union V_i)) in {
    id, sp id_(V_(i+1)) union.sq S_i, sp S_(i+1) union.sq id_(V_i), sp S_(i+1) union.sq S_(i)
  }.
$ <nonum>

Можно убедиться, что четвертый вариант действительно является автоморфизмом на $Gen_(G)(V_(i+1) union V_i)$ в прямоугольном случае или в треугольном при нечетном $n$. Если же сеть треугольная и $n$ четно, то степени крайних вершин в $V_i$ при рассмотрении графа $Gen_(G)(V_(i+1) union V_i)$ не совпадают, так что такие вершины попросту не могут переходить друг в друга, так что $Aut("SN") tilde.equiv bold(1)$ в случае треугольной сети с четным числом столбцов.

Второй и третий варианты также не дают нам автоморфизма, поскольку в этом случае под действием $Phi$ рвется связь между, например, вершинами \ $(0, i+1)$ и $(0, i)$:

$
  ((0, i+1), (0, i)) in E, "но" (Phi((0, i+1)), Phi((0, i))) in.not E.
$ <nonum>

Однако же, если сеть треугольная и в ней присутствует всего один столбец, то наше рассуждение неверно, так как один уровень ($V_(i+1)$ или $V_i$) состоит из единственной вершины (и тогда, конечно, либо $S_(i+1) = id$, либо $S_i = id$) и можно проверить, что тогда $Phi$ действительно автоморфизм на $Gen_(G)(V_(i+1) union V_i)$.

До сих пор мы оставляли в стороне шестиугольные сети. В них $G_i$ является не цепью, а набором из пар взаимно соединенных вершин, либо же некоторыми одиночными вершинами, так что $Aut(G_i)$ достаточно насыщенна. Лучше же рассмотреть $Gen_(G)(V_(i+1) union V_i)$. В отличие от прямоугольных и квадратных сетей, здесь этот граф как раз таки и представляет из себя цепь, только веса ребер, не являющихся петлями, здесь не все равны друг другу: присутствуют как горизонтальные ребра, так и "сверху вниз" и "снизу вверх". Отметим, что, по аналогии с рассмотрением сужения $Phi$ на $V_i$, $Phi|_(Gen_(G)(V_(i+1) union V_i))$ также должна быть автоморфизмом $Gen_(G)(V_(i+1) union V_i)$, поскольку $Phi(V_(i+1) union V_i) = V_(i+1) union V_i$.

Можно заметить, что $Aut(Gen_(G)(V_(i+1) union V_i)) tilde.equiv bold(1)$ если $m$ четно, так как веса на ребрах крайних вершин цепи оказываются различными. И, наоборот, можно убедиться, что при нечетном $m$ $Aut(Gen_(G)(V_(i+1) union V_i)) =$ \ $= {id_(V_(i+1) union V_i), S'_i}$, где $S'_i$ -- соответствующее отражение. Попытка "связать" $S'_(i+1)$ и $S'_i$ по аналогии с тем, что мы сделали для прямоугольной или треугольной сети выше, еще быстрее даст нам ответ \ $Aut(S'_(i+1) union S'_i) = {id, S'_(i+1) union S'_(i)}$, поскольку часть вершин у \ $Gen_(G)(V_(i+2) union V_(i+1))$ и $Gen_(G)(V_(i+1) union V_i)$ совпадает, при этом $S'_(i+1)$ и $S'_i$ совпадают на пересечении их областей определения.

Итак, мы показали, что для всех рассмотренных типов сетей (помимо треугольной сети с одним столбцом) единственный возможный нетривиальный автоморфизм -- отражение. Более того, было показано, что при объединении отражений на разных "уровнях" мы получаем корректно определенное отражение на большем подграфе графа $G$. Естественным образом доказывается, что, проделав подобную процедуру $tilde(n)$ раз, можно получить отражение $S$, определенное корректно на всем графе $G$. Таким образом, доказано, что, помимо случаев, оговоренных выше, \ $Aut("SN") tilde.equiv quo(ZZ, 2 ZZ)$.

Рассмотрим теперь случай треугольной сети с одним столбцом. Здесь "склеивание" возможно между различными функциями: как тождественными, так и отражениями. Отражений, при этом, набирается ровно столько, сколько имеется строк с двумя вершинами, а их $ceil(n "/" 2)$. Таким образом, $Aut("SN")$ является прямым произведением групп, сгенерированных отражениями на всевозможных уровнях, т.е. \ $Aut("SN") tilde.equiv limits(times.big)_(i = 1)^(ceil(n "/" 2)) quo(ZZ, 2 ZZ)$.
//   ]
// ]

Наблюдение, касающееся того, какие автоморфизмы может иметь объединение двух графов, можно обобщить с помощью следующего утверждения.

#claim[
  Пусть $G$ -- произвольный граф (возможно, неориентированный или же с взвешенными ребрами), при этом \ $V = V_1 union.sq V_2$. Пусть $Aut(G)(V_1) = V_1$ и $Aut(G)(V_2) = V_2$, т.е. все автоморфизмы графа $G$ переводят вершины из $V_i$ в $V_i$. Определим $tilde(V)_1$ как множество тех вершин из $V_1$, которые смежны с некоторыми вершинами из $V_2$ в графе $G$, т.е. \ $tilde(V_1) = {v in V_1 | "adj"_G (v) sect V_2 != varnothing}$, аналогичным образом определим $tilde(V)_2$. Пусть $H_1 = Aut(Gen_G (V_1))$, $H_2 = Aut(Gen_G (V_2))$. Тогда выполняется неравенство:

  $
    (limits(sect.big)_(v in tilde(V)_1) Stab_(H_1)(v)) times (
      limits(sect.big)_(v in tilde(V)_2) Stab_(H_2)(v)
    ) <= Aut(G) <= H_1 times H_2.
  $
]

#proof[
  #fli[
    Рассмотрим произвольный автоморфизм $Phi in Aut(G)$. В силу условия на инвариантность множеств $V_i$ и утверждения~@claim:aut_restriction, $Phi|_V_1 in H_1, Phi|_V_2 in H_2$. Из этого можно заключить, что отображение $Phi$ принадлежит множеству $Aut(Gen_G (V_1))$ в прямом произведении с $Aut(Gen_G (V_2))$, значит $Aut(G) <= H_1 times H_2$.

    Докажем второе неравенство. Обозначим $N_i eq.def limits(sect.big)_(v in tilde(V)_i) Stab_(H_i)(v),$ где \ $i = overline(1"," 2)$. Пусть некоторая функция $Phi_1 in H_1$ оставляет на месте все вершины, соприкасающиеся со множеством $V_2$, т.е. $Phi_1 in N_1$. Аналогичным образом, пусть $Phi_2 in N_2$. Пара функций $(Phi_1, Phi_2)$ принадлежит, с одной стороны, группе #box[$N_1 times N_2$] по определению последней. С другой стороны, с каждой такой парой $(Phi_1, Phi_2)$ можно сопоставить функцию $Phi: G -> G$ следующим образом. Пусть #box[$Phi(v) = Phi_1(v)$], если $v in V_1$ и $Phi(v) = Phi_2(v),$ если $v in V_2$. На ребрах же ее действие определим так. Если $v_1, v_2 in V_1$, то $Phi((v_1, v_2)) = Phi_1((v_1, v_2))$; аналогично с множеством $V_2$. Если же $v_1 in V_1, v_2 in V_2$, то пусть $Phi((v_1, v_2)) = (v_1, v_2)$; аналогично с $v_1 in V_2, v_2 in V_1$.

    Несложно понять, что $Phi$ -- биекция. Докажем, что $Phi in Aut(G)$. Если $v_1, v_2 in V_1$, то

    $
      Phi((v_1, v_2)) = Phi_1((v_1, v_2)) = (Phi_1(v_1), Phi_2(v_2)) = (
        Phi(v_1), Phi(v_2)
      );
    $ <nonum>
    аналогично с $v_1, v_2 in V_2$. Предположим, $v_1 in V_1, v_2 in V_2$. Если #box[$(v_1, v_2) in E$], то тогда $v_1 in tilde(V)_1, v_2 in tilde(V)_2$ и, согласно определению $Phi_1$ и $Phi_2$, $Phi(v_1) = v_1, Phi(v_2) = v_2$, так что действительно оказывается, что $Phi((v_1, v_2)) = (v_1, v_2) = (Phi(v_1), Phi(v_2))$. Напротив, если $(v_1, v_2) in.not E$, то нового ребра не появится, поскольку множества $V_1 \\ tilde(V)_1, sp V_2 \\ tilde(V)_2$ также инвариантны относительно $Phi$. Симметричные рассуждения можно провести и для $v_1 in V_2, v_2 in V_1$.

    Таким образом, показано, что $Phi in Aut(G)$ и, соответственно, #box[$N_1 times N_2 subset Aut(G)$]. Наши выкладки следует дополнить тем фактом, что отображение $mu$, ставящее каждой паре функций #box[$(Phi_1, Phi_2) in N_1 times N_2$] элемент #box[$Phi in Aut(G)$], сохраняет групповую операцию: $mu(Phi'_1 compose Phi_1, Phi'_2 compose Phi_2) = mu(Phi'_1, Phi'_2) compose$ \ $compose mu(Phi_1, Phi_2)$. Получается, что $mu$ -- гомоморфизм групп, а значит #box[$N_1 times N_2 <= Aut(G)$].
  ]
]

В определении автоморфизма сказано о необходимости того, чтобы верхние вершины переходили в верхние при отображении. На самом деле, об этом можно не говорить явно, поскольку это требование автоматически выполняется. По аналогии с тем, как было доказано, что в шестиугольной сети вершины $(0, 2n)$ и $(m, 2n)$ не могут перейти ни в какие другие кроме как друг в друга, здесь можно также проанализировать список смежности верхних вершин и сравнить его с другими вершинами.

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

#claim[
  Предположим, что, в нарушение базовых предположений о губковой сети, веса "сверху вниз" и "снизу вверх" в сети $"SN"$ совпадают. Предположим также, что в сети нет стоковых вершин. Пусть сеть треугольная или прямоугольная и, дополнительно, в случае треугольной сети количество строк четно ($n = 2k$), а в случае прямоугольной $m != n$. В данном случае сеть будет иметь еще один автоморфизм $Phi: Phi((i, j)) =$ \ $= (i, 2 ceil(n "/" 2) - j)$ и, соответственно, $Aut("SN") tilde.equiv quo(ZZ, 2 ZZ)$ в случае треугольной сети и $Aut("SN") tilde.equiv (quo(ZZ, 2 ZZ))^2 = D_2$ (вторая группа диэдра, полная группа симметрий прямоугольника) в случае прямоугольной сети.
]

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

== Фактор-сети

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

Понятие факторграфа, однако, применимо лишь к графам в их базовом понимании, а губковая сеть есть в первую очередь взвешенный граф. Если рассмотреть вершины $esq(u)$ и $esq(v)$ из определения @def:quotient-graph, то, в общем случае, может оказаться, что для них существует несколько разных $u$ и $v$, связанных ребрами в исходном графе, при этом эти ребра могут иметь разные веса. Какой будет вес у $(esq(u), esq(v))$? На этот вопрос можно отвечать по-разному. Мы введем сначала операцию, которая позволяет сделать фактор-сеть из любого отношения эквивалентности, а потом рассмотрим ее частный случай, обладающий более интересными свойствами.

// TODO: сделать что-нибудь с D, оно нам вообще надо?
#definition[
  Пусть $"RN"$ -- произвольная ресурсная сеть (возможно, с жадными вершинами), а "$~$", как и в определении @def:quotient-graph, произвольное отношение эквивалентности на вершинах соответствующего графа $G$. Определим *факторизованную ресурсную сеть* (*фактор-сеть*) $quo("RN", ~) eq.def (G', D', S')$ по отношению эквивалентности "$~$" как ресурсную сеть, где:
  // - Граф $G "/" ~$ -- факторграф графа $G$ по отношению $~$;
  // Пусть $u, v in V$ и, соответственно, $esq(u), esq(v) in quo(V, ~)$.
  - Ребра $E'$ и веса $w'$ графа $G'$ определяются следующим образом. \ $forall esq(u) in quo(V, ~), forall esq(v) in quo(V, ~)$:
    - $(exists u in esq(u) : (u, u) in E) <=> (esq(u), esq(u)) in E';$ тогда

    $w'((esq(u), esq(u))) = "avg"{w((u, u)) | (u, u) in E and u in esq(u)}.$

    Здесь $"avg" X$ есть среднее арифметическое элементов множества чисел $X$;

    - $(exists u in esq(u), exists v in esq(v) : (u, v) in E) <=> (esq(u), esq(v)) in E'$; тогда

    $
      w'((esq(u), esq(v))) = "avg"{
        w((u, v)) | (u, v) in E and u in esq(u) and v in esq(v)
      }.
    $ <nonum>

  - Функция эволюции динамической системы $S'$ определяется согласно правилам работы ресурсной сети (возможно, с жадными вершинами), соответствущей графу $G'$.
] <def:quotient-network>

Как можно видеть, так же, как и в случае обычного факторграфа, в при факторизации в ресурсной сети не появляется никаких "новых" ребер в том смысле что количество ребер в факторизованной сети не больше, чем в исходной. Отметим также, что данное определение не согласуется с определением обычного ориентированного факторграфа. Действительно, если представить себе некоторый граф $G$ без петель, в котором отождествлены смежные вершины $u$ и $v$, то в $quo(G, ~)$ появится петля $(esq(u), esq(u)) = (esq(v), esq(v))$. Напротив, если представить себе подобную ситуацию с ресурсной сетью $"RN"$, то новых петель в ходе факторизации не появится. Такая разница введена для того, чтобы различить разные по своей сути классы ребер в ресурсной сети с жадными вершинами: петли и все остальные ребра. Действительно, если бы мы разрешили отождествлять вершины без петель так, чтобы в результате получалась "жадная" вершина, это бы заметно изменило качественные свойства сети. Впрочем, мы будем рассматривать несколько иные ситуации, подпадающие под \ определение @def:ideal-quotient.

#definition[
  Пусть $"RN"$ -- произвольная ресурсная сеть (возможно, с жадными вершинами). Отношение эквивалентности на множестве вершин сети "$~$" назовем *идеальным* (и, соответственно, получившуюся фактор-сеть $quo("RN", ~)$ назовем *идеально факторизованной*), если $forall esq(u) in quo(V, ~)$, $forall esq(v) in quo(V, ~)$ выполняются следующие условия:
  - $forall u', u'' in esq(u) sp ((u', u') in E and (u'', u'') in E and w((u', u')) = w((u'', u'')))$;
  - $forall u', u'' in esq(u), forall v', v'' in esq(v) ((u', v') in E and (u'', v'') in E => $ \ $=> w((u', v')) = w((u'', v'')))$.

  !! Иначе говоря, всякий раз, когда в определении @def:quotient-network встречается выражение $"avg" X$ для некоторого $X$, $X$ есть одноэлементное множество.
] <def:ideal-quotient>

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

#claim[
  Пусть $J = {esq(v) | esq(v) in quo(V, ~) and abs(esq(v)) > 1 }$. Тогда если $forall esq(u) in J, forall esq(v) in J : esq(u) != esq(v) sp (forall u' in esq(u), forall v' in esq(v) sp "adj"_(G)(u') sect$ \ $sect "adj"_(G)(v') = varnothing)$, то выполнено второе условие из определения @def:quotient-network. Если, дополнительно, веса петель в каждом классе эквивалентности равны, то $quo("RN", ~)$ факторизуется идеально.
] <claim:simple_ideal>

Доказательство данного факта провести несложно: стоит заметить, что при выполнении условия из утверждения @claim:simple_ideal в исходном графе $G$ не окажется никакой пары ребер, ведущих из одного общего класса эквивалентности в другой общий класс эквивалентности, а значит условие на равенство весов ребер будет выполнено автоматически.

// cspell:disable-next-line
В качестве примера рассмотрим губковую сеть $"qn"_1$ ("$"qn"$" -- #strong[q]uotient #strong[n]etwork) с 2 строками и 4 столбцами с треугольной сеткой. Определим отношение эквивалентности на множестве вершин сети следующим образом. Отождествим 2 вершины, не имеющие общих смежных вершин, например, вершины $(0, 1)$ и $(3, 0)$, а остальные будут эквивалентны только себе. Для наглядности будем говорить об одноэлементных множествах сети как о самих элементах этих множеств. Так, вместо того, чтобы писать "${(0, 2)} in quo(V, ~)$", будем писать "$(0, 2) in quo(V, ~)$".

На @fig:qn_1_1 приведена данная сеть с начальным состоянием \ $q_0$ = #state_dict(("(0, 2)": 0, "(1, 2)": 30, "(2, 2)": 0, "(3, 2)": 0)) (остальные вершины имеют нулевое начальное состояние). Отождествленные вершины обведены красным. Данный рисунок является условным, поскольку никаких двух вершин в графе на самом деле нет, равно как и ребер, соединяющих эти вершины с другими. Такой способ изображения выбран потому, что в результате факторизации получившийся граф может не быть планарным, так что выбрать наглядное представление соответствующей сети может быть затруднительно. При данном способе отображения состояние "разделяется" отождествленными вершинами. На @fig:qn_1_2 показано состояние $"qn"_1$ в следующий момент времени. Вершина ${(0, 1), (3, 0)}$ содержит 5 единиц ресурса, так что на рисунке обе "вершины" содержат по 5 единиц ресурса.

#figure(
  caption: [Пример фактор-сети в момент времени $t = 0$],
  generated_image("qn_1/1")(),
) <fig:qn_1_1>

#figure(
  caption: [Та же сеть в момент времени $t = 1$],
  generated_image("qn_1/2")(),
) <fig:qn_1_2>

Поскольку в рассмотренной сети выполняются условия утверждения @claim:simple_ideal, то полученная факторизация сети идеальна. С точки зрения выбранного нами способа изображения это значит, что веса ребер на рисунке не меняются по сравнению с сетью до факторизации. Так, в исходной сети ребро $((1, 2), (0, 1))$ имело вес 5, значит и ребро $((1, 2), {(0, 1), (3, 0)})$ имеет вес 5, поэтому на приведенных рисунках соответствующее ребро имеет также вес 5.

== Губковые сети на цилиндре

#let eqcyl = $~_("cyl")$

Пусть дана некоторая сеть $"SN"$, удовлетворяющая базовым предположениям о губковой сети. Пусть $tilde(m) = m$, если сеть прямоугольная или шестиугольная и $tilde(m) = floor(m "/" 2)$, если сеть треугольная.
// Дополнительно, пусть $m$ -- четно, если сеть треугольная и шестиугольная.
Рассмотрим следующее отношение эквивалентности $eqcyl$ на множестве вершин сети $V$:
$
  u sp eqcyl v <=> cases(delim: "[",
    u = v\,,
    j_1 = j_2 and (i_1\, i_2 in {0, tilde(m)})\, #[где] (i_1, j_1) = u\, (i_2, j_2) = v.
  )
$

Будем называть $quo("SN", eqcyl)$ *губковой сетью на цилиндре*. Приведенную факторизацию можно рассматривать как помещение губковой сети на цилиндр: левый и правый края сети "склеиваются" в одну линию. Пример такой сети приведен на @fig:sn_on_cylinder_1. Как и прежде, вершины, которые были отождествлены \ (с какими-либо другими вершинами) обведены красным. Подчеркнем, что классов эквивалентности с числом элементов $> 1$ не 1, а 4: ${(0, 2), (3, 2)}$, ${(0, 1), (3, 1)}$, ${(0, 0), (3, 0)}$ и, наконец ${(0, -1), (3, -1)}$.

#figure(
  caption: [Губковая сеть с треугольной стекой, помещенная на цилиндр],
  // placement: bottom,
  generated_image("cylinder_triangular_1/plot")()
) <fig:sn_on_cylinder_1>

#lemma[
  Губковая сеть $quo("SN", eqcyl)$ факторизована идеально, если она удовлетворяет базовым предположениям о губковой сети.
] <lem:ideal_cylinder>

Для доказательства данной леммы воспользуемся следующим фактом.

#lemma[
  Пусть $"RN"$ -- произвольная ресурсная сеть, а $~$ -- такое отношение эквивалентности на $V$, что сеть $quo("RN", ~)$ факторизована идеально. Пусть также внутри одного класса эквивалентности:

  - совпадают веса всех ребер, т.е. $forall esq(u) in quo(V, ~) sp forall u_1, u_2, u'_1, u'_2 in esq(u) :$ \ $u_1 != u_2  and u'_1 != u'_2 sp ((u_1, u_2) in E and (u'_1, u'_2) in E => w((u_1, v_1)) =$ \ $= w((u'_1, u'_2)))$;
  - совпадают веса всех петель.

  !! В таком случае, любое измельчение разбиения $quo(V, ~)$ также факторизует сеть идеально. Под измельчением мы понимаем такое отношение эквивалентности $~'$ на $V$, что $u ~' v => u ~ v$.
] <lem:subpartition>

#proof[#fli[
    #let esqt = esq.with(eqv_rel: $~'$)
    Рассмотрим произвольные классы $esqt(u)$ и $esqt(v)$ и произвольные вершины внутри этих классов $u', u'' in esqt(u)$, $v', v'' in esqt(v)$.

    - Поскольку веса всех петель внутри $esq(u)$ и $esq(v)$ совпадали, то совпадут они и на любом подмножестве $esq(u)$ и $esq(v)$ соответственно, в частности, на $esqt(u)$ и $esqt(v)$.
    - Рассмотрим теперь ребра $(u', v')$ и $(u'', v'')$, полагая, что $u' != v' and$ \ $and u'' != v''$, а $esqt(u) != esqt(v)$.
      - Если $esq(u) != esq(v)$, то $w((u', v')) = w((u'', v''))$ в силу определения @def:ideal-quotient, примененного к отношению $~$.
      - Положим, что $esq(u) = esq(v)$. Тогда $w((u', v')) = w((u'', v''))$ в силу условия леммы.

    Таким образом, все требования для идеальной факторизации сети $quo("RN", ~')$ выполнены.
  ]
]

#proof[леммы @lem:ideal_cylinder][
  #let eqlev = $~_"level"$
  Рассмотрим отношение эквивалентности $eqlev$, которое отождествляет все вершины уровня $V_i$ между собой, т.е. \ $(i_1, j_1) sp eqlev (i_2, j_2) <=> j_1 = j_2$. С одной стороны, все ребра, связывающие классы эквивалентности по $eqlev$ являются ребрами одного типа одновременно: либо "сверху вниз", либо "снизу вверх". С другой стороны, все ребра внутри одного уровня -- горизонтальные. Учитывая вышесказанное, заключим, что если сеть удовлетворяет базовым предположениям о губковой сети, то выполняются условия леммы @lem:subpartition. Очевидно, что отношение $eqcyl$ является измельчением разбиения $eqlev$, а значит, $quo("SN", eqcyl)$ факторизуется идеально.
]

// Помещение сети на цилиндр может быть и проинтерпретировано с помощью замощений плоскости. Положим,

// Очевидно, что помещение

Отметим, что у сети с треугольной сеткой на @fig:sn_on_cylinder_1 число столбцов до факторизации было четным. Для сравнения приведем сеть с треугольной сеткой и нечетным количеством столбцов (@fig:sn_on_cylinder_bad). Может показаться, что -- в отличие от случая с исходной сетью -- сеть на @fig:sn_on_cylinder_1 более симметрична, чем сеть на @fig:sn_on_cylinder_bad. Действительно, это так.

#figure(
  caption: [Губковая сеть с треугольной стекой и нечетным числом столбцов на цилиндре],
  generated_image("cylinder_triangular_2/plot")(),
) <fig:sn_on_cylinder_bad>

#theorem[
  Пусть $"SN"$ -- губковая сеть с числом столбцов $m > 1$. Пусть также, снова, $tilde(m) = m$, если сеть прямоугольная или шестиугольная и $tilde(m) = floor(m "/" 2)$, если сеть треугольная.

  - Если сеть прямоугольная, то $Aut(quo("SN", eqcyl)) tilde.equiv D_(tilde(m) - 1)$, где $D_k$ -- $k$-ая группа диэдра.
  - Если сеть треугольная или шестиугольная, а количество столбцов четно, то $Aut(quo("SN", eqcyl)) tilde.equiv D_(tilde(m) - 1)$.
  - Если сеть треугольная или шестиугольная, но количество столбцов нечетно, то $Aut(quo("SN", eqcyl)) tilde.equiv quo(ZZ, 2 ZZ)$.

] <th:cylinder-sym>

#proof[
  #fli[
    Наша логика будет во многом повторять ту, что использовалась в теореме @th:sym. Для начала, предположим, что сеть прямоугольная или же треугольная с четным количеством столбцов. Рассмотрим снова уровни $V_i$ сети $quo("SN", eqcyl)$. На сей раз $Gen_G (V_i)$ представляют из себя не простые пути, а простые циклы на $tilde(m) - 1$ вершине. Известно, что группа симметрий простого цикла на $tilde(m) - 1$ вершине есть $D_(tilde(m) - 1)$. Такая группа соответствует $Aut(Gen_G (V_i))$ для каждого $i$. При попытке "соединить" указанные слои мы снова приходим к выводу, что

    $
      forall Phi_i in Aut(Gen_G (V_i)) sp exists! Phi_(i-1) in Aut(Gen_G (V_(i-1))): \
      Phi_i union.sq Phi_(i-1) in Aut(Gen_G (V_i union V_(i-1))).
    $ <nonum>

    Так мы проходимся по каждой паре соседствующих слоев и устанавливаем, что, вообще, для каждого $i$ каждая симметрия $Phi_i in Aut(Gen_G (V_i))$ однозначно определяет симметрию всего графа $G$. Стало быть, $Aut(quo("SN", eqcyl)) tilde.equiv D_(tilde(m) - 1)$.

    Если же сеть треугольная, но количество столбцов нечетно (например, как на @fig:sn_on_cylinder_bad), то мы сталкиваемся с тем, что количество вершин на уровне $V_i$ зависит, вообще говоря, от четности $i$: на четных уровнях вершин на одну больше, чем на нечетных. Возникает асимметрия при нечетном $i$: вершина ${(0, i), (tilde(m), i)}$ оказывается смежной сразу с тремя вершинами уровня $i-1$: ${(0, i-1), (tilde(m)-1, i-1)}, (1, i-1)$ и $(tilde(m)-2, i-1)$. Остальные же вершины уровня $i$ имеют в соседях только 2 вершины из уровня $i-1$. Очевидно, что в данном случае любой автоморфизм графа $Gen_G (V_i union V_(i-1))$ должен оставлять эту уникальную вершину на месте. Таких автоморфизма существует ровно 2: тождественный и отражение, которое, собственно, и оставляет эту вершину на месте. Можно убедиться, что при "склеивании" уровней дальше указанное отражение все так же остается автоморфизмом сети. Таким образом, $Aut(quo("SN", eqcyl)) tilde.equiv quo(ZZ, 2 ZZ)$.

    В случае шестиугольной сети доказательство проходит образом, аналогичным доказательству теоремы @th:sym с той разницей, что теперь вместо $quo(ZZ, 2 ZZ)$ фигурирует $D_(tilde(m) - 1)$.
  ]
]

Отметим, что понимание губковых сетей на цилиндре как буквально сетей, помещенных на цилиндр, позволяет продолжить нашу геометрическую аналогию с замощением плоскости. Напомним, что губковую сеть можно представить себе как часть регулярного замощения плоскости $cal(F)$, а отображение, переводящее губковую сеть в подмножество $cal(F)$ мы называли $cal(I)$. Теперь же мы можем поступить иначе: рассматривать не регулярные разбиения плоскости, а регулярные разбиения (бесконечного) цилиндра. Не составит труда, в таком случае, для губковой сети на цилиндре (при условии, что в исходной сети, если она была треугольная или шестиугольная, число столбцов было четно) указать другое соответствие $cal(I)'$, переводящее граф сети в подмножество разбиения на цилиндре. На сей раз, на множестве $"Im"(cal(I)')$ часть симметрий сохраняется, а именно движения "вправо" и "влево" вместе с отражениями относительно некоторых плоскостей, проходящих через ось цилиндра. Указанные симметрии и образуют группу $D_k$. Таким образом, губковые сети на цилиндре намного более похожи на регулярные замощения плоскости с точки зрения симметрий нежели обычные губковые сети. Можно добавить, что максимальное сходство проявилось бы, если бы мы рассматривали сети на торе, однако в таком случае мы потеряли бы представление о "верхних" и "нижних" вершинах, что выходит за рамки нашего рассмотрения.

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

#claim[
  Графы губковых сетей, помещенных на цилиндр, планарны, при условии, что в исходной губковой сети, если она была треугольная или шестиугольная, число столбцов было четно.
]

#proof[
  #fli[
    Для начала отметим, что губковая сеть на цилиндре суть ограниченное множество, если рассматривать ее как часть замощения (т.е.~$"Im"(cal(I)')$). Таким образом, достаточно рассмотреть только конечный цилиндр, т.е. фигуру, гомеоморфную квадрату со склеенными сторонами: #box[$C = [0, 1]^2 \/ {forall y in [0, 1] med (0, y) med ~ med (1, y)}$]. Однако такой цилиндр является, в свою очередь, гомеоморфным "кольцу" #box[$R = {(r cos phi, r sin phi) | phi in [0, 2 pi), r in [1, 2]}$]. Очевидно, что вложение графа внутрь этого кольца без пересечения ребер делает его планарным (поскольку данное кольцо есть просто подмножество вещественной плоскости). Значит и исходный граф губковой сети на цилиндре был планарным.
  ]
]

== Связь с динамическими системами

// TODO дополнить
Мы хотели бы связать симметрии ресурсных сетей как графов с некоторым симметричным поведением их как динамических систем. Можно смотреть на ресурсные сети как на отображения $S : RR_+^nu -> RR_+^nu$, где $nu$ -- количество вершин в сети. В установлении того, какие симметрии наличествуют у ресурсных сетей помогает следующая теорема.

#theorem[
  Пусть $"RN"$ -- ресурсная сеть с $nu$ вершинами. Будем считать, что в сети зафиксирована некоторая нумерация вершин, т.е. $V = {v_i}_(i = 1)^nu$. Пусть $Phi$ -- автоморфизм $"RN"$ как графа (определение @def:rn_aut). В таком случае $Phi$ индуцирует ее автоморфизм $Phi' : RR_+^nu -> RR_+^nu$ как динамической системы следующим образом: $forall q in RR_+^nu sp Phi'(q)_i eq.def q_j$, где $j : Phi(v_j) = v_i$.
] <th:rn_sym_with_dyn>

#proof[
  #fli[
    Отметим, сначала, что отображение $Phi'$ определено корректно, поскольку $Phi$ -- биекция на множестве вершин графа. Далее, заметим, что любой автоморфизм графа индуцирует некоторую перестановку его вершин. Назовем ее $sigma$, тогда $sigma(i) eq.def j : Phi(v_i) = v_j $.

    // Пусть граф исходной сети -- $G$, тогда скажем, что граф сети, полученной после перенумерации вершин, есть $G_"perm"$. Применив перестановку $sigma$ к строкам и столбцам матрицы смежности $R$ получим матрицу смежности $sigma(R)$ графа $G_"perm"$. Поскольку стохастическую матрицу от матрицы пропускной способности отличает лишь сумма элементов каждой строки, то стохастическая матрица $G_"perm"$ есть $R'_"perm" = sigma(R')$.

    Для произвольного вектора $v$ будем обозначать соответствующую перестановку его элементов за $sigma(v)$, для произвольной матрицы $A$ будем обозначать одновременную перестановку ее строк и столбцов снова за $sigma(A)$. Можно доказать, что для произвольных векторов $v_1, v_2 in RR^(nu times 1)$, матриц $A, B in RR^(nu times nu)$ верно:

    - $sigma(v_1^T v_2) = sigma(v_1)^T sigma(v_2)$;
    - $sigma(A v_1) = sigma(A) sigma(v_1)$;
    - $sigma(A B) = sigma(A) sigma(B)$;
    - $sigma(v_1 + v_2) = sigma(v_1) + sigma(v_2)$;
    - $sigma(A dot.circle B) = sigma(A) dot.circle sigma(B)$;
    - $sigma(min{A, B}) = min{sigma(A), sigma(B)}$.

    В таком случае, для произвольного состояния системы $q$, с использованием определения @def:flow-matrix, получим:

    $
      sigma(F(q)) = sigma(min{R' dot.circle (bold(1) dot q), R}) = min{
        sigma(R') dot.circle (bold(1) dot sigma(q)), sigma(R)
      }.
    $ <nonum>

    Поскольку $Phi$ -- автоморфизм графа, то перестановка $sigma$ оставляет на месте матрицу смежности графа, т.е. $sigma(R) = R$. Более того, поскольку стохастическая матрица является функцией только матрицы смежности, то $sigma(R') = R'$. Тогда

    $
      sigma(F(q)) = min{
        sigma(R') dot.circle (bold(1) dot sigma(q)), sigma(R)
      } = \
      = min{R' dot.circle (bold(1) dot sigma(q)), R} = F(sigma(q)).
    $ <nonum>

    Используем теперь формулу для функции эволюции ресурсной сети @eq:S:

    $
      sigma(S(q)) = sigma(q - (F(q) dot bold(1))^T + bold(1)^T dot F(q)) =\
      = sigma(q) - (F(sigma(q)) dot bold(1)^T + bold(1)^T dot F(sigma(q))) = S(
        sigma(q)
      ).
    $ <nonum>

    Последняя формула и является переформулировкой искомого. Таким образом, согласно определению @def:dyn_syst_aut, теорема доказана.

    // матрицы смежности $R$ (обозначим ее $Phi(R)$), при этом $Phi(R)$ является (взвешенной) матрицей смежности графа, полученного перенумерацией вершин, соответствующей $Phi$.
  ]
]

Обозначим группу автоморфизмов ресурсной сети $"RN"$ как графа $Aut_"graph" ("RN")$, а группу автоморфизмов ее как динамической системы -- $Aut_"dyn" ("RN")$.

#block(breakable: false)[
  #corollary[
    Для произвольной ресурсной сети $"RN"$ верно

    $ Aut_"graph" ("RN") <= Aut_"dyn" ("RN"). $ <nonum>
  ]
]

#remark[
  Из вышесказанного еще не следует, что симметрии ресурсной сети как динамической системы ограничиваются симметриями соответствующего графа. Для получения ответа на этот вопрос требуется проведение дополнительного исследования.
]

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

#claim[
  Пусть дана произвольная динамическая система \ $cal(S) = (X, S)$, $Aut(cal(S))$ -- группа ее автоморфизмов, $x in X$ -- произвольное состояние, а $Stab(x)$ -- стабилизатор состояния $x$ относительно действия группы $Aut(cal(S))$ на $X$, т.е. $Stab(x) = {Phi in Aut(cal(S)) | Phi(x) = x}$. Тогда

  $
    forall n in NN sp Stab(x) subset Stab(S^n (x)).
  $ <nonum>

  !! Иначе говоря, траектория, соответствующая начальному состоянию $x$ является целиком "самосимметричной", если начальное состояние было "самосимметричным".
] <claim:sym_traj>

#proof[
  Возьмем произвольную $Phi in Stab(x)$, тогда $Phi(S(x)) = S(Phi(x)) = S(x)$, значит $Stab(x) subset Stab(S(x))$. Аналогичным образом доказывается, что $Stab(S(x)) subset Stab(S^2 (x))$. И вообще, по индукции доказывается $forall n in NN sp Stab(S^n (x)) subset Stab(S^(n+1) (x))$, из чего и следует искомое.

]
// С другой стороны, если $Phi in Stab(S(x))$, то $Phi(S(x)) = S(x)$ и одновременно $Phi(S(x)) = S(Phi(x))$, следовательно $$

#remark[
  Заметим, что обратное включение в утверждении @claim:sym_traj, в общем случае, неверно. Это зависит от того, является ли $S$ биекцией. В литературе по эргодической теории (например, в @Walters2000) в определении динамической системы требуется, чтобы $S$ была биекцией. К сожалению, функция эволюции ресурсной сети не является биективной. Более того, она не является сюръективной. Например, в сети на @fig:basic_network_1 невозможно указать состояние, при действии на которое функции $S$ получится $(10, 0, 0)$. В некоторых случаях $S$ не является и инъективной. Например, в некоторой окрестности нуля функция $S$ линейна, но при этом возможны такие топологии графа ресурсной сети, что стохастическая матрица оказывается вырожденной. Тогда $S$ будет неинъективна.

  // #figure(
  //   caption: [Ресурсная сеть, функция эволюции которой не является инъективной],
  //   generated_image("noninjective_network/plot")(width: 35%)
  // ) <fig:noninjective_network>
]

В качестве примера, когда стабилизатор "расширяется" под действием $S$, приведем следующую динамическую систему $cal(S)$. Пусть $X$ -- множество конечных последовательностей из натуральных чисел. Например, $(1, 4, 2) in X$ или же $(3, 3, 7, 4, 5) in X$. Пусть $S$ "забывает" последний элемент последовательности, то есть $S : (x_1, x_2, ..., x_(n-1), x_n) arrow.bar (x_1, x_2, ..., x_(n-1))$, а $S((x_1)) = (x_1)$. Можно показать, что любой автоморфизм $Phi$ данной динамической системы однозначно определяется набором функций ${f_i}_(i = 1)^infinity$, где $f_i : NN^i -> NN$, а $Phi : (x_1, x_2, ..., x_n) |->$ \ $|-> (f_1 (x_1), f_2 (x_1, x_2), ..., f_n (x_1, ..., x_n))$. Рассмотрим произвольный элемент \ $a in X, a = (a_1, ..., a_k)$. Каждый автоморфизм $Phi_a in Stab(a)$ характеризуется тем, что для него $forall i in overline(1\, k) sp f_i (a_1, ..., a_i) = a_i$, дополнительных ограничений на $f_i$ не накладывается. Образ $a$ под действием $S$ суть $S(a) = (a_1, ..., a_(k-1))$. Повторяя приведенные выше рассуждения получим, что $Phi_S(a) in Stab(S(a)) : forall i in overline(1\, k-1) sp f_i (a_1, ..., a_i) = a_i$. Очевидно, что $exists Phi in Stab(S(a)) : Phi in.not Stab(a)$, например $Phi : (x_1, ..., x_(k-1), x_k, ..., x_n) |->$ \ $ |-> (x_1, ..., x_(k-1), phi(x_k), ..., x_n)$, где $phi$ -- некоторая нетривиальная биекция $NN$ в себя: $phi(a_k) != a_k$. Более того, $Stab(a) subset Stab(S(a)) subset ... subset Stab(S^(k-1) (a))$, и здесь все включения являются строгими. Можно также видоизменить данный пример так, чтобы образовывалась бесконечная все расширяющаяся цепочка $Stab(a) subset Stab(S(a)) subset ...$ и чтобы

$
  limits(union.big)_(i=0)^infinity Stab(S^i (a)) = Aut(cal(S)).
$ <nonum>

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

#remark[
  Покуда это не вызовет недопониманий, будем говорить о группе $Aut_"graph" ("RN")$ одновременно и как о действующей на граф сети, и как о действующей на динамическую систему.
]

#let state1 = state_dict((
  "(0, 2)": 8,
  "(1, 2)": 20,
  "(2, 2)": 0,
  "(3, 2)": 20,
  "(4, 2)": 8,
))

Приведем теперь пример такой сети $"SN"$ и такого состояния $q^0$, что $Stab(q^0) != {id}$ (@fig:sponge_symmetrical_sim).

#figure(
  caption: [Некоторая губковая сеть и ее начальное состояние \ $q^0 = #state1$],
  placement: top,
  generated_image("sponge_symmetrical_sim/1")(width: 80%),
) <fig:sponge_symmetrical_sim>

Согласно теореме @th:sym, $Aut_("graph")("SN") = {id, "flip"},$ где $"flip"$ -- отражение сети вдоль вертикальной оси. Несложно видеть, что $q^0$ является самосимметричным в том смысле, что $Stab(q^0) = Aut_("graph")("SN")$. Исходя из утверждения @claim:sym_traj, данная симметрия сохранится и под действием динамической системы в дальнейшем.

#figure(
  caption: [Та же губковая сеть, состояние в момент времени $t = 4$],
  placement: top,
  generated_image("sponge_symmetrical_sim/2")(width: 80%),
) <fig:sponge_symmetrical_sim_2>

#let state2 = state_dict((
  "{(0, 3), (6, 3)}": 12,
  "(1, 3)": 0,
  "(2, 3)": 12,
  "(3, 3)": 0,
  "(4, 3)": 12,
  "(5, 3)": 0,
))

#figure(
  caption: [Начальное состояние губковой сети на цилиндре],
  placement: top,
  generated_image("sponge_symmetrical_2_sim/1")(width: 80%),
) <fig:sponge_symmetrical_2_sim_1>

Так, на @fig:sponge_symmetrical_sim_2 приведено состояние сети после действия на $q^0$ системы $S$ 4 раза, т.е. в момент времени $t = 4$. Можно видеть, что симметрия сохранилась.

#pagebreak()

Обыкновенные губковые сети, как было сказано, обладают довольно небольшим количеством симметрий. Более интересные результаты можно получить, если рассмотреть губковые сети на цилиндре. На @fig:sponge_symmetrical_2_sim_1 приведен пример такой сети с прямоугольной сеткой и начальным состоянием

$ q^0 = #state2. $ <nonum>

В данном случае стабилизатор порождается отражением (любым) и поворотом цилиндра на $pi\/3$, т.е. смещением всех вершин сети на 2 позиции вправо.

На @fig:sponge_symmetrical_2_sim_2 показана сеть в момент времени $t = 3$. Можно видеть, что у состояния тот же стабилизатор.

#figure(
  caption: [Та же губковая сеть, состояние в момент времени $t = 3$],
  generated_image("sponge_symmetrical_2_sim/2")(width: 100%),
) <fig:sponge_symmetrical_2_sim_2>

= ЗАКЛЮЧЕНИЕ <nonum>

Нами были исследованы симметрии губковых сетей и связи между автоморфизмами графов и динамических систем ресурсных сетей, порождающихся этими графами. С одной стороны, мы установили, что несмотря на регулярность, губковые сети теряют много своих симметрий относительно замощений плоскости, их порождающих. Вместе с тем было дано полное описание групп автоморфизмов губковых сетей (в том числе и в случае, когда "верх" и "низ" симметричны друг относительно друга). Было введено понятие факторизации ресурсных сетей и исследованы базовые ее свойства: в каких ситуациях сеть факторизуется идеально, а в каких нет? С помощью факторизации мы смогли из обыкновенных губковых сетей строить губковые сети на цилиндре, обладающие намного большим набором симметрий. Группы автоморфизмов таких сетей также были описаны полностью. Наконец, мы установили, что каждая симметрия графа ресурсной сети порождает симметрию ее как динамической системы. Полученные утверждения можно применять для облегчения моделирования и уменьшения размера анализируемой сети.

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

- При данных параметрах сети (столбцы, строки, вес всех типов ребер), каково минимальное количество ресурса, которое может быть помещено в верхние вершины так, чтобы ресурс дотек до стоковых вершин? Каково должно быть распределение этого ресурса?
- При данном начальном распределении ресурса в верхних вершинах, какую форму будет иметь "след" данного ресурса в пределе, если ресурса не хватит на то, чтобы покрыть все "потребности" жадных вершин? Какова зависимость ширины и глубины следа от параметров сети?

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

//  функционирование губковых сетей с

#[
  #let nbsp = sym.space.nobreak

  // HAHAHA, that's a dirty hack, but works in simple cases
  #let re = regex(`#([\w\d\-_]+)\[(.+)\]`.text)
  #show re: it => {
    let (func, text) = it.text.match(re).captures
    eval("#" + func + "[" + text + "]", mode: "markup")
  }

  #let re = regex(`(\d+)–(\d+)`.text)
  #show re: it => {
    let (l, r) = it.text.match(re).captures
    [#nbsp#box[#l–#r]]
  }

  #set par(hanging-indent: -0.95cm)

  // #show par: it => {
  //   v(0.6em)
  //   it
  // }

  #bibliography(
    "../literature/sn_literature.bib",
    title: [СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ],
    style: "../literature/gost-r-7-0-5-2008-numeric.csl",
  )
]

= ПРИЛОЖЕНИЕ А <nonum>

Ниже представлены примеры функционала, реализованного в библиотеке `sponge-networks` (обозначается в коде как `sn`).

#figure(
  caption: [Пример создания ресурсной сети из матрицы смежности с помощью модуля `networkx`, проведения одной итерации симуляции и получения результата в виде svg-изображения],
  code(```python
  basic_network = sn.ResourceNetwork[int](
      nx.from_numpy_array(
          np.array(
              [
                  [0, 3, 1],
                  [4, 1, 0],
                  [2, 2, 0],
              ]
          ),
          create_using=nx.DiGraph,
      )
  )
  sim1 = basic_network.run_simulation([8, 1, 0], n_iters=1)
  img2 = basic_network.plot_with_states(
    sim1, max_node_width=0.6, scale=1.1
  )[0]
  img2
  ```),
) // <lst:basic_network>

#figure(
  caption: [Пример создания губковой сети на цилиндре из обыкновенной #h(2em) губковой сети и получение svg-изображения этой сети],
  code(```python
  nw = sn.build_sponge_network(
      grid_type="hexagonal", n_cols=4, n_rows=2,
      layout={
          "weights_sink_edge": 1,
          "weights_loop": 1,
          "weights_horizontal": 2,
          "weights_up_down": 5,
          "weights_down_up": 1,
          "generate_sinks": True,
      },
      visual_sink_edge_length=0.7
  )
  (sn
      .quotient_sponge_network_on_cylinder(nw)
      .quotient_network
      .plot(scale=1.)
  )
  ```),
)
