Вход

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

Курсовая работа по математике
Дата добавления: 18 января 2003
Язык курсовой: Русский
Word, rtf, 745 кб
Курсовую можно скачать бесплатно
Скачать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу

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

Скращук Дмитрий ( г. Кобрин)

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

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

Пусть P1, P2 , … ,Pn–вершины выпуклого n-угольника, Аn- число его правильных разбиений. Рассмотрим диагональ многоугольника PiPn.В каждом правильном разбиени P1Pn принадлежит какому-то треугольнику P1PiPn, где1

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

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

При i=4 среди треугольников разбиение непременно содержит треугольник P1P4Pn.К нему примыкают четырехугольник P1P2P3P4 и (n-3)угольник P4P5 …Pn.Число правильных разбиений четырехугольника равно 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-1n-2n-3 A4n-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 будет (32d )-угольником. Окончательно получаем: r = 3, если n[2d+1+1; 32d], в противном случае 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 , где (*).



© Рефератбанк, 2002 - 2017