Триангуляция - многоугольник
Cтраница 1
Триангуляция многоугольника представляет собой граф, получающийся из регулярного re - угольника путем добавления непересекающихся хорд до тех пор, пока каждая внутренняя область не станет треугольником. Очевидно, что для получения п - 2 треугольников нужно провести п - 3 хорд. Мы переформулируем задачу ( замечая, что триангуляции многоугольников соответствуют как раз планар-ным 2-деревьям) в утверждение, относящееся к двумерным сим-плициальным комплексам. [1]
Триангуляция многоугольника представляет собой граф, получающийся из регулярного и-угольника путем добавления непересекающихся хорд до тех пор, пока каждая внутренняя область не станет треугольником. Очевидно, что для получения п - 2 треугольников нужно провести п - 3 хорд. Мы переформулируем задачу ( замечая, что триангуляции многоугольников соответствуют как раз планар-ным 2-деревьям) в утверждение, относящееся к двумерным сим-плициальным комплексам. [2]
Триангуляции многоугольника abed, показанные на рис. 1А и 1В, изоморфны, а триангуляции, представленные на рис. 1В и 1C, не изоморфны. [3]
Сначала они ищут триангуляцию многоугольника Р, а затем выполняют 3-раскрашивание вершин многоугольника Р таким образом, чтобы никакие две смежные в триангуляции вершины не были бы раскрашены в один цвет. Основываясь на этой раскраске, они удаляют все диагонали, инцидентные вершинам заданного цвета, получая, таким образом, разбиение на звездные многоугольники. [4]
Сначала они ищут триангуляцию многоугольника Я, а затем выполняют 3-раскрашивание вершин многоугольника Р таким образом, чтобы никакие две смежные в триангуляции вершины не были бы раскрашены в один цвет. Основываясь на этой раскраске, они удаляют все диагонали, инцидентные вершинам заданного цвета, получая, таким образом, разбиение на звездные многоугольники. [5]
 |
Внешнепланарный граф и две его внешнеплоские укладки.| Три максимальных внешнеплоских графа. [6] |
Внешнепланарный граф G называется максимальным внешнепланарным, если к нему нельзя добавить ни одного ребра, не теряя свойства внешнепланарности. Ясно, что каждый максимальный внешнеплоский граф есть триангуляция многоугольника, а каждый максимальный плоский граф - триангуляция сферы. [7]
Многоугольник подвергается мелкой триангуляции Тп так, чтобы стороны треугольников были меньше 1 / ге. Для каждого треугольника этой триангуляции строится плоский треугольник со сторонами той же длины и берется сумма площадей Sn таких треугольников. Оказывается, независимо от выбора триангуляции многоугольника, сумма Sn при г - - оо стремится к определенному пределу. Этот предел и принимается за площадь многоугольника. Затем обычными приемами теории меры определяются площади замкнутых, открытых и вообще борелевских множеств. [8]
Триангуляция многоугольника представляет собой граф, получающийся из регулярного re - угольника путем добавления непересекающихся хорд до тех пор, пока каждая внутренняя область не станет треугольником. Очевидно, что для получения п - 2 треугольников нужно провести п - 3 хорд. Мы переформулируем задачу ( замечая, что триангуляции многоугольников соответствуют как раз планар-ным 2-деревьям) в утверждение, относящееся к двумерным сим-плициальным комплексам. [9]
Триангуляция многоугольника представляет собой граф, получающийся из регулярного и-угольника путем добавления непересекающихся хорд до тех пор, пока каждая внутренняя область не станет треугольником. Очевидно, что для получения п - 2 треугольников нужно провести п - 3 хорд. Мы переформулируем задачу ( замечая, что триангуляции многоугольников соответствуют как раз планар-ным 2-деревьям) в утверждение, относящееся к двумерным сим-плициальным комплексам. [10]
В этом параграфе изучаются некоторые понятия, относя-циеся к деревьям и связанные со структурами достаточно высокой размерности. Для того чтобы перечислить специальные щумерные структуры, называемые 2-деревьями, приходится до-юлнительно развить теорию характеристики неподобия и применять теоремы перечисления Пойа. Наши методы можно приспособить к перечислению таких 2-деревьев, которые уложены га плоскости, и, таким образом, предлагается новый подход к старой задаче о нахождении числа триангуляции многоугольника. [11]
В этом параграфе изучаются некоторые понятия, относящиеся к деревьям и связанные со структурами достаточно высокой размерности. Для того чтобы перечислить специальные двумерные структуры, называемые 2-деревьями, приходится дополнительно развить теорию характеристики неподобия и применять теоремы перечисления Пойа. Наши методы можно приспособить к перечислению таких 2-деревьев, которые уложены на плоскости, и, таким образом, предлагается новый подход к старой задаче о нахождении числа триангуляции многоугольника. [12]
Страницы: 1