Teorema celor două urechi
În geometrie teorema celor două urechi afirmă că fiecare poligon simplu cu mai mult de trei vârfuri are cel puțin două urechi, vârfuri care pot fi eliminate din poligon fără a introduce nicio intersectare. Teorema celor două urechi este echivalentă cu existența triangulării poligoanelor. Este adesea atribuită lui Gary H. Meisters, dar a fost demonstrată anterior de Max Dehn.
Enunțul teoremei[modificare | modificare sursă]
O ureche a unui poligon este definită ca fiind un vârf, v, pentru care segmentul de dreaptă dintre vârfurile vecine lui v se află în întregime în interiorul poligonului. Teorema celor două urechi afirmă că orice poligon simplu are cel puțin două urechi.
Urechi din triangulări[modificare | modificare sursă]
O ureche împreună cu cele două vârfuri vecine ale sale formează un triunghi în interiorul poligonului, care nu este traversat de nicio altă latură a poligonului. Eliminarea unui triunghi de acest tip produce un poligon cu mai puține laturi, iar eliminarea repetată a urechilor permite oricărui poligon simplu să fie triangulat.
Invers, dacă un poligon este triangulat, graful dual slab(d) al triangulării (un graf cu un nod pe triunghi și o muchie pe perechea de triunghiuri adiacente) va fi un arbore și fiecare nod terminal al arborelui va forma o ureche. Deoarece fiecare arbore cu mai mult de un nod are cel puțin două noduri terminale, fiecare poligon triangulat cu mai mult de un triunghi are cel puțin două urechi. Astfel, teorema celor două urechi este echivalentă cu faptul că fiecare poligon simplu are o triangulare.[1]
Tipuri înrudite de vârfuri[modificare | modificare sursă]
Se spune despre o ureche că este expusă când formează un vârf al înfășurătoarei convexe a poligonului. Însă este posibil ca un poligon să nu aibă urechi expuse.[2]
Urechile sunt un caz particular al unui vârf principal, un vârf la care segmentul de dreaptă care leagă vecinii vârfului nu traversează poligonul și nu atinge niciun alt vârf al acestuia. Un vârf principal pentru care acest segment de dreaptă se află în afara poligonului este numit gură. În mod analog cu teorema celor două urechi, fiecare poligon simplu neconvex are cel puțin o gură. Poligoanele cu numărul minim de vârfuri principale ale ambelor tipuri, două urechi și o gură, se numesc poligoane antropomorfe.[3]
Istoric și demonstrație[modificare | modificare sursă]
Teorema celor două urechi este adesea atribuită unei lucrări din 1975 a lui Gary H. Meisters, din care provine terminologia ureche.[4] Însă teorema a fost demonstrată anterior de Max Dehn (în circa 1899) ca parte a unei demonstrații a teoremei lui Jordan. Pentru a demonstra teorema, Dehn observă că fiecare poligon are cel puțin trei vârfuri convexe. Dacă unul dintre aceste vârfuri, v, nu este o ureche, atunci poate fi conectat printr-o diagonală de un alt vârf x în interiorul triunghiului uvw format din v și cei doi vecini ai săi; x poate fi ales să fie vârful din acest triunghi care este cel mai îndepărtat de linia uw. Această diagonală descompune poligonul în două poligoane mai mici, iar descompunerea repetată prin urechi și diagonale produce în cele din urmă o triangulare a întregului poligon, din care o ureche poate fi găsită ca un nod terminal al arborelui dual.[5]
Note[modificare | modificare sursă]
- ^ en O'Rourke, Joseph (), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, Oxford University Press, ISBN 0-19-503965-3, MR 0921437
- ^ en Meisters, G. H. (), „Principal vertices, exposed points, and ears”, American Mathematical Monthly, 87 (4): 284–285, doi:10.2307/2321563, JSTOR 2321563, MR 0567710
- ^ Toussaint, Godfried (), „Anthropomorphic polygons”, American Mathematical Monthly, 98 (1): 31–35, doi:10.2307/2324033, JSTOR 2324033, MR 1083611
- ^ en Meisters, G. H. (), „Polygons have ears”, American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703, MR 0367792
- ^ en Guggenheimer, Heinrich (), „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
Legături externe[modificare | modificare sursă]
- en Meisters' Two Ears Theorem, la Cut-the-Knot
- en The Two-Ears Theorem, Godfried Toussaint
- en Eric W. Weisstein, Two-Ears Theorem la MathWorld.
