Теорема про два вуха

В геометрії теорема про два вуха стверджує, що кожен простий багатокутник більш ніж з трьома вершинами має щонайменше два (вуха), вершини, які можна вилучити з багатокутника без використання перетинів. Теорема про два вуха еквівалентна існуванню тріангуляції багатокутника. Її часто приписують Гері Х. Мейстерсу, але вона була доведена раніше Максом Деном.

Тріангульований багатокутник. Дві вершини на кінцях ланцюга трикутників утворюють вуха. Однак, у цього багатокутника є й інші вуха, які очевидні при такій триангуляції.

Твердження теореми

Вухо багатокутника визначається як вершина v така, що відрізок лінії між двома вершинами, які суміжні (з'єднані ребром) v, повністю лежить у внутрішній частині багатокутника. Теорема про два вуха стверджує, що кожен простий багатокутник має щонайменше два вуха.

Вуха та тріангуляція

Вухо та дві його суміжні вершини утворюють трикутник у межах багатокутника, який не перетинається жодною іншою частиною багатокутника. Якщо вилучити трикутник такого типу, утворюється багатокутник з меншою кількістю сторін, а багаторазове видалення вух дозволяє тріангулювати будь-який простий багатокутник.

І навпаки, якщо багатокутник трикутний, слабко двоїстий граф тріангуляції (граф в якому одна вершина відповідає одному трикутнику, а одне ребро — парі суміжних трикутників) буде деревом і кожен лист дерева відповідатиме вуху. Оскільки кожне дерево більш ніж з однією вершиною має щонайменше два листки, кожен тріангульований багатокутник, в якому більш ніж один трикутник, має принаймні два вуха. Таким чином, теорема про два вуха рівносильна тому, що кожен простий багатокутник має тріангуляцію.

Суміжні типи вершин

Вухо називають оголеним, коли воно утворює вершину опуклої оболонки багатокутника. Однак багатокутник може й не мати оголених вух.

Вуха є окремим випадком (головної вершини), а саме такою, що відрізок лінії, який з'єднує суміжні вершини, не перетинає багатокутник і не торкається будь-якої іншої його вершини. Основна вершина, для якої цей відрізок не належить багатокутнику, називається ротом. Аналогічно теоремі про два вуха, кожен не опуклий простий багатокутник має щонайменше один рота. Багатокутники з мінімальною кількістю головних вершин обох типів, а саме, рівно з двома вухами та одним ротом, називаються антропоморфними багатокутниками.

Історія та докази

Теорему про два вуха часто пов'язують зі статтею Гарі Х. Мейстерса 1975 року, з якого і походить термінологія «вуха». Однак теорема була доведена раніше Максом Деном (близько 1899 року) як частина доказу теореми Жордана. Для доведення теореми, Ден зауважує, що кожен багатокутник має щонайменше три опуклі вершини. Якщо одна з цих вершин, v, не є вухом, то вона може бути з'єднана по діагоналі з іншою вершиною x всередині трикутника uvw утвореної v і двома його суміжними; x може бути вершиною у цьому трикутнику, та буде найвіддаленішою від лінії uw. Ця діагональ ділить багатокутник на два менші багатокутники, і повторний поділ на вуха та діагоналі призводить до тріангуляції всього многокутника, з якого вухо може бути знайдено як лист двоїстого дерева.

Примітки

1. (1987), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN , MR 0921437
2. Meisters, G. H. (1980), Principal vertices, exposed points, and ears, American Mathematical Monthly, 87 (4): 284—285, doi:10.2307/2321563, MR 0567710.
3. (1991), Anthropomorphic polygons, American Mathematical Monthly, 98 (1): 31—35, doi:10.2307/2324033, MR 1083611.
4. Meisters, G. H. (1975), Polygons have ears, American Mathematical Monthly, 82: 648—651, doi:10.2307/2319703, MR 0367792.
5. (1977), (PDF), , 17 (2): 193—200, doi:10.1007/BF02464980, JSTOR 41133486, MR 0532231, архів оригіналу (PDF) за 19 лютого 2018, процитовано 17 жовтня 2019.

Джерела

• Meisters' Two Ears Theorem [ 22 жовтня 2019 у Wayback Machine.], Cut-the-Knot (англ.)
• The Two-Ears Theorem [ 23 травня 2016 у Wayback Machine.], ^[en] (англ.)
• Weisstein, Eric W. Two-Ears Theorem(англ.) на сайті Wolfram MathWorld.