Sonkásszendvicstétel

A Wikipédiából, a szabad enciklopédiából

A sonkásszendvicstétel a mértékelmélet és a topológia egy tétele. Azt állítja, hogy ha adva van az n-dimenziós térben n páronként diszjunkt test úgy, hogy mindegyik minden irányban elfelezhető, akkor van egy hipersík, ami mindegyiket elfelezi. Az elfelezés érthető úgy is, hogy az n-dimenziós térfogatot felezi. Véges ponthalmazokra alkalmazva az elemszám a mérték. Nevezik Stone–Tukey-tételnek is.

Története[szerkesztés | forrásszöveg szerkesztése]

Beyer és Zardecki cikke (2004) szerint a tétel első változata, speciálisan a háromdimenziós esetre, Steinhausnál bukkant fel először 1938-ban. Beyer és Zardecki cikke tartalmazza Steinhaus cikkének fordítását. Steinhaus kétféleképpen is leírta, formálisan: Elfelezhető-e mindig két test egy síkkal, akárhol is vannak a térben? és informálisan: Kettévágható-e késsel egy sonka úgy, hogy a vágás a húst, a csontot és a zsírt is elfelezze? A cikk a Borsuk–Ulam-tétel felhasználásával be is bizonyítja a tételt. Az általános esetet Stone és Tukey (1942) oldotta meg. Az n=3 speciális esetet S. M. Ulamnak tulajdonították, ám Beyer és Zardecki szerint tévesen.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Ez a háromdimenziós eset bizonyítása. Más dimenziókban hasonlóan látható be.

Tekintjük az adott irányú síkok közös normálvektorát, v-t. A normálvektor és a síkok közötti kapcsolat folytonos. Nevezzük ezeket a síkokat σA-nak, σB-nek és σC-nek. Jelölje f1 a σA és a σB síkok, és f2 a σA és a σC távolságát úgy, hogy v iránya pozitív. Legyen f(v)=(f1(v),f2(v)). Ez egy páratlan függvény, mivel előjeles távolságokat mér. A Borsuk–Ulam-tétel szerint viszont van v vektor, amire ugyanazok lesznek a távolságok. Ez csak úgy lehet, ha ezek a távolságok mind nullák, vagyis a síkok egybeesnek.

Mértékelméleti változatai[szerkesztés | forrásszöveg szerkesztése]

Stone és Tukey a tétel két általánosabb formáját is bizonyította. Mindkét verzió az n-dimenziós tér egy X halmazának elfelezéséről szól, ahol is az X halmaz n diszjunkt részből áll. Az X halmaznak van külső Carathéodory-mértéke, és a diszjunkt X1, X2,… Xn halmazok külső X1-mértéke véges.

Az egyik általánosítás szerint minden f : S^n \times X \to \mathbb{R} függvényhez van olyan p pontja az Sn gömbnek, hogy az f(p,x) = 0 felület felezi nemcsak X, hanem X1, X2,… Xn külső Carathéodory-mértékét is. Ez szintén belátható a Borsuk–Ulam tétellel.

A másik általánosítás szerint, ha X-en értelmezve vannak az f0, f1, …, fn mérhető függvények, amik lineárisan függetlenek X egy pozitív mértékű részhalmazán, akkor van olyan f=a0f0+a1f1+ … +anfn lineáris kombinációjuk, hogy az f(x)=0 felület felezi nemcsak X, hanem X1, X2,… Xn külső Carathéodory-mértékét is.

A véges és a számítógépi geometriában[szerkesztés | forrásszöveg szerkesztése]

A véges és a számítógépi geometriában a sonkásszendvicstételt véges ponthalmazokra vonatkoztatják. Itt a mértéket a halmazok elemszáma adja. Tehát a tétel szövege a síkbeli esetre vonatkoztatva:

Akárhogy is van megadva a síkon véges sok piros és véges sok kék pont, mindig van egyenes, ami úgy osztja két részre a síkot, hogy a piros és a kék pontok halmazát is megfelezi, vagyis az egyenes egyik oldalán levő piros pontok száma megegyezik a másik oldalon levő piros pontok számával, és ugyanígy, az egyenes egyik oldalán fekvő kék pontok száma egyenlő a másik oldalon fekvő kék pontok számával.

Egyes konfigurációk esetén a felező egyenes átmegy néhány piros, vagy kék ponton. Ez történik például, ha valamelyik ponthalmaz páratlan sok pontból áll, de megeshet akkor is, ha a piros és a kék pontok száma egyaránt páros. Ezekben az esetekben mindkét oldalhoz hozzászámítjuk azokat a pontokat, amik illeszkednek az egyenesre, azaz ha szigorúan vesszük, akkor mindkét oldalra a pontoknak legfeljebb a fele került. A tétel ekkor is teljesül.

A számítógépi geometriában megfogalmazott feladat a sonkásszendvics feladat: adva van a síkon néhány piros és kék pont, keressünk hozzájuk egy felező egyenest! Az első algoritmus Megiddotól származik (1985) arra a speciális esetre, amikor a piros és a kék pontok egy egyenessel elválaszthatók. Ekkor Megiddo algoritmusa lineáris időben talált felező vágást. Edelsbrunner és Waupotitsch algoritmusa (1986) az általános esetben is működött O(n log n) futási idővel, ahol is 'O a nagy ordo jelölés. Lo és Steiger algoritmusa (1990) már lineáris időben talált felező vágást. Lo, Matoušek és Steiger ezt az algoritmust (1994) kiterjesztette magasabb dimenziós esetekre is.

Felhasznált források[szerkesztés | forrásszöveg szerkesztése]

  • Szűcs András: Topológia

Beyer, W. A. & Zardecki, Andrew (2004), "The early history of the ham sandwich theorem", American Mathematical Monthly 111 (1): 58–61, doi:10.2307/4145019, <http://proquest.umi.com/pqdweb?did=526216421&Fmt=3&clientId=5482&RQT=309&VName=PQD>.

Edelsbrunner, H. & Waupotitsch, R. (1986), "Computing a ham sandwich cut in two dimensions", J. Symbolic Comput. 2: 171–178, DOI 10.1016/S0747-7171(86)80020-7.

Lo, Chi-Yuan & Steiger, W. L. (1990), "An optimal time algorithm for ham-sandwich cuts in the plane", Proceedings of the Second Canadian Conference on Computational Geometry, pp. 5–9.

Lo, Chi-Yuan; Matoušek, Jiří & Steiger, William L. (1994), "Algorithms for Ham-Sandwich Cuts", Discrete and Computational Geometry 11: 433–452, DOI 10.1007/BF02574017.

Megiddo, Nimrod (1985), "Partitioning with two lines in the plane", Journal of Algorithms 6: 430–433, DOI 10.1016/0196-6774(85)90011-2.

Steinhaus, Hugo (1938), "A note on the ham sandwich theorem", Mathesis Polska 9: 26–28.

Stone, A. H. & Tukey, J. W. (1942), "Generalized "sandwich" theorems", Duke Mathematical Journal 9: 356–359, doi:10.1215/S0012-7094-42-00925-6, <http://projecteuclid.org/euclid.dmj/1077493229>.

Ajánlott források[szerkesztés | forrásszöveg szerkesztése]

Fordítás[szerkesztés | forrásszöveg szerkesztése]

Ez a szócikk részben vagy egészben a Ham sandwich theorem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.