В полиэдральной комбинаторике , разделе математики, теорема Балински представляет собой утверждение о теоретико-графической структуре трехмерных многогранников и многомерных многогранников . Он утверждает, что если составить неориентированный граф из вершин и ребер выпуклого d -мерного многогранника или многогранника (его скелета ), то полученный граф будет как минимум d- вершинно-связным : удаление любого d - 1 вершина выходит из связного подграфа. Например, для трехмерного многогранника, даже если две его вершины (вместе с их инцидентными ребрами) будут удалены, для любой пары вершин все равно будет существовать путь из вершин и ребер, соединяющих пару. [1]
Теорема Балински названа в честь математика Мишеля Балински , который опубликовал свое доказательство в 1961 году [2], хотя трехмерный случай восходит к началу 20 века и к открытию теоремы Стейница о том, что графы трехмерных многогранников являются ровно трехсвязные плоские графы. [3]
Доказательство Балинского
Балински доказывает результат, основанный на корректности симплексного метода нахождения минимума или максимума линейной функции на выпуклом многограннике ( задача линейного программирования ). Симплексный метод начинается с произвольной вершины многогранника и многократно перемещается к соседней вершине, что улучшает значение функции; когда улучшение невозможно, оптимальное значение функции достигнуто.
Если S представляет собой набор из менее чем d вершин, которые нужно удалить из графика многогранника, Балински добавляет еще одну вершину v 0 к S и находит линейную функцию ƒ, которая имеет нулевое значение на расширенном множестве, но не является тождественно нулевым на все пространство. Тогда любая оставшаяся вершина, в которой неотрицательна (включая v 0 ), может быть соединена симплексными шагами с вершиной с максимальным значением ƒ, в то время как любая оставшаяся вершина, в которой неположительна (опять же, включая v 0 ) аналогично можно связать с вершиной с минимальным значением. Следовательно, весь оставшийся граф связан.
Рекомендации
- ↑ Ziegler, Günter M. (1995), «Раздел 3.5: Теорема Балински: граф d- связан», Лекции по многогранникам , Тексты для выпускников по математике , 152 , Springer-Verlag.
- ^ Balinski, М. Л. (1961), "О структуре графа выпуклых многогранников в п - пространстве" , Тихоокеанский журнал математики , 11 (2): 431-434, DOI : 10,2140 / pjm.1961.11.431 , МР 0126765.
- ^ Стейниц, Э. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der Mathematischen Wissenschaften , Band 3 (Geometries) , стр. 1–139.