4551
правка
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Геометрическая сеть; протяженность; обход == Постановка за…») |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 36: | Строка 36: | ||
Дас и Джозеф [9] следующим образом обобщили утверждение теоремы 1 (см. | Дас и Джозеф [9] следующим образом обобщили утверждение теоремы 1 (см. рисунок). Пусть G – плоский граф с множеством вершин S, а a – вещественное число, 0 < a < л/2. Для любого ребра e графа G обозначим за A\ и Ai два равнобедренных треугольника с основанием e и углом при основании a. Ребро e удовлетворяет свойству a-ромба, если по меньшей мере один из треугольников A\ и Л 2 не содержит внутри точек множества S. Плоский граф G удовлетворяет свойству a-ромба, если каждое ребро e графа G удовлетворяет этому свойству. Для вещественного числа d > 1 граф G удовлетворяет свойству d-хорошего многоугольника, если для каждой грани f графа G и для каждых двух вершин p и q на границе f, таких, что соединяющий их отрезок прямой полностью находится в f, длина пути между p и q вдоль границы f не превышает d|pq|. Дас и Джозеф [9] доказали, что любой плоский граф, удовлетворяющий одновременно свойству a-ромба и свойству d-хорошего многоугольника, является t-остовом для некоторого вещественного числа t, которое зависит только от a и d. Значение t было несколько улучшено Ли [13]: | ||
[[Файл:PGS_1.png]] | |||
С левой стороны изображено свойство a-ромба. По меньшей мере один из треугольников A\ Л 2 не содержит внутри точек множества S. Справа проиллюстрировано свойство d-хорошего многоугольника. p и q – две вершины на одной и той же грани f, которые видят друг друга. По меньшей мере один из двух путей между p и q вдоль границы f имеет длину, не превышающую d|pq| | С левой стороны изображено свойство a-ромба. По меньшей мере один из треугольников A\ Л 2 не содержит внутри точек множества S. Справа проиллюстрировано свойство d-хорошего многоугольника. p и q – две вершины на одной и той же грани f, которые видят друг друга. По меньшей мере один из двух путей между p и q вдоль границы f имеет длину, не превышающую d|pq| | ||
правка