PQ-дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

PQ дерево — структура данных для представления группы перестановок. Это корневое планарное дерево. Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо P, либо Q. Вершины с пометкой Q имеют по крайней мере 3 потомка, а вершины с пометкой P имеют по крайней мере 2 потомка. В PQ дереве разрешается как угодно переставлять потомков вершины с пометкой P и обращать порядок потомков вершины с пометкой Q.

PQ-дерево, описывающее вложенный список
[1 (2 3 4) 5]

PQ деревья используются для поиска перестановок, ограничения на которые становятся известны постепенно, одно за другим. Такие задачи возникают при воссоздании ДНК и проверке планарности графа.

Статьи[править | править вики-текст]

  • Booth, Kellogg S. and Lueker, George S. (1976). «Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms». Journal of Computer and System Sciences 13: 335–379.