Теорема Балинского — это утверждение относительно структуры графа многогранника размерности 3 и выше. Теорема утверждает, что если образовать неориентированный граф из вершин и рёбер выпуклого d-мерного многогранника (его скелет[en]), то полученный граф по меньшей мере вершинно d-связен — удаление любого набора из d − 1 вершин оставляет связный подграф. Например, для трёхмерного многогранника, если удалить две вершины (вместе с инцидентными им рёбрами), для любой пары вершин существует путь, соединяющий эту пару[1].
Теорема Балинского названа именем математика Мишеля Балински[en], опубликовавшего доказательство в 1961[2], хотя доказательство трёхмерного случая датируется началом 20-го века (теорема Штайница, что графы трёхмерных многогранников — это в точности трёхсвязные планарные графы[3]).
Доказательство Балинского
Балински доказал свой результат, основываясь на корректности симплекс-метода для нахождения минимума или максимума линейной функции на выпуклом многограннике (задача линейного программирования). Симплекс-метод начинает с произвольной вершины многогранника и итеративно движется к смежной вершине с улучшением значения. Если не нашли улучшение, достигли оптимального значения функции.
Если из S удаляется множество из менее чем d вершин из графа многогранника, Балински добавляет к этому множеству вершину v0 многогранника S и находит линейную функцию ƒ, имеющую нулевое значение на расширенном множестве, но не тождественно нулю на всём пространстве. Тогда любая оставшаяся вершина, в которой ƒ неотрицательна (включая v0), может быть соединена шагами симплекс-метода с вершиной, имеющей максимальное значение функции ƒ, в то время как любая оставшаяся вершина, в которой ƒ не положительна (опять же, включая v0) может быть аналогичным образом соединена с вершиной, на которой достигается минимальное значение ƒ. Таким образом, весь оставшийся граф связан.
Примечания
- ↑ Ziegler, 1995.
- ↑ Balinski, 1961, с. 431–434.
- ↑ Steinitz, 1922, с. 1–139.
Литература
- Günter M. Ziegler. Section 3.5: Balinski's Theorem: The Graph is d-Connected // Lectures on Polytopes. — Springer-Verlag, 1995. — Т. 152. — (Graduate Texts in Mathematics).
- Balinski M. L. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11, вып. 2. — DOI:10.2140/pjm.1961.11.431.
- Steinitz E. Polyeder und Raumeinteilungen // Encyclopädie der mathematischen Wissenschaften. — 1922. — Т. Band 3 (Geometries). — С. 1–139.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .