Определение древовидной ширины

Дадим точное определение класса графов, предназначенного для обобщенного представления деревьев. В основу определения заложены два соображения.

Во-первых, нам нужны графы, которые можно разложить на несвязанные части удалением небольшого количества узлов; это позволит реализовать динамические алгоритмы того типа, о котором говорилось ранее.

Во-вторых, мы хотим формализовать интуитивное представление о «древовидных» изображениях графов наподобие изображенного на рис. 10.5, b.

Видно, что G на самом деле состоит из десяти переплетенных треугольников; и семь из десяти треугольников обладают тем свойством, что при их удалении остаток G распадется на несвязанные части, рекурсивно обладающие той же структурой из сцепленных треугольников.

Еще три треугольника прикреплены в крайних точках, и их удаление можно сравнить с удалением листовых узлов из дерева.

Итак, граф G древовиден, если рассматривать его не как состоящий из двенадцати узлов, как обычно, а как состоящий из десяти треугольников.

И хотя G очевидным образом содержит много циклов, при рассмотрении на уровне этих десяти треугольников циклов словно бы и нет; на этом основании граф наследует многие полезные декомпозиционные свойства дерева.

Древовидная структура из треугольников должна представляться так, чтобы каждый треугольник соответствовал узлу дерева, как показано на рис. 10.5, c. Интуитивно понятно, что дерево на рисунке соответствует графу (каждый узел дерева представляет один из треугольников).

Однако обратите внимание на то, что одни узлы графа присутствуют в разных треугольниках — даже в треугольниках, не являющихся смежными в структуре дерева, и некоторые ребра соединяют узлы треугольников, находящихся очень далеко в древовидной структуре, — например, центральный треугольник соединяется ребрами с узлами всех остальных треугольников.

Как точно сформулировать соответствие между деревом и графом? Для этого мы введем понятие древовидной декомпозиции графа G, которая называется так потому, что мы хотим провести декомпозицию G по древовидной схеме.