WikiDer > Теорема Балинскиса - Википедия

Balinskis theorem - Wikipedia
Удаление любых двух вершин (желтая) не может разъединить трехмерный многогранник: можно выбрать третью вершину (зеленый) и нетривиальную линейную функцию, нулевой набор которой (синий) проходит через эти три вершины, что позволяет соединять выбранную вершину с вершиной. минимум и максимум функции и от любой другой вершины к минимуму или максимуму.

В многогранная комбинаторика, раздел математики, Теорема Балинского это заявление о теоретико-графовый структура трехмерного многогранники и многомерные многогранники. В нем говорится, что если кто-то формирует неориентированный граф из вершин и ребер выпуклого d-мерный многогранник или многогранник (его скелет), то полученный граф не меньше d-вершинно-связанный: удаление любых d - 1 вершина выходит из связного подграфа. Например, для трехмерного многогранника, даже если две его вершины (вместе с их инцидентными ребрами) будут удалены, для любой пары вершин все равно будет существовать путь из вершин и ребер, соединяющих пару.[1]

Теорема Балинского названа в честь математика Мишель Балински, опубликовавший свое доказательство в 1961 г.,[2] хотя трехмерный корпус восходит к началу 20 века, и открытие Теорема Стейница что графики трехмерных многогранников - это в точности трехсвязные плоские графы.[3]

Доказательство Балинского

Балински доказывает результат на основании правильности симплексный метод для нахождения минимума или максимума линейной функции на выпуклом многограннике ( линейное программирование проблема). Симплексный метод начинается с произвольной вершины многогранника и многократно перемещается к соседней вершине, что улучшает значение функции; когда улучшение невозможно, оптимальное значение функции достигнуто.

Если S это набор из менее чем d вершины, которые нужно удалить из графа многогранника, Балински добавляет еще одну вершину v0 к S и находит линейную функцию ƒ, которая имеет нулевое значение на расширенном множестве, но не является тождественным нулем на всем пространстве. Тогда любая оставшаяся вершина, в которой неотрицательна (включая v0) может быть соединена симплексными шагами с вершиной с максимальным значением, в то время как любая оставшаяся вершина, в которой неположительна (снова включая v0) аналогично соединяется с вершиной с минимальным значением. Следовательно, весь оставшийся граф связан.

Рекомендации

  1. ^ Циглер, Гюнтер М. (1995), "Раздел 3.5: Теорема Балински: График d-Связаны", Лекции по многогранникам, Тексты для выпускников по математике, 152, Springer-Verlag.
  2. ^ Балински, М.Л. (1961), «О графическом строении выпуклых многогранников в п-Космос", Тихоокеанский математический журнал, 11 (2): 431–434, Дои:10.2140 / pjm.1961.11.431, МИСТЕР 0126765.
  3. ^ Стейниц, Э. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der Mathematischen Wissenschaften, Полоса 3 (геометрии), стр. 1–139.