Balinski-tétel

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 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.

A Balinski-tétel névadója Michel Balinski matematikus, aki bizonyítását 1961-ben publikálta, 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.

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.