Сборники трудов ИСП РАН


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

И.Б. Бурдонов (ИСП РАН, Москва, Россия)
А.С. Косачев (ИСП РАН, Москва, Россия)

Аннотация

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

Ключевые слова

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

Издание

Труды Института системного программирования РАН, том 29, вып. 2, 2017, стр. 7-26.

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

DOI: 10.15514/ISPRAS-2017-29(2)-1

Полный текст статьи в формате pdf Вернуться к содержанию тома