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

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

20.01.2021


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

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

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

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

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