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

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

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

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

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

Примечания

Литература