Hasse kaavio

FONT SIZE:
fontsize_dec
fontsize_inc
Lokakuu 30, 2016 Venla Oja H 0 0

Jotta Teoriassa Hasse kaavio on eräänlainen matemaattinen kaavio, jota käytetään edustamaan rajallinen osittain järjestetty joukko, muodossa piirustus sen transitiivisten vähentäminen. Konkreettisesti osittain järjestetty joukko yksi edustaa jokainen osa S kuin kärki tasossa ja piirtää jana tai käyrä, joka menee ylöspäin x-y aina y kattaa x. Nämä käyrät voivat ristiin mutta saa koskettaa mitään kärkipisteet muu kuin niiden parametrit. Tällainen kaavio, leimatun vertices, yksikäsitteisesti määrittää sen osittainen järjestys.

Hasse kaaviot on nimetty Helmut Hasse; mukaan Birkhoffin, ne ovat ns, koska tehokkaan käytön Hasse johdosta. Kuitenkin, Hasse ei ollut ensimmäinen käyttää näitä kaavioita; ne näkyvät, esim Vogt. Vaikka Hasse kaaviot alunperin määritetty kuin tekniikka tekee piirustukset osittain tilattu asetetaan käsin, ne ovat viime aikoina luotu automaattisesti kuvaajan piirtäminen tekniikoita.

Ilmaisu "Hasse kaavio" voi viitata myös transitiivinen vähentämistä abstrakti suunnattu asyklinen kuvaaja, riippumatta mistään piirustus kuvaajan, mutta tämä käyttö on karttoi täällä.

"Hyvä" Hasse kaavio

Vaikka Hasse kaaviot ovat yksinkertaisia ​​sekä intuitiivinen työkaluja käsitellä rajallinen Posets, se osoittautuu melko vaikea tehdä "hyvä" kaavioita. Syynä on se, että on yleisesti monia mahdollisia tapoja tehdä Hasse kaavio tietyn poset. Yksinkertaista tekniikkaa vain alkaa minimaalinen elementtejä järjestyksessä ja sitten piirustus enemmän elementtejä vähitellen tuottaa usein melko huonoja tuloksia: symmetriat ja sisäinen rakenne tilauksessa helposti menetetty.

Seuraava esimerkki osoittaa ongelman. Harkitse teho sarja 4-elementti set tilata osallisuutta. Alla on neljä eri Hasse kaavioita tämän osittaisen järjestyksessä. Kustakin seikasta on solmu merkitty binary koodaus, joka näyttää, onko tietty elementti on osajoukko tai ei:

Ensimmäinen kaavio tehdään selväksi, että valta sarja on porrastettu poset. Toinen kaavio on sama porrastettu rakenne, mutta tekemällä joitakin reunoista kauemmin kuin toiset, se korostaa, että 4-ulotteinen kuutio on unionin kahden 3-ulotteinen kuutiot. Kolmas kaavio osoittaa joitakin sisäisiä symmetriaa rakenteen. Neljännessä kaaviossa kärjet on järjestetty kuin aloilla 4 × 4 matriisi.

Ylöspäin tasomaisuuden

Jos osittaisjärjestys voida tehdä Hassen kaavio, jossa ei kaksi reunaa ylittää, sen kattaa kuvaaja sanotaan olevan ylöspäin tasomainen. Useita tuloksia ylöspäin tasaisuutta ja ylitettäessä vapaa Hassen kaavio rakentaminen ovat tunnettuja:

  • Jos osittainen jotta vedettävä on ristikko, niin se voidaan tehdä ilman risteykset jos ja vain jos se on järjestyksessä ulottuvuus korkeintaan kaksi. Tässä tapauksessa ei ylitykseen piirustus löytyy johtamalla suorakulmaiset koordinaatit elementtejä kantojaan kaksi lineaarista tilaukset ymmärtämättä järjestyksessä ulottuvuus, ja sitten kääntämällä piirustus vastapäivään 45 asteen kulmassa.
  • Jos osittainen järjestys on korkeintaan yksi minimaalinen elementti, tai se on korkeintaan yksi maksimaalinen elementti, se voidaan testata lineaarisessa ajassa, onko sillä ei-rajan Hasse kaavio.
  • Se on NP-täydellinen, onko osittaisjärjestys useita lähteitä ja nieluja voida tehdä ylitys vapaa Hasse kaavio. Kuitenkin löytää ylitys vapaa Hassen kaavio on kiinteä-parametri mukautuva kun parametrized useissa nivelpisteet ja triconnected komponentit transitiivinen vähentäminen osatilauksesta.
  • Jos y-koordinaatit elementtejä osittaisjärjestys on määritelty, niin ylitys vapaa Hassen kaavio kunnioittaen ne koordinoivat tehtäviä löytyy lineaarisessa ajassa, jos tällainen kaavio on olemassa. Erityisesti jos tulo poset on porrastettu poset, on mahdollista määrittää lineaarisessa ajassa, onko ylitys vapaa Hasse kaavio, jossa korkeus jokaista pistettä on verrannollinen sen listalla.
  0   0
Edellinen artikkeli Hister
Seuraava artikkeli Freddie Roman

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha