Реферат : Разбиения выпуклого многоугольника 


Полнотекстовый поиск по базе:

Главная >> Реферат >> Математика


Разбиения выпуклого многоугольника




Разбиения выпуклого многоугольника

П.1. Выпуклый многоугольник с n сторонами можно разбить на треугольники диагоналями, которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений.

Определение: назовем правильным разбиением выпуклого n-угольника на треугольники диагоналями, пересекающимися только в вершинах n-угольника.

Пусть P1, P2 , … ,Pn–вершины выпуклого n-угольника, Аn- число его правильных разбиений. Рассмотрим диагональ многоугольника PiPn.В каждом правильном разбиение P1Pn принадлежит какому-то треугольнику P1PiPn, где1<i<n. Следовательно, полагая i=2,3, … , n-1, мы получаем (n-2) группы правильных разбиений, включающие все возможные случаи.

Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P2Pn .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1) угольника P2P3Pn, то есть равно Аn-1.

Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P3P1 и P3Pn.Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений (n-2)угольника P3P4Pn, то есть равно Аn-2.

При i=4 среди треугольников разбиение непременно содержит треугольник P1P4Pn.К нему примыкают четырехугольник P1P2P3P4 и (n-3)угольник P4P5Pn.Число правильных разбиений четырехугольника равно A4, число правильных разбиений (n-3) угольника равно

Аn-3.Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно

Аn-3A4.Группы с i=4,5,6,… содержат Аn-4A5, Аn-5A6, … правильных разбиений.

При i=n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с i=2,то есть равно Аn-1.

Поскольку А12=0, А3=1, A4=2 и т.к. n 3, то число правильных разбиений равно:

Аn= Аn-1+Аn-2+Аn-3 A4+Аn-4 A5+ … + A 5Аn-4+ A4Аn-3+ Аn-2+ Аn-1.

Например:

A 5= A4+ А3+ A4=5

A6= A5+ А4+ А4+ A5=14

A7= A6+ А5+ А4 *А45+ A6 =42

A8= A7+ А65*А4+ А4*А56+ A7 =132

П.2.1. Найдем количество во всех диагоналей правильных разбиениях, которые пересекают внутри только одну диагональ.

Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-3)

Докажем предположение, что P1n= Аn(n-3)

Каждый n-угольник можно разбить на (n-2) треугольника, из которых можно сложить (n-3) четырехугольника, причем каждый четырехугольник будет иметь диагональ. Но в четырехугольнике можно провести 2 диагонали, значит в (n-3) четырехугольниках можно провести (n-3) дополнительные диагонали. Значит, в каждом правильном разбиении можно провести (n-3) диагонали удовлетворяющих условию задачи.

П.2.2. Найдем количество во всех диагоналей правильных всех разбиениях, которые пересекают внутри только две диагонали.

Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-4), где n ≥ 5

Докажем предположение, что P2n=(n-4)Аn , где n ≥ 5.

n-угольник можно разбить на (n-2) треугольников из которых можно сложить (n-4) пятиугольника, в котором будут содержаться две непересекающиеся диагонали. Значит, найдется третья диагональ, которая пересекает две другие. Так как имеется (n-4) пятиугольника, значит, существует (n-4) дополнительные диагонали удовлетворяющих условию задачи.

П.2.3. Разбиение n-угольника, в котором дополнительные диагонали пересекают главные k раз.

Определение 1:Главными диагоналями выпуклого n-угольника называются диагонали, которые разбивают его на треугольники, пересекаясь при этом только в вершинах n-угольника.

Замечание: их существует (n-3).

Определение 2:Дополнительными диагоналями выпуклого n-угольника называются диагонали, которые в данном разбиении пересекают главные диагонали.

Замечание: их существует менее (n-3).

I.Определение k:

Б
удем выделять из выпуклого n-угольника

следующим образом: соединяем диагоналями через одну вершину данного n-угольника, причем выделением считается получение последующего a-угольника из предыдущего, используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (r = 4 или r = 3 (r – остаточный коэффициент)). Назовем каждое такое выделение циклом и введем величину, которая будет “считать” их (d). Для каждого d существует 2d+1 многоугольников, первый многоугольник для данного d ,будет (2d+1+1)-угольником. Для первой половины (для данного d) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (32d )-угольником. Окончательно получаем: r = 3, если n[2d+1+1; 32d], в противном случае r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через d циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой k.

Итак, за 1 цикл 2 пересечения, за 2 цикла – 4, за 3 – 6, очевидна арифметическая прогрессия с разностью 2, a1=2 и количество членов равным d; значит k=2+2(d-1)=2d – только в том случае, если конечной фигурой окажется треугольник. В противном случае k=2d+1, так как четырехугольник имеет собственную диагональ.

Рассчитаем d: т.к.: d=1, n [22+1; 23]

d=2, n [23+1; 24]

d=3, n [24+1; 25]

Зависимость d от n- логарифмическая по основанию 2; становится очевидным равенство: d=[log2(n-1)]-1. Выразим k через n:

k=2([log2 (n-1)]-1), если n[2[log2(n-1)]+1; 32[log2(n-1)]-1]

или

k=2([log2(n-1)]-1)+1= 2[log2 (n-1)]-1, если n[2[log2(n-1)]+1; 32[log2(n-1)]-1]

Так как k – максимум пересечений, то уместны неравенства:

k≤2([log2 (n-1)]-1), если n[2[log2(n-1)]+1; 32[log2(n-1)]-1]

или (*)

k≤2[log2 (n-1)]-1, если n[2[log2(n-1)]+1; 32[log2(n-1)]-1]

II. Найдем число дополнительных диагоналей (m), которые пересекают главные не более k раз.

Выделим в данном выпуклом n-угольнике (k+3)-угольник (k+3)-угольник (если это возможно), зн.

уже ‘использовано’ (n+3)-2=k+1 всех

отбросили существующих треугольников

1 треугольник n-угольника (всего их (n-2)),потом добавили другой ‘отбросим’ крайний треугольник и реугольник и ‘добавим’ к получившейся фигуре еще опять получили один, имеющий общую с ней сторону, (k+3)-угольник ‘не использованный’ треугольник, тогда останется (k+2) не использованных треугольника, и так далее до тех пор, пока не ‘используем’ все (n-2)треугольника. Очевидна арифметическая прогрессия с разностью 1, am=n-2 и c количеством членов равным m. Получим:n-2=k+1+(m-1)<=>n-2=k+m<=>m=n-k-2m=n-(k+2)Значит, в n-угольник можно вписать (k+3)угольник (n-(k+2))раз, то есть существуют такие (n-(k+2)) дополнительные диагонали, которые пересекут k главных диагоналей.

Окончательно получаем: Pkn=(n- (k+2))Аn , где (*).

Список литературы

Скращук Дмитрий (г. Кобрин). Разбиения выпуклого многоугольника

Похожие работы:

  • Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

    Реферат >> Математика
    ... в конечном множестве. Теорема 4. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла ... разбиение исходной задачи на подзадачи для параллельной обработки. Быстрые методы построения выпуклой ...
  • Разбиение Делоне

    Курсовая работа >> Информатика, программирование
    ... способами. В двумерном случае для многоугольника с N вершинами может реализоваться ( ... ибо все полиэдры Делоне – выпуклые многогранники. Отсюда следует, что ... первоначальной логике Б.Н. Делоне, разбиением Делоне является разбиение системы {A} на полиэдры ...
  • Методы и приемы решения задач

    Реферат >> Математика
    ... количество острых углов выпуклого многоугольника – три. Докажем ее. 1) Пусть найдется выпуклый многоугольник с большим числом ... сделанного предположения, общее число треугольников разбиения будет равно (k-2)+[(n-k+2)-2]=n-2; тем самым наше ...
  • Особенности применения технологии квантового обучения в преподавании математики

    Дипломная работа >> Педагогика
    ... соответствующим типом модальности. Разбиение на группы здесь используется ... Подготовительная часть заключается в разбиении учащихся на группы для ... грани выпуклого многогранника являются выпуклыми многоугольниками. Можно доказать, что в выпуклом многограннике ...
  • Эйлеровы и гамильтоновы графы

    Реферат >> Информатика, программирование
    ... нижних границ подмножеств и разбиения множества гамильтоновых контуров на ... длины гамильтоновых контуров. Разбиение множества контуров на подмножества ... чтобы включить в тур в виде выпуклого многоугольника все центральные города с минимальными потерями ...
  • Элементы общей топологии

    Курсовая работа >> Математика
    ... рассмотренных многогранников (или, вообще, любого выпуклого многогранника) гомеоморфна сфере: если О  произвольная ... характеристика (Q) не зависит от выбора разбиения на многоугольники, а определяется самой поверхностью, т.е. является ...
  • Обеспечение всеобщей компьютерной грамотности

    Курсовая работа >> Информатика, программирование
    ... конструктивно, т. е. дается алгоритм построения такого разбиения для любого числа. Доказательство опирается ... данного множества точек, являющихся вершинами выпуклого многоугольника, который содержит все остальные точки ...
  • Нейрокомпьютерные системы

    Реферат >> Информатика, программирование
    ... 2.8 показан результат такого двойного разбиения, где выходной сигнал нейрона ... использовано три нейрона с дальнейшим разбиением плоскости и созданием области ... принима­ет в качестве входа набор выпуклых многоугольников, и их логическая комбинация может ...
  • Углеродные нанотрубки

    Реферат >> Физика
    ... n3 число треугольных граней выпуклого многогранника, через n4 - ... Пусть Q — ïîâåðõíîñòü, êîòîðàÿ äîïóñ­кает разбиение на многоугольники; это означает, что на поверхности ... Х(Q) не зависит от выбора разбиения на многоугольники, а определяется самой по­верхностью. ...
  • Задача коммивояжера

    Курсовая работа >> Экономика
    ... В работах Л.Эйлера по разбиениям и композициям натуральных чисел на ... выпуклый многоугольник, по периметру которого лежат все города, то такой выпуклый многоугольник ... включить в тур в виде выпуклого многоугольника все центральные города с минимальными ...