PQ дерево

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

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

Статьи

  • Booth, Kellogg S. and Lueker, George S. [{{{url}}} Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms] // Journal of Computer and System Sciences. — 1976. — Т. 13. — № {{{issue}}}. — С. 335–379.
  • Shih, Wei-Kuan and Hsu, Wen-Lian A new planarity test // Theoretical Computer Science. — 1999. — Т. 223. — № {{{issue}}}. — С. 179–191.
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home