Ширина ленты графа: различия между версиями

Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <math>G = (V, E) \; </math>, позволяющего минимизировать максимальное «растяжение» любого ребра в этом упорядочении. Более формально, пусть <math>n = |V| \; </math>. Рассмотрим отображение «сколько угодно к одному» <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>. Ширина этого упорядочения составляет <math>bw_{\pi } (G) = max_{ \{ u, v \} \in E} | \pi (u) - \pi (v) | </math>. Ширина ленты графа G задается шириной ленты лучшего возможного упорядочения: <math>bw(G) = min_{\pi } bw_{\pi }(G)</math>.