A poliéderek kombinatorikája

A poliéderek kombinatorikája a matematikának a kombinatorikához és a kombinatorikus geometriához tartozó  ága , amely a konvex poliéderek lapjainak megszámlálásának és leírásának kérdéseit vizsgálja .

A poliéderek kombinatorikájának kutatása két ágra oszlik. Az ezen a területen dolgozó matematikusok a poliéderek kombinatorikáját tanulmányozzák; például olyan egyenlőtlenségeket keresnek, amelyek leírják egy tetszőleges poliéderben a csúcsok, élek és különböző méretű lapok száma közötti összefüggést, és tanulmányozzák a poliéderek egyéb kombinatorikus tulajdonságait is, mint például az összekapcsolhatóságot és az átmérőt (az eléréshez szükséges lépések száma). bármely más csúcsból elérje bármely csúcsot). Ezenkívül sok számítástechnika területén dolgozó tudós használja a "poliéderek kombinatorikája" kifejezést bizonyos poliéderek (különösen 0-1 poliéderek, amelyek csúcsai a poliéderek részhalmazai) lapjainak pontos leírására irányuló kutatásokat írja le.hypercube ) egészszámú programozási problémákból adódóan .

Arcok és arcszámláló vektorok

Egy P konvex poliéder lapja úgy definiálható, mint P és egy zárt H féltér metszéspontja úgy, hogy H határa nem tartalmaz P belső pontjait . Egy lap mérete megegyezik ennek a metszéspontnak a méretével. A 0-dimenziós lapok maguk a csúcsok, míg az 1-dimenziós lapok (úgynevezett élek ) csúcspárokat összekötő vonalszakaszok . Ne feledje, hogy ez a definíció magában foglalja az üres halmazokat és a teljes P politópot lapként . Ha P mérete d , akkor P d − 1 méretű lapjait P lapjainak  , a d − 2 dimenziójú  lapjait pedig gerinceknek [ 1] nevezzük . A P lapjai részben befoglalással rendezhetők , olyan laprácsot alkotva, amelyen felül a P poliéder , alul az üres halmaz áll.

A politópok kombinatorikájának kulcsfontosságú módszere a politóp ƒ-vektorának [2] figyelembevétele – a vektor  ( f 0 , f 1 , …, f d  − 1 ), ahol f i az i - dimenziós lapok száma . a politóp. Például egy kockának nyolc csúcsa, tizenkét éle és hat lapja (ferde szöge) van, tehát a ƒ-vektora (8,12,6). A kettős poliédernek van egy ƒ-vektora ugyanazokkal a számokkal fordított sorrendben. Így például a szabályos oktaédernek , amely duális a kockával, van ƒ-vektora (6,12,8). A kiterjesztett ƒ-vektort úgy alakítjuk ki, hogy az ƒ-vektor mindkét végéhez hozzáadunk egyet, ami megfelel az arcrács minden szintjén lévő objektumok felsorolásának: f −1  = 1 az üres halmazt lapként tükrözi, míg f d  = 1 magát a P -t tükrözi . Kocka esetén a kiterjesztett ƒ-vektor (1,8,12,6,1), oktaédernél pedig (1,6,12,8,1). Bár ezeknek a példáknak a vektorai unimodálisak (a balról jobbra haladó elemek először növekednek, majd csökkennek), vannak magasabb dimenziós poliéderek, amelyekre ez nem igaz [3] .

