Теорема про два вуха
В геометрії теорема про два вуха стверджує, що кожен простий багатокутник більш ніж з трьома вершинами має щонайменше два вуха, вершини, які можна вилучити з багатокутника без використання перетинів. Теорема про два вуха еквівалентна існуванню тріангуляції багатокутника. Її часто приписують Гері Х. Мейстерсу, але вона була доведена раніше Максом Деном.
Твердження теореми[ред. | ред. код]
Вухо багатокутника визначається як вершина v така, що відрізок лінії між двома вершинами, які суміжні (з'єднані ребром) v, повністю лежить у внутрішній частині багатокутника. Теорема про два вуха стверджує, що кожен простий багатокутник має щонайменше два вуха.
Вуха та тріангуляція[ред. | ред. код]
Вухо та дві його суміжні вершини утворюють трикутник у межах багатокутника, який не перетинається жодною іншою частиною багатокутника. Якщо вилучити трикутник такого типу, утворюється багатокутник з меншою кількістю сторін, а багаторазове видалення вух дозволяє тріангулювати будь-який простий багатокутник.
І навпаки, якщо багатокутник трикутний, слабко двоїстий граф тріангуляції (граф в якому одна вершина відповідає одному трикутнику, а одне ребро — парі суміжних трикутників) буде деревом і кожен лист дерева відповідатиме вуху. Оскільки кожне дерево більш ніж з однією вершиною має щонайменше два листки, кожен тріангульований багатокутник, в якому більш ніж один трикутник, має принаймні два вуха. Таким чином, теорема про два вуха рівносильна тому, що кожен простий багатокутник має тріангуляцію[1].
Суміжні типи вершин[ред. | ред. код]
Вухо називають оголеним, коли воно утворює вершину опуклої оболонки багатокутника. Однак багатокутник може й не мати оголених вух[2].
Вуха є окремим випадком головної вершини, а саме такою, що відрізок лінії, який з'єднує суміжні вершини, не перетинає багатокутник і не торкається будь-якої іншої його вершини. Основна вершина, для якої цей відрізок не належить багатокутнику, називається ротом. Аналогічно теоремі про два вуха, кожен не опуклий простий багатокутник має щонайменше один рота. Багатокутники з мінімальною кількістю головних вершин обох типів, а саме, рівно з двома вухами та одним ротом, називаються антропоморфними багатокутниками[3].
Історія та докази[ред. | ред. код]
Теорему про два вуха часто пов'язують зі статтею Гарі Х. Мейстерса 1975 року, з якого і походить термінологія «вуха»[4]. Однак теорема була доведена раніше Максом Деном (близько 1899 року) як частина доказу теореми Жордана. Для доведення теореми, Ден зауважує, що кожен багатокутник має щонайменше три опуклі вершини. Якщо одна з цих вершин, v, не є вухом, то вона може бути з'єднана по діагоналі з іншою вершиною x всередині трикутника uvw утвореної v і двома його суміжними; x може бути вершиною у цьому трикутнику, та буде найвіддаленішою від лінії uw. Ця діагональ ділить багатокутник на два менші багатокутники, і повторний поділ на вуха та діагоналі призводить до тріангуляції всього многокутника, з якого вухо може бути знайдено як лист двоїстого дерева[5].
Примітки[ред. | ред. код]
- ↑ O'Rourke, Joseph (1987), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN 0-19-503965-3, MR 0921437
- ↑ Meisters, G. H. (1980), Principal vertices, exposed points, and ears, American Mathematical Monthly, 87 (4): 284—285, doi:10.2307/2321563, MR 0567710.
- ↑ Toussaint, Godfried (1991), Anthropomorphic polygons, American Mathematical Monthly, 98 (1): 31—35, doi:10.2307/2324033, MR 1083611.
- ↑ Meisters, G. H. (1975), Polygons have ears, American Mathematical Monthly, 82: 648—651, doi:10.2307/2319703, MR 0367792.
- ↑ Guggenheimer, H. (1977), The Jordan curve theorem and an unpublished manuscript by Max Dehn (PDF), Archive for History of Exact Sciences, 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.