3622
правки
Изменения
→Свойства Straight skeleton
Каждая грань <tex> f(e) </tex> начинает образовываться во время стягивания ребра <tex> e </tex>, и даже если на ребре произошёл <tex> split\ event </tex>, сама грань не могла разделиться. Построение грани <tex> f(e) </tex> завершается, когда ребро <tex> e </tex> полностью стягивается. И это ребро дальше не может появиться снова, поэтому граней в <tex> S(P) </tex> столько, сколько сторон в многоугольнике, то есть ровно <tex> n </tex>.
То, что <tex> S(P) </tex> является деревом, легко доказывается по индукциичисла вершин в многоугольнике. '''База верна:''' многоугольник является треугольником, когда внутренняя вершина всего одна. Тогда у в его <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> будет одна внутренняя вершина {{---}} точка пересечения биссектрис, {{---}} листьями будут вершины многоугольникатреугольника. Такой граф очевидным образом будет деревом. Если в '''Переход:''' пусть для всех многоугольников с количеством вершин меньше <tex>k</tex> <tex> \mathrm{straight}\ \mathrm{skeleton}\ k </tex> внутренних вершин, то рассмотрим будет деревом. Рассмотрим самый первый <tex> edge\ event</tex>в многоугольнике из <tex>k</tex> вершин. Он закончился в какой-то внутренней вершине * Если это <tex> edge\mathrm{straight}\ \mathrm{skeleton} event</tex>, у неё есть смежные листья {{---}} вершиныто появится новая вершина, инцидентные этому которую мы соединим с инцидентными ребрувершинами, {{а так же с какой---}} и из неё достижимы другие то вершиной <tex> \mathrm{straight}\ \mathrm{skeleton}' </tex>ы, с не более чем полигона из <tex> k - 1 </tex> внутренними вершинамивершин. Получившийся граф будет деревом.* Если это <tex>split\ event</tex>, то новая вершина соединяется с одной вершиной исходного полигона и они являются деревьями по предположению индукцию. Тогда получаем, что с двумя вершинами <tex> S(P) \mathrm{straight}\ \mathrm{skeleton} </tex> для полигонов, в которых меньше <tex> k </tex> вершин тоже будет деревом.В этом случае также получаем дерево.
Внутренние вершины в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> имеют [[Основные определения теории графов#def_graph_degree_1 | степень]] не меньше <tex> 3 </tex> {{---}} простой перебор всех случаев <tex> event'</tex>ов (степень будет больше, если в одной вершине совпало несколько событий). Так как <tex> S(P) </tex> имеет <tex>n</tex> листьев, то внутренних вершин будет не больше <tex> n - 2 </tex>, а так как <tex> S(P) </tex> является деревом, то рёбер у него будет не более <tex> 2 n - 3 </tex>.
