4551
правка
Ширина ленты графа: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Файги доказал следующие положения. | Файги доказал следующие положения. | ||
''' | |||
Теорема 1. Существует эффективный алгоритм, который для графа G = (V, E) устанавливает линейный порядок ж: V !f 1; 2; :::; ng. ::; ng, для которого bw^(G) < O I (log n)3 plog n log log n J • D(G). В частности, имеется полилогарифмический относительно n алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида. | Теорема 1. Существует эффективный алгоритм, который для графа G = (V, E) устанавливает линейный порядок ж: V !f 1; 2; :::; ng. ::; ng, для которого bw^(G) < O I (log n)3 plog n log log n J • D(G). В частности, имеется полилогарифмический относительно n алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида.''' | ||
| Строка 37: | Строка 37: | ||
Требование kf(u) — f(v)k < 1 для каждого ребра fu; vg является естественным, поскольку f(u) и f(v) должны иметь сходные проекции на произвольное направление a; из этого интуитивно следует, что u и v будут отображаться в порожденном линейном порядке не слишком далеко друг от друга. Но даже если jh(u) — h(v)j мало, может оказаться, что между h(u) и h(v) проецируется слишком много вершин, из-за чего между u и v возникает значительное растяжение. Чтобы избежать такой ситуации, изображения вершин должны быть в достаточной мере «разнесены», что соответствует требованию большого объема выпуклой оболочки изображений. | Требование kf(u) — f(v)k < 1 для каждого ребра fu; vg является естественным, поскольку f(u) и f(v) должны иметь сходные проекции на произвольное направление a; из этого интуитивно следует, что u и v будут отображаться в порожденном линейном порядке не слишком далеко друг от друга. Но даже если jh(u) — h(v)j мало, может оказаться, что между h(u) и h(v) проецируется слишком много вершин, из-за чего между u и v возникает значительное растяжение. Чтобы избежать такой ситуации, изображения вершин должны быть в достаточной мере «разнесены», что соответствует требованию большого объема выпуклой оболочки изображений. | ||
== Применение == | == Применение == | ||
