Balinski-tétel

A matematika, azon belül a poliéder-kombinatorika területén a Balinski-tétel a háromdimenziós poliéderek, valamint a magasabb dimenziós politópok gráfelméleti szerkezetéről tanúskodik. Kimondja, hogy egy konvex, d dimenziós poliéder vagy politóp csúcsaiból és éleiből irányítatlan gráfot (a politóp vázát) alkotva, az eredményül kapott gráf d-szeresen összefüggő: d − 1 tetszőleges csúcsát eltávolítva összefüggő marad. Például egy poliéder bármely két csúcsát (a hozzájuk vezető élekkel együtt) eltávolítva továbbra is bármely csúcspár esetén létezik őket összekötő csúcsokból és élekből álló útvonal.^[1]

Bármely két csúcs (sárgával jelölve) eltávolításával nem lehet egy háromdimenziós poliédert szétszedni: mindig választható egy harmadik csúcs (zölddel) és egy nemtriviális lineáris függvény, melynek zérushalmaza (kékkel) áthalad ezen a három csúcson, lehetővé téve a kiválasztott csúcsból a függvény minimális és maximális értékű csúcsához való csatlakozást, így bármely csúcsból a minimális és maximális értékű csúcshoz való csatlakozást.

A Balinski-tétel névadója Michel Balinski matematikus, aki bizonyítását 1961-ben publikálta,^[2] bár a háromdimenziós eset a 20. század első felére, a Steinitz-tételhez (1922) nyúlik vissza, ami szerint a háromdimenziós poliéderek gráfjai éppen a háromszorosan összefüggő síkbarajzolható gráfok.^[3]

Balinski bizonyítása

Balinski bizonyítása a konvex politóp lineáris függvénye minimumának vagy maximumának megkeresésére (a lineáris programozási probléma) szolgáló szimplex algoritmusának korrektségén alapul. A szimplex módszer a politóp tetszőleges csúcsából kiindulva ismételten egy olyan szomszédos csúcs felé mozog, ami növeli a függvény értékét; ha már nem érhető el javulás, az algoritmus elért az optimális függvényértékhez.

Legyen S egy d-nél kevesebb csúcsból álló halmaz, amit a politóp gráfjából el kell távolítani; Balinski egyetlen új, v₀ csúcsot ad S-hez, majd talál egy lineáris ƒ függvényt, aminek az értéke a kiegészített halmazon nulla, de az egész teret tekintve nem identikusan nulla. Ekkor bármely megmaradó csúcs, melyre ƒ értéke nem negatív (beleértve v₀-t) egyszerű lépésekkel összeköthető azzal a csúccsal, melyhez ƒ maximális értéke tartozik, míg bármely megmaradó csúcs, melyre ƒ értéke nem pozitív (ismét ideértve v₀-t is) hasonlóan összeköthető azzal a csúccsal, melyhez ƒ minimális értéke tartozik. Ebből az következik, hogy a teljes megmaradó gráf is összefüggő.

Fordítás

Ez a szócikk részben vagy egészben a Balinski's theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Ziegler, Günter M. (1995), "Section 3.5: Balinski's Theorem: The Graph is d-Connected", Lectures on Polytopes, vol. 152, Graduate Texts in Mathematics, Springer-Verlag.
↑ Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, <http://projecteuclid.org/euclid.pjm/1103037323>.
↑ Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1–139.

[1] Ziegler, Günter M. (1995), "Section 3.5: Balinski's Theorem: The Graph is d-Connected", Lectures on Polytopes, vol. 152, Graduate Texts in Mathematics, Springer-Verlag.

[2] Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, <http://projecteuclid.org/euclid.pjm/1103037323>.

[3] Steinitz, E. (1922), "Polyeder und Raumeinteilungen", Encyclopädie der mathematischen Wissenschaften, Band 3 (Geometries), pp. 1–139.

[1]

[2]

[3]