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

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

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

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

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

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

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

Примечания
  1. Ziegler, 1995.
  2. Balinski, 1961, с. 431–434.
  3. Steinitz, 1922, с. 1–139.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.