4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <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>. | Задача нахождения ширины ленты графа заключается в установлении линейного порядка над вершинами графа <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>. | ||
Изначально эта задача возникла в процессе предварительной обработки разреженных симметричных квадратных матриц. Пусть A – такая матрица n | Изначально эта задача возникла в процессе предварительной обработки разреженных симметричных квадратных матриц. Пусть A – такая матрица <math>n \times n \;</math> ; рассмотрим задачу нахождения матрицы перестановок P, такой, что все ненулевые элементы <math>P^T AP \; </math> располагаются в максимально возможно узкой полосе вблизи от диагонали. Эта задача эквивалентна задаче минимизации ширины ленты графа G, имеющего вершины {1, 2, ..., n} и содержащего ребро {u, v} в том и только том случае, когда <math>A_{u, v} \ne 0</math>. | ||
Взамен этого факта можно попытаться эффективно вычислить линейный порядок, для которого | |||
Взамен этого факта можно попытаться эффективно вычислить линейный порядок <math>\pi \;</math> , для которого <math>bw_{\pi }(G) \le A \cdot bw(G)</math>, сделав при этом [[коэффициент аппроксимации]] A минимально возможным. Было показано, что задача получения любого значения A = O(1) является NP-полной [18]. Основная сложность при нахождении ширины ленты графа заключается в том, что целевая функция представляет собой максимум по всем ребрам графа. В силу этого подход «разделяй и властвуй» для нахождения ширины ленты графа неэффективен, в отличие от таких родственных задач, как алгоритм минимального линейного ранжирования [ ] (здесь задача заключается в минимизации J2{u v}€E \ж(и) — ^(V)D-. Таким образом, требуется более глобальный алгоритм. Вначале следует обсудить нахождение хорошей нижней границы значения bw(G). | |||