Размер памяти для хранения упорядоченного корневого графа

В статье рассматривается размер памяти, необходимый и достаточный для хранения графа из класса неориентированных корневых упорядоченных связных графов как нумерованных, так и ненумерованных. Введение содержит основные определения и постановку задачи. Граф корневой, если одна из вершин выделена и названа корнем. Граф упорядоченный, если для каждой вершины все инцидентные ей рёбра линейно упорядочены. Граф нумерованный, если все его вершины помечены различными идентификаторами, в частности, пронумерованы целыми числами от $0$ до $n-1$, где $n$ — число вершин графа. Два неориентированных корневых упорядоченных графа $G$ и $G'$ считаются слабо изоморфными, если существует взаимно-однозначное соответствие вершин такое, что: 1) соответствующие вершины имеют одинаковые степени, 2) рёбра $ab$ из графа $G$ и $a'b'$ из графа $G'$, инцидентные соответствующим вершинам $a$ и $a'$ и имеющие в этих вершинах одинаковые номера, ведут в соответствующие вершины $b$ и $b'$, 3) корни соответствуют друг другу. Для нумерованных графов при изоморфизме дополнительно требуется совпадение номеров соответствующих вершин. Графы рассматриваются с точностью до слабого изоморфизма. Показано, что память, необходимая и достаточная для хранения любого графа из указанного класса, имеет размер $\Theta(m\log n)$ для нумерованных графов, $\Theta(n+(m-n+1)\log n)$ для ненумерованных графов с числом вершин $n$ и числом рёбер $m$, и $\Theta(n^2\log n)$ для графов без кратных рёбер и петель с числом вершин $n$. Также показано, что память, достаточная для хранения последовательности рёбер длины $O(n)$ или остова графа, имеет размер $O(n\log(n\Delta))$ или $O(n\log \Delta)$, соответственно, где $\Delta$ — максимальная степень вершины.