184
правки
Изменения
→Ушной метод
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует два не пересекающихся между собой уха.
|proof=
[[Файл:4vertex 2ear.jpg|200px|thumb|right|Тривиальный пример многоугольника с четырьмя вершинами. <tex>E_1</tex> и <tex>E_2</tex> — уши]]Доказательство будем вести по индукции. Базовый случай: <tex>n = 4</tex> <здесь должна быть пикча>. Предположим для всех многоугольников, количество вершин в которых не больше <tex>n</tex>, теорема верна. Рассмотрим многоугольник <tex>P</tex>, в котором <tex>n+1</tex> вершина. Далее возможны два случая:
* Произвольная вершина <tex>v_i</tex> многоугольника <tex>P</tex> является ухом. Отрезав это ухо, мы уменьшим число вершин <tex>P</tex> на одну. В результате, получиv <tex>n</tex>-вершинный многоугольник <tex>P'</tex>. По предположению индукции у него существует два непересекающихся уха. Учитывая, что уши <tex>P'</tex> являются ушами и <tex>P</tex>, несложно заметить, что для <tex>P</tex> теорема верна.
