В.А. Овчинников, Г.С. Иванова
МЕТОДИКА ФОРМАЛЬНОГО СИНТЕЗА
КОМБИНИРОВАННЫХ СТРУКТУР ДАННЫХ
ДЛЯ ПРЕДСТАВЛЕНИЯ ГРАФОВ
На примере организации хранения множества ребер гиперграфа и их
образов относительно предиката инцидентности рассмотрена методика синтеза комбинированных многоуровневых структур данных. <...> Математическими моделями базовых и производных структур данных являются ориентированные графы. <...> Модель синтезированной
структуры формируется в результате выполнения операции объединения модели исходной структуры и модели отношений, обеспечивающих эффективную реализацию заданных операций. <...> Формальный синтез комбинированных структур базируется на
анализе данных, отношений между ними и набора выполняемых операций. <...> Целью синтеза является получение такой структуры, которая
обеспечивала бы высокую эффективность выполнения заданных над
данными операций. <...> Возможность формального синтеза обеспечивается наличием библиотеки моделей базовых и производных структур данных, а также
процедур отношений и предикатов (биективного, сюръективного и
инъективного отношений, предиката принадлежности элементов подмножества множеству и т. д.) <...> . При автоматизированном синтезе пользователю необходимо задать имена, размеры множеств, отношения
между ними и имена моделей базовых или производных структур для
их хранения. <...> Пусть необходимо построить структуру для представления множества ребер и их образов гиперграфа, заданного в форме H(X, <U,
W>, ГX, ГU). <...> Над гиперграфом выполняются операции поиска ребер
с максимальным весом, удаления вершин и «пустых» ребер, т. е.
тех, у которых |Гu| = 0. <...> При удалении вершин и «пустых» ребер порядок их записи необходимо сохранять. <...> 2012
135
С учетом сказанного выше множество ребер гиперграфа U целесообразно представить в виде двусвязного списка LD [1]. <...> Также в виде двусвязных списков {Lj / j = 1, m} представим множества вершин
Xj = Гuj, инцидентных каждому ребру uj (рис. <...> Двусвязный список двусвязных <...>