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

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

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

    Скращук Дмитрий

    ( г. Кобрин)

    П.1.

    Выпуклый многоугольник с

    n сторонами можно разбить на треугольники диагоналями, которые пересекаются

    лишь в его вершинах. Вывести формулу для числа таких разбиений.

    Определение: назовем правильным разбиением выпуклого

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

    n-угольника.

    2 , … ,

    n–вершины выпуклого

    n-угольника, А

    - число его правильных разбиений. Рассмотрим диагональ многоугольника

    n.В каждом правильном разбиени

    n принадлежит какому-то треугольнику

    n, где1

    n. Следовательно, полагая

    i=2,3, … ,

    n-1, мы получаем (

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

    Пусть

    i=2 – одна группа правильных разбиений, которая всегда содержит диагональ

    .Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (

    n-1) угольника

    3…

    Pn, то есть равно А

    n-1.

    Пусть

    i=3 – одна группа правильных разбиений, которая всегда содержит диагональ

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

    числом правильных разбиений (

    n-2)угольника

    4…

    Pn, то есть равно А

    n-2.

    При

    i=4 среди треугольников

    разбиение непременно содержит треугольник

    .К нему примыкают четырехугольник

    и (

    n-3)угольник

    5 …

    Pn.Число правильных разбиений четырехугольника равно

    4, число правильных разбиений (

    n-3) угольника равно

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

    4.Группы с

    i=4,5,6,… содержат А

    5, А

    … правильных разбиений.

    При

    n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с

    i=2,то есть равно

    n-1.

    Поскольку А

    1=А

    2=0, А

    3=1,

    4=2 и т.к.

    3, то число правильных разбиений равно:

    5+ … + A

    n-1.

    Например:

    5= A

    4+ А

    6= A

    5+ А

    + А

    5=14

    6+ А

    5+ А

    4 *А

    4+А

    6 =42

    7+ А

    6+А

    5*А

    4+ А

    4*А

    5+А

    7 =132

    П.2.1.

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

    Проверяя на частных случаях,

    пришли к предположению, что количество диагоналей в выпуклых

    n-угольниках равно произведению количества разбиений на (

    n-3)

    Докажем предположение, что

    = А

    n-3)

    n-угольник можно разбить на (

    n-2) треугольника, из которых можно сложить (

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

    n-3) четырехугольниках можно провести (

    n-3)

    дополнительные диагонали. Значит, в каждом правильном разбиении можно провести (

    n-3) диагонали удовлетворяющих условию задачи.

    П.2.2.

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

    Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых

    n-угольниках равно произведению количества разбиений на

    n-4), где

    n >= 5

    Докажем предположение, что

    n-4)А

    где

    n >= 5.

    n-угольник можно разбить на (

    n-2) треугольников из которых можно сложить (

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

    n-4) пятиугольника, значит, существует (

    n-4) дополнительные

    диагонали удовлетворяющих условию задачи.

    П.2.3.

    Разбиение

    n-угольника, в котором дополнительные диагонали пересекают главные

    k раз.

    Определение 1:Главными диагоналями

    выпуклого

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

    n-угольника.

    Замечание: их существует (

    n-3).

    Определение 2:Дополнительными диагоналями выпуклого

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

    Замечание: их существует менее (

    n-3).

    .Определение

    -угольник (где

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

    n-угольника

    n-угольника, причем выделением считается получение последующего

    a-угольника из предыдущего,

    используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (

    r = 4 или

    r = 3 (

    r – остаточный коэффициент)). Назовем

    каждое такое выделение циклом и введем величину, которая будет “считать” их (

    d). Для каждого

    d существует 2

    d+1 многоугольников, первый многоугольник для данного

    d ,будет (2

    d+1+1)-угольником. Для первой половины (для данного

    d) многоугольников

    r = 3, для второй -

    r = 4. Последним многоугольником, для которого

    r = 3 будет (3

    )-угольником. Окончательно получаем:

    r = 3, если

    d+1+1; 3

    ], в противном случае

    r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через

    d циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой

    Итак, за 1 цикл 2 пересечения, за 2 цикла – 4, за 3 – 6, очевидна

    арифметическая прогрессия с разностью 2,

    a1=2 и количество членов равным

    d; значит

    k=2+2(

    d-1)=2

    d – только в том случае, если конечной фигурой окажется треугольник. В противном случае

    d+1, так как четырехугольник имеет собственную диагональ.

    Рассчитаем

    d: т.к.:

    d=1,

    2+1; 2

    d=2, n

    3+1; 2

    d=3, n

    4+1; 2

    Зависимость

    d от

    становится очевидным равенство:

    n-1)]-1. Выразим

    k через

    k=2([log

    2 (n-1)]-1),

    если

    [log2(n-1)]+1; 3

    [log2(n-1)]-1]

    или

    k=2([log

    2(n-1)]-1)+1= 2[log

    2 (n-1)]-1, если

    [log2(n-1)]+1; 3

    [log2(n-1)]-1]

    Так как

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

    k<=2([log

    2 (n-1)]-1),

    если

    [log2(n-1)]+1; 3

    [log2(n-1)]-1]

    или

    k<=2[log

    2 (n-1)]-1, если

    [log2(n-1)]+1; 3

    [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,

    n-2 и

    c количеством членов равным

    m. Получим:

    n-2=

    k+1+(

    m-1)

    n-2=

    k+2)Значит, в

    n-угольник можно вписать (

    k+3)угольник (

    k+2))раз, то есть существуют

    такие (

    k+2)) дополнительные диагонали, которые пересекут

    k главных диагоналей.

    Окончательно получаем:

    n- (k+2))А

    n , где(*).

    Язык: Русский

    Скачиваний: 121

    Формат: Microsoft Word

    Размер файла: 61 Кб

    Автор:

    Скачать работу...

    Забрать файл

    Похожие материалы:


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

    Введите код:
    Включите эту картинку для отображения кода безопасности
    обновить, если не виден код



ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены