Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2017-29(2)-1

Полный текст:

Аннотация

В статье рассматривается размер памяти, необходимый и достаточный для хранения графа из класса неориентированных корневых упорядоченных связных графов как нумерованных, так и ненумерованных. Введение содержит основные определения и постановку задачи. Граф корневой, если одна из вершин выделена и названа корнем. Граф упорядоченный, если для каждой вершины все инцидентные ей рёбра линейно упорядочены. Граф нумерованный, если все его вершины помечены различными идентификаторами, в частности, пронумерованы целыми числами от 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( n2 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.


Для цитирования:


Бурдонов И.Б., Косачев А.С. Размер памяти для хранения упорядоченного корневого графа. Труды Института системного программирования РАН. 2017;29(2):7-26. https://doi.org/10.15514/ISPRAS-2017-29(2)-1

For citation:


Burdonov I.B., Kossatchev A.S. Size of the memory for storage of ordered rooted graph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(2):7-26. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(2)-1

Просмотров: 69


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)