PQ-дерево

Граф (a) и его PQ-дерево (b)

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

Использование

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

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

Статьи

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Публикация
• Approximate search for known gene clusters in new genomes using PQ-trees

Примечания

Шаблон:Деревья (структуры данных)