Какое значение имеет ширина в теории графов и компьютерных науках?

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

Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. 13 Например, графы потока управления, появляющиеся при трансляции структурных программ, также имеют ограниченную древесную ширину, что позволяет эффективно выполнять некоторые задачи, такие как распределение регистров. 2

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