Polyhedrien kombinatoriikka

Polyhedrien kombinatoriikka on matematiikan  haara , joka kuuluu kombinatoriikkaan ja kombinatoriseen geometriaan ja tutkii kuperoiden monitahojen kasvojen laskemisen ja kuvaamisen kysymyksiä .

Monitahoisten kombinatorioiden tutkimus jakautuu kahteen haaraan. Tällä alalla työskentelevät matemaatikot tutkivat polyhedrien kombinatoriikkaa ; he esimerkiksi etsivät epäyhtälöitä , jotka kuvaavat suhdetta mielivaltaisen monitahoisen eri mittaisten kärkien, reunojen ja pintojen lukumäärän välillä, ja tutkivat myös muita monitahojen kombinatorisia ominaisuuksia, kuten liitettävyyttä ja halkaisijaa (askelmien lukumäärää saavuttaa minkä tahansa kärjen mistä tahansa toisesta kärjestä). Lisäksi monet tietojenkäsittelytieteilijät käyttävät ilmaisua "polyhedrien kombinatoriikka" kuvaamaan tutkimusta, joka koskee tiettyjen monitahoisten pintojen tarkkaa kuvausta (erityisesti 0-1 polyhedraa, jonka kärjet ovat hyperkuution osajoukkoja), jotka johtuvat kokonaislukuohjelmointiongelmista .

Kasvot ja kasvojen laskentavektorit

Konveksin monitahoisen P pinta voidaan määritellä P : n ja suljetun puoliavaruuden H leikkauspisteeksi siten, että H :n raja ei sisällä P :n sisäpisteitä . Kasvojen mitta on yhtä suuri kuin tämän leikkauspisteen mitta. 0-ulotteiset pinnat ovat itse kärkipisteitä, kun taas 1-ulotteiset pinnat (kutsutaan reunat ) ovat viivasegmenttejä, jotka yhdistävät kärkipareja. Huomaa, että tämä määritelmä sisältää tyhjät joukot ja koko polytoopin P kasvoina . Jos P :llä on mitta d , P :n pintoja, joiden mitat ovat d  − 1, kutsutaan P :n faseteiksi ja mitan d  − 2 pintoja harjuiksi [1] . P :n pinnat voidaan järjestää osittain inkluusiona, jolloin muodostuu pintahila , jossa itse monitahoinen P on ylhäällä ja tyhjä joukko alhaalla.

Polytooppien kombinatoriikan avainmenetelmä on polytoopin ƒ -vektorin [2] huomioon ottaminen  — vektori ( f 0 , f 1 , …, f d  − 1 ), missä f i on i - ulotteisten pintojen lukumäärä polytooppia. Esimerkiksi kuutiolla on kahdeksan kärkeä, kaksitoista reunaa ja kuusi pintaa (viistettä), joten sen ƒ-vektori on (8,12,6). Kaksoispolyhedronissa on ƒ-vektori, jossa on samat numerot käänteisessä järjestyksessä. Joten esimerkiksi säännöllisellä oktaedrilla , joka on kaksoiskuution kanssa, on ƒ-vektori (6,12,8). Laajennettu ƒ-vektori muodostetaan lisäämällä ykköset ƒ-vektorin molempiin päihin, mikä vastaa kaikkien kasvohilan tasojen objektien luettelointia: f −1  = 1 heijastaa tyhjää joukkoa kasvona, kun taas f d  = 1 heijastaa itse P :tä . Kuutiolle laajennettu ƒ-vektori on (1,8,12,6,1) ja oktaedrin (1,6,12,8,1). Vaikka näiden esimerkkien vektorit ovat unimodaalisia (elementit vasemmalta oikealle kasvavat ensin ja sitten pienenevät), on korkeamman ulottuvuuden polyhedrejä, joille tämä ei pidä paikkaansa [3] .

