Twierdzenie o dwojgu uszach

Trójkątny wielokąt. Dwa wierzchołki na końcach łańcucha trójkątów tworzą uszy. Jednak ten wielokąt ma również inne uszy, które nie są widoczne w tej triangulacji.

W geometrii twierdzenie o dwojgu uszach stwierdza, że każdy prosty wielokąt z więcej niż trzema wierzchołkami ma co najmniej dwoje uszu , wierzchołki, które można usunąć z wielokąta bez wprowadzania przecięć. Twierdzenie o dwojgu uszach jest równoważne z istnieniem triangulacji wielokątów . Jest to często przypisywane Gary'emu H. Meistersowi, ale udowodnił to wcześniej Max Dehn .

Stwierdzenie twierdzenia

Ucho wielokąta definiuje się jako wierzchołek $v$ taki, że odcinek linii między dwoma sąsiadami v $leży$ całkowicie we wnętrzu wielokąta. Twierdzenie o dwojgu uszach mówi, że każdy prosty wielokąt ma co najmniej dwoje uszu.

Uszy z triangulacji

Ucho i dwaj jego sąsiedzi tworzą trójkąt wewnątrz wielokąta, którego nie przecina żadna inna część wielokąta. Usunięcie trójkąta tego typu tworzy wielokąt o mniejszej liczbie boków, a wielokrotne usuwanie uszu umożliwia triangulację dowolnego prostego wielokąta .

I odwrotnie, jeśli wielokąt jest triangulowany, słaba liczba podwójna triangulacji (wykres z jednym wierzchołkiem na trójkąt i jedną krawędzią na parę sąsiednich trójkątów) będzie drzewem, a każdy liść drzewa utworzy ucho. Ponieważ każde drzewo z więcej niż jednym wierzchołkiem ma co najmniej dwa liście, każdy trójkątny wielokąt z więcej niż jednym trójkątem ma co najmniej dwoje uszu. Zatem twierdzenie o dwojgu uszach jest równoważne z faktem, że każdy prosty wielokąt ma triangulację.

Powiązane typy wierzchołków

Ucho nazywamy odsłoniętym , gdy tworzy wierzchołek wypukłej otoczki wielokąta. Jednak wielokąt może nie mieć odsłoniętych uszu.

Uszy są szczególnym przypadkiem głównego wierzchołka , wierzchołka takiego, że odcinek linii łączący sąsiadów wierzchołka nie przecina wielokąta ani nie dotyka żadnego innego jego wierzchołka. Główny wierzchołek, dla którego ten odcinek linii leży poza wielokątem, nazywany jest ujściem . Analogicznie do twierdzenia o dwojgu uszach, każdy prosty wielokąt niewypukły ma co najmniej jedno usta. Wielokąty z minimalną liczbą głównych wierzchołków obu typów, dwojgiem uszu i ustami, nazywane są wielokątami antropomorficznymi .

Historia i dowód

Twierdzenie o dwojgu uszach jest często przypisywane artykułowi Gary'ego H. Meistersa z 1975 r., Z którego wywodzi się terminologia „ucha”. Jednak twierdzenie to zostało udowodnione wcześniej przez Maxa Dehna (około 1899 r.) jako część dowodu twierdzenia o krzywej Jordana . Aby udowodnić twierdzenie, Dehn zauważa, że każdy wielokąt ma co najmniej trzy wierzchołki wypukłe. Jeśli jeden z tych wierzchołków, $v$ , nie jest uchem, to może być połączony przekątną z innym wierzchołkiem $x$ wewnątrz trójkąta $uvw$ utworzonego przez $v$ i jego dwóch sąsiadów; $X$ można wybrać jako wierzchołek w tym trójkącie, który jest najdalej od linii $uw$ . Ta przekątna rozkłada wielokąt na dwa mniejsze wielokąty, a wielokrotny rozkład na uszy i przekątne ostatecznie tworzy triangulację całego wielokąta, z którego można znaleźć ucho jako liść podwójnego drzewa.

Linki zewnętrzne