Egyszerű politópok esetén (olyan politópok, ahol minden lap szimplex ), ezt a vektort gyakran transzformálják h vektorgá. Ha az ƒ-vektor elemeit (véges 1 nélkül) az ƒ( x ) = Σ f i x d  −  i  − 1 polinom együtthatóinak tekintjük (például egy oktaédernél ez az ƒ( x ) polinomot adja ) =  x 3  + 6 x 2  + 12 x  + 8), akkor a h -vektor tartalmazza a h ( x ) = ƒ( x − 1) polinom együtthatóit  (egy oktaédernél ismét h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . Ahogy Ziegler írja, „az egyszerű politópokkal kapcsolatos különféle problémákhoz a h - vektorok sokkal kényelmesebbek az oldalak számáról való információadásra, mint az f-vektorok”.

Egyenlőségek és egyenlőtlenségek

A poliéder ƒ-vektorának együtthatóinak legfontosabb hányadosa a Σ(−1) i f i = 0 Euler-képlet , ahol az összegzés a kiterjesztett ƒ-vektor elemei felett van. Három dimenzióban a kiterjesztett ƒ-vektor (1, v , e , f , 1) bal és jobb oldaláról két 1-est az egyenlőség jobb oldalára mozgatva az egyenlőség az ismerősebb v − e + f = -vé alakul. 2. Abból, hogy egy 3D poliéder bármely lapjának legalább három éle van, az következik, hogy 2 e ≥ 3 f . Ezzel a kifejezéssel e és f kiküszöbölésére az Euler-képletből azt kapjuk, hogy e ≤ 3 v − 6 és f ≤ 2 v − 4. Az e ≤ 3 f − 6 és v ≤ 2 f − 4 ​​kettőssége miatt. Steinitz tétele arra utal , hogy hogy bármely A háromdimenziós egész vektor, amely kielégíti ezeket az egyenlőségeket és egyenlőtlenségeket, egy konvex poliéder ƒ-vektora [5] .

Nagyobb dimenziókban a poliéder lapjainak száma közötti egyéb összefüggések is fontossá válnak, beleértve a Dehn-Somerville-egyenletet , amely egyszerű politópok h-vektoraiban kifejezve a h k = h d − k egyszerű alakot ölti bármelyikre. k . Ezen egyenletek k = 0 változata ekvivalens az Euler-formulával, de d > 3 esetén ezek az egyenletek lineárisan függetlenek egymástól, és további megszorításokat írnak elő a h -vektorra (és így a ƒ-vektorra is) [4] .

Egy másik fontos egyenlőtlenség a politóp lapjainak számára a felső korlátos tételből származik, amelyet először McMullen [6] bizonyított be , és amely kimondja, hogy egy n csúcsú d -dimenziós politópnak nem lehet több lapja, mint egy szomszédosnak. politóp azonos számú csúcsgal:

ahol a csillag azt jelenti, hogy az összeg utolsó tagját meg kell felezni, ha d páros [7] . Ebből aszimptotikusan következik, hogy nem lehet több minden dimenziójú lapnál.

A konvex poliéderek összes lehetséges ƒ-vektorának halmaza még a négyes dimenzió esetében sem képezi a négydimenziós egészrács konvex részhalmazát, és sok minden nem világos ezen vektorok lehetséges értékeivel kapcsolatban [8] .

Tulajdonságok a gráfelméletből

A poliéderek lapjainak számával együtt a kutatók egyéb kombinatorikus tulajdonságaikat is vizsgálják, például a poliéderek csúcsaiból és éleiből nyert gráfok tulajdonságait (az 1-vázuk ).

Balinsky tétele kimondja, hogy egy tetszőleges d -dimenziós konvex poliéderből így kapott gráf csúcs - d -összefüggésben van [9] [10] . A 3-politópok esetében ez a tulajdonság és síkság felhasználható politópgráfok pontos leírására – Steinitz tétele kimondja, hogy G akkor és csak akkor egy 3-politóp váza, ha G egy csúcs-3-as síkgráf [11 ] .

Blind és Money-Levitsk tétele [12] (amelyet Micha Perles sejtéseként fogalmazott meg) kimondja, hogy lehetséges egy egyszerű politóp arcszerkezetét rekonstruálni a gráfjából . Vagyis ha egy adott irányítatlan gráf egy egyszerű politóp váza, akkor csak egy politóp van (a kombinatorikus ekvivalenciáig), amelyhez a gráf vázként szolgál. Ez a tulajdonság éles ellentétben áll a szomszédos (nem egyszerű) politópok tulajdonságaival, amelyek gráfjai teljesek  – sok különböző szomszédos poliéder lehet ugyanazzal a gráfgal. Ennek a tételnek egy másik bizonyítékát Kalai [13] adta meg , és Friedman [14] megmutatta, hogyan lehet ezzel a tétellel polinomiális idő algoritmust létrehozni egyszerű poliéderek gráfjaikból való felépítésére.

A szimplex lineáris programozással összefüggésben fontos figyelembe venni a poliéder átmérőjét , azon csúcsok minimális számát, amelyeken be kell haladni, hogy bármely más csúcsból bármely csúcsot elérjünk. Egy lineáris programozási feladat lineáris egyenlőtlenségeinek rendszere határozza meg a probléma megengedhető megoldásai poliéderének lapjait , és a szimplex módszer ennek a poliédernek az élei mentén haladva megtalálja az optimális megoldást. Így az átmérő kiértékeli ennek a módszernek a lépésszámának alsó korlátját . A megcáfolt Hirsch-sejtés erős felső korlátot adott az átmérőnek [15] . Az átmérő gyengébb (kvázi-polinomiális) felső korlátja ismert [16] , és a Hirsch-sejtés bizonyos poliéderosztályokra bebizonyosodott [17] .

Számítási tulajdonságok

Annak meghatározása, hogy egy adott poliéder csúcsainak számát határolja-e valamilyen k természetes szám , nehéz feladat, és a PP összetettségi osztályba tartozik [18] .

0-1 poliéderek arcai

Az egész programozás levágási módszereivel összefüggésben fontos, hogy a kombinatorikus optimalizálási feladatok megoldásainak megfelelően pontosan le tudjuk írni a poliéder letöréseit (lapjait), amelyeken a csúcsok fekszenek. Az ilyen problémáknak gyakran vannak megoldásai, amelyek bitvektorokkal adhatók meg , és a megfelelő poliédereknek vannak olyan csúcsai, amelyek koordinátái a nulla és az egyes számok.

Példaként vegyük a Birkhoff poliédert , egy n  ×  n mátrixból álló halmazt, amely permutációs mátrixok konvex kombinációival alakítható ki . Hasonlóképpen, ennek a politópnak a csúcsai felfoghatók a teljes bipartit gráf összes tökéletes illeszkedésének leírásaként , és a lineáris optimalizálási probléma ezen a politópon egy súlyozott minimum tökéletes illeszkedés megtalálásának problémájának tekinthető. Birkhoff tétele kimondja, hogy egy ilyen poliéder kétféle lineáris egyenlőtlenséggel írható le. Először is, a mátrix minden eleme nem negatív, másodszor pedig minden oszlopra és minden sorra a mátrixelemek összege eggyel egyenlő. A sorok és oszlopok összegére vonatkozó korlátozások egy n 2  − 2 n  + 1 dimenziójú lineáris alteret határoznak meg, amelyben a Birkhoff-poliéder található, és a mátrixelemek nem-negativitására vonatkozó korlátozások határozzák meg a politóp lapjait ebben az altérben.

A Birkhoff poliéder szokatlan, mivel lapjainak teljes leírása ismert. Sok más 0-1 poliédernek exponenciálisan (vagy szuperexponenciálisan) sok lapja van, és csak részleges leírásuk áll rendelkezésre [19] .

Lásd még

Jegyzetek

  1. ↑ Ziegler, 1995 , p. 51.
  2. ↑ Ziegler, 1995 , p. 245–246.
  3. ↑ Ziegler, 1995 , p. 272.
  4. ↑ 12 Ziegler , 1995 , p. 246–253.
  5. ↑ Steinitz, 1906 .
  6. ↑ McMullen, 1970 .
  7. ↑ Ziegler, 1995 , p. 254–258.
  8. ↑ Höppner, Ziegler, 2000 .
  9. ↑ Balinski, 1961 .
  10. ↑ Ziegler, 1995 , p. 95–96.
  11. ↑ Ziegler, 1995 , p. 103–126.
  12. ↑ Blind, Mani-Levitska, 1987 .
  13. ↑ Kalai, 1988 .
  14. ↑ Friedman, 2009 .
  15. ↑ Santos, 2012 .
  16. ↑ Kalai, Kleitman, 1992 .
  17. ↑ Naddef (1989) .
  18. ↑ Haase és Kiefer 2015 , p. Thm. 5.
  19. ↑ Ziegler, 2000 .

Irodalom

Linkek