Теорема Балинского

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

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

Теорема Балинского названа именем математика Мишеля Балински^[en], опубликовавшего доказательство в 1961, хотя доказательство трёхмерного случая датируется началом 20-го века (теорема Штайница, что графы трёхмерных многогранников — это в точности трёхсвязные планарные графы).

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

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

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