Yksinkertaisille polytoopeille (polytoopeille, joissa jokainen pinta on simpleksi ) tämä vektori muunnetaan usein muodostamaan h -vektori. Jos tarkastellaan ƒ-vektorin alkioita (ilman äärellistä 1) polynomin ƒ( x ) = Σ f i x d  −  i  − 1 kertoimina (esim. oktaedrille tämä antaa polynomin ƒ( x ) ) =  x 3  + 6 x 2  + 12 x  + 8), niin h -vektori sisältää polynomin kertoimet h ( x ) = ƒ( x  − 1) (jälleen oktaedrin kohdalla h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . Kuten Ziegler kirjoittaa, "monisiin yksinkertaisiin polytooppeihin liittyviin ongelmiin h -vektorit ovat paljon kätevämpiä antamaan tietoa kasvojen lukumäärästä kuin f-vektorit."

Tasa-arvot ja epätasa-arvot

Monitahoisen ƒ-vektorin kertoimien tärkein suhde on Eulerin kaava Σ(−1) i f i = 0, jossa summa on laajennetun ƒ-vektorin alkioiden yli. Kolmessa ulottuvuudessa kahden 1:n siirtäminen laajennetun ƒ-vektorin (1, v , e , f , 1) vasemmalta ja oikealta puolelta tasa-arvon oikealle puolelle muuttaa yhtälön tutummaksi v − e + f = 2. Siitä tosiasiasta, että millä tahansa 3D-polyhedronin pinnalla on vähintään kolme reunaa, seuraa, että 2 e ≥ 3 f . Käyttämällä tätä lauseketta eliminoimaan e ja f Eulerin kaavasta, saamme e ≤ 3 v − 6 ja f ≤ 2 v − 4. Johtuen e ≤ 3 f − 6 ja v ≤ 2 f − 4 ​​kaksinaisuudesta. Steinitzin lause viittaa että mikä tahansa A 3-ulotteinen kokonaislukuvektori, joka tyydyttää nämä yhtäläisyydet ja epäyhtälöt, on konveksin monitahoisen ƒ-vektori [5] .

Korkeammissa ulottuvuuksissa muut polyhedronin pintojen lukumäärän väliset suhteet tulevat tärkeiksi, mukaan lukien Dehn-Somerville-yhtälö , joka ilmaistuna yksinkertaisten polytooppien h-vektoreina saa yksinkertaisen muodon h k = h d − k mille tahansa k . Näiden yhtälöiden muunnos k = 0 vastaa Eulerin kaavaa, mutta kun d > 3 nämä yhtälöt ovat lineaarisesti riippumattomia toisistaan ​​ja asettavat lisärajoituksia h -vektorille (ja siten ƒ-vektorille) [4] .

Toinen tärkeä epäyhtälö polytoopin pintojen lukumäärälle tulee McMullenin [6 ] ensimmäisenä todistamasta ylärajalauseesta , joka väittää, että d - ulotteisella polytooppilla, jossa on n kärkeä, ei voi olla enempää minkään ulottuvuuden kasvoja kuin viereisellä. polytooppi , jolla on sama määrä pisteitä:

jossa tähti tarkoittaa, että summan viimeinen termi on puolitettava, jos d on parillinen [7] . Tästä seuraa asymptoottisesti, että kasvoja ei voi olla enempää kuin kaikki mitat.

Jopa dimensiolle neljä, kaikkien mahdollisten kuperan monitahojen ƒ-vektorien joukko ei muodosta neliulotteisen kokonaislukuhilan kuperaa osajoukkoa, ja näiden vektorien mahdollisista arvoista on paljon epäselvää [8] .

Ominaisuudet graafiteoriasta

Polyhedrien pintojen lukumäärän ohella tutkijat tutkivat myös niiden muita kombinatorisia ominaisuuksia, kuten monitahoisten pisteistä ja reunoista saatujen graafien ominaisuuksia (niiden 1-luuranko ).

Balinskyn lauseessa todetaan, että mistä tahansa d - ulotteisesta konveksista polyhedronista tällä tavalla saatu graafi on kärki - d - kytketty [9] [10] . 3-polytoopin tapauksessa tätä ominaisuutta ja tasomaisuutta voidaan käyttää polytooppigraafien kuvaamiseen tarkasti – Steinitzin lause sanoo, että G on 3-polytoopin luuranko, jos ja vain jos G on kärkikolmeen yhdistetty tasograafi [11 ] .

Blind ja Money-Levitskin lause [12] (micha Perlesin olettamuksena) väittää, että sen graafista on mahdollista rekonstruoida yksinkertaisen polytoopin pintarakenne. Eli jos tietty suuntaamaton graafi on yksinkertaisen polytoopin luuranko, on olemassa vain yksi polytooppi (kombinatoriseen ekvivalenssiin asti), jolle graafi toimii luurankona. Tämä ominaisuus on jyrkässä ristiriidassa vierekkäisten (ei yksinkertaisten) polytooppien ominaisuuksien kanssa, joiden graafit ovat täydellisiä  – samassa graafissa voi olla monia erilaisia ​​vierekkäisiä polyedrejä. Toisen todisteen tälle lauseelle antoi Kalai [13] , ja Friedman [14] osoitti kuinka tätä lausetta käytetään luomaan polynomiaikaalgoritmi yksinkertaisten polyhedrien rakentamiseksi heidän graafistaan.

Yksipuolisen lineaarisen ohjelmoinnin yhteydessä on tärkeää ottaa huomioon monitahoisen halkaisija , minimimäärä pisteitä, jotka täytyy kulkea päästäkseen mihin tahansa kärkeen mistä tahansa muusta kärjestä. Lineaarisen ohjelmointitehtävän lineaaristen epäyhtälöiden järjestelmä määrittää tehtävän hyväksyttävien ratkaisujen monitahojen pinnat , ja simpleksimenetelmä löytää optimaalisen ratkaisun kulkemalla tämän monitahoisen reunoja pitkin. Siten halkaisija arvioi tämän menetelmän vaiheiden lukumäärän alarajan Kumottu Hirsch-oletus antoi vahvan ylärajan halkaisijalle [15] . Halkaisijan heikompi (quasi-polynomiaalinen) yläraja tunnetaan [16] , ja Hirsch-oletus on todistettu tietyille polyhedra-luokille [17] .

Laskennalliset ominaisuudet

Sen määrittäminen, rajoittaako tietyn polyhedronin kärkien lukumäärää jokin luonnollinen luku k , on vaikea tehtävä ja kuuluu kompleksisuusluokkaan PP [18] .

0-1 polyhedran kasvot

Kokonaislukuohjelmoinnin katkaisumenetelmien yhteydessä on tärkeää pystyä kuvaamaan tarkasti ne monitahoisen viisteet (pinnat), joilla kärjet sijaitsevat, mikä vastaa kombinatoristen optimointitehtävien ratkaisuja. Usein tällaisissa ongelmissa on ratkaisuja, jotka voidaan antaa bittivektoreilla ja vastaavilla polyhedrillä on kärkipisteitä, joiden koordinaatit ovat luvut nolla ja yksi.

Otetaan esimerkkinä Birkhoffin polyhedri , n  ×  n matriisin joukko, joka voidaan muodostaa permutaatiomatriisien konveksilla yhdistelmillä . Vastaavasti tämän polytoopin kärjet voidaan ymmärtää täydellisen kaksiosaisen graafin kaikkien täydellisten vastaavuuksien kuvauksena , ja tämän polytoopin lineaarista optimointiongelmaa voidaan pitää painotetun minimitäydellisen vastaavuuden löytämisen ongelmana. Birkhoffin lause sanoo, että tällainen monitahoinen voidaan kuvata käyttämällä kahden tyyppisiä lineaarisia epäyhtälöitä. Ensinnäkin matriisin jokainen elementti on ei-negatiivinen, ja toiseksi jokaiselle sarakkeelle ja jokaiselle riville matriisielementtien summa on yhtä suuri kuin yksi. Rivien ja sarakkeiden summan rajoitukset määrittelevät lineaarisen aliavaruuden dimensiolla n 2  − 2 n  + 1, jossa Birkhoffin polyhedri sijaitsee, ja rajoitukset matriisielementtien ei-negatiivisuudelle määrittelevät polytoopin pinnat tässä aliavaruudessa.

Birkhoffin monitahoinen on epätavallinen siinä mielessä, että sen kasvot tunnetaan täydellisesti. Monilla muilla 0-1-polyhedreillä on eksponentiaalisesti (tai supereksponentiaalisesti) monta pintaa, ja niistä on saatavilla vain osittainen kuvaus [19] .

Katso myös

Muistiinpanot

  1. ↑ Ziegler, 1995 , s. 51.
  2. ↑ Ziegler, 1995 , s. 245-246.
  3. ↑ Ziegler, 1995 , s. 272.
  4. ↑ 12 Ziegler , 1995 , s. 246-253.
  5. ↑ Steinitz, 1906 .
  6. ↑ McMullen, 1970 .
  7. ↑ Ziegler, 1995 , s. 254-258.
  8. ↑ Höppner, Ziegler, 2000 .
  9. ↑ Balinski, 1961 .
  10. ↑ Ziegler, 1995 , s. 95–96.
  11. ↑ Ziegler, 1995 , s. 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 ja Kiefer 2015 , s. Thm. 5.
  19. ↑ Ziegler, 2000 .

Kirjallisuus

Linkit