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

В статье рассматривается размер памяти, необходимый и достаточный для хранения графа из класса неориентированных корневых упорядоченных связных графов как нумерованных, так и ненумерованных. Введение содержит основные определения и постановку задачи. Граф корневой, если одна из вершин выделена и названа корнем. Граф упорядоченный, если для каждой вершины все инцидентные ей рёбра линейно упорядочены. Граф нумерованный, если все его вершины помечены различными идентификаторами, в частности, пронумерованы целыми числами от 0 до n -1, где n число вершин графа. Два неориентированных корневых упорядоченных графа G и G` считаются слабо изоморфными, если существует взаимно-однозначное соответствие вершин такое, что: 1) соответствующие вершины имеют одинаковые степени, 2) рёбра ab из графа G и a`b` из графа G` , инцидентные соответствующим вершинам a и a` и имеющие в этих вершинах одинаковые номера, ведут в соответствующие вершины b и b` , 3) корни соответствуют друг другу. Для нумерованных графов при изоморфизме дополнительно требуется совпадение номеров соответствующих вершин. Графы рассматриваются с точностью до слабого изоморфизма. Показано, что память, необходимая и достаточная для хранения любого графа из указанного класса, имеет размер Q( mlogn ) для нумерованных графов, Q( n +( m - n +1) logn ) для ненумерованных графов с числом вершин n и числом рёбер m , и Q( n² logn ) для графов без кратных рёбер и петель с числом вершин n . Также показано, что память, достаточная для хранения последовательности рёбер длины O ( n ) или остова графа, имеет размер O ( nlog ( n D)) или O ( nlog D), соответственно, где D максимальная степень вершины.

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

1. О.Оре. Теория графов. М., Наука, 1968.

2. F. Harary and E. M. Palmer. Graphical Enumeration, Academic Press, NY, 1973.

3. The On-Line Encyclopedia of Integer Sequences. Catalan numbers. https://oeis.org/A000108. Дата доступа 10.02.2017.

4. J. H. Conway and R. K. Guy. The Book of Numbers, New York: Springer-Verlag, 1995.

5. F. Bergeron, G. Labelle and P. Leroux. Combinatorial Species and Tree-like Structures, EMA vol.67, Cambridge, 1998.

6. R. Dutton, and R. Brigham. Computationally Efficient. Bounds for the Catalan Numbers. Europ. J. Combinatorics, vol.7, 1986.

7. Решение математики онлайн, http://math24.biz/. Дата доступа 10.02.2017.