Gamma-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. tammikuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Gamma-algoritmi  on algoritmi graafin asettamiseen litteäksi ja sen tasaisuuden tarkistamiseksi matkan varrella .

Määritelmät

Algoritmi

Aseta tasolle mikä tahansa graafin G sykli H ilman kärkien toistoja.

  1. Muodosta graafin G kaikki segmentit S 1 ,..,S k H :stä .
  2. Jos segmentillä S i on yksi sallittu pinta  , valitse se.
  3. Jos kaikilla segmenteillä on useita lisäpintoja, valitse mikä tahansa.
  4. Valitse segmentin mielivaltainen gammaketju ja sovita se sallittuun pintaan.
  5. Siirry vaiheeseen (2) lisäämällä gammaketju H -kaavioon .

Kaavioiden ominaisuudet algoritmin oikeaan toimintaan

  1. Kaavio on yhdistettävä .
  2. Kaaviossa on oltava vähintään yksi sykli .
  3. Graafissa ei saa olla siltoja eli reunoja, joiden poistamisen jälkeen graafi jakautuu kahdeksi yhdistetyksi komponentiksi .

Jos ominaisuutta (1) rikotaan, kaavio on pinottava erikseen yhdistettyjen komponenttien mukaan. Jos ominaisuutta (2) rikotaan, graafi on puu ja on triviaalia piirtää sen litistys.

Omaisuusrikkomusta (3) käsitellään tarkemmin. Jos kaaviossa on siltoja, ne on leikattava, jokainen yhdistetty komponentti tulee litistää erikseen ja yhdistää sitten silloilla. Tässä voi syntyä vaikeus: asennuksen aikana sillan päätypisteet voivat olla tasograafin sisällä. Piirretään yksi yhdistetty komponentti ja lisätään siihen muita peräkkäin. Jokainen uusi yhdistetty komponentti piirretään pinnalle, joka sisältää vastaavan sillan päätypisteen. Koska yhdistettyjen komponenttien siltojen liitettävyyden kuvaaja on puu, voimme saada tasaisen pakkauksen.

Lause

Graafi Г on tasomainen, jos ja vain jos gamma-algoritmi sijoittaa sen tasolle.

Todiste

Päinvastaiseen suuntaan todiste on ilmeinen.

Todistakaa se suoraan. Jos kuvaaja Γ on tasomainen, niin tasolle aseteltu osagraafi H voidaan täydentää kuvaajan Γ asettamiseen . Erityisesti viimeisellä askeleella tämä tarkoittaa, että kuvaaja Γ on täysin aseteltu tasolle.

Olkoon kuvaaja Γ tasomainen. Sitten mikä tahansa kaavion Γ sykli esitetään monikulmiona pinottuna. Tämä monikulmio sisältyy graafin Γ asettamiseen tasolle.

Olkoon väite tosi algoritmin n. iteraatioon asti.

Vaihtoehdot:

  1. S sopii graafin H ainoaan pintaan, graafi H täydentyy graafin G taitteeseen , ja tässä taitteessa segmentti S on ainoassa pinnassa. Näin ollen minkä tahansa segmentin S gammapolun C upottaminen tähän pintaan johtaa graafin H yhdistämiseen C : n kanssa , joka voidaan laajentaa laatoitukseen Г.
  2. Jokaisella segmentillä on useita kelvollisia kasvoja.

Olkoon S  jana, jonka sallitut pinnat ovat F 1 ja F 2 . Aligraafi H täydentyy graafin Г asettamiseen induktiivisen hypoteesin avulla. Tässä tapauksessa segmentti S sopii yhteen hyväksytyistä pinnoista. Yleisyyttä menettämättä olkoon tämä kasvo F 1 . Osoitetaan, että H :lla on jatke graafin Г asettamiseen asti, jossa jana S on kasvossa F 2 . Koska F 1 ja F 2  ovat lisäpintoja, ne molemmat sisältävät segmentin S kaikki kosketuspisteet . Siksi kaikki segmentin S kosketuspisteet ovat yhteisten kärkien F 1 ja F 2 joukossa . Olkoon S 1 ,..,S k kaikki F 1  :n sisältämät segmentit . Olkoon S ' 1 ,..,S ' m  kaikki segmentit F 2 :ssa , jotka sisältävät yhden pisteistä. Olkoon segmentillä S ' i kontaktipiste ja toinen kontaktipiste, joka ei kuulu F 1 : een . Tällöin sallitut kasvot S ' i ovat kasvot F 2 , ja tämä on pisteen (2) oletus. Ristiriikasta seuraa, että kaikki kosketuspisteet S ' i (samalla tavalla kuin S i ) ovat segmenttien S ' 1 ,..,S ' m kärkijoukossa .

Siksi graafin G asettelussa on mahdollista siirtää segmentit S 1 ,..,S k kohtaan F 2 ja S ' 1 ,..,S ' m asentoon F 1 , mikä johtaa asettamiseen kuvaajan Г , jossa jana S on kasvossa F 2 .

Siksi algoritmi sovittaa minkä tahansa tasograafin tasolle. Mitä vaadittiin.

Katso myös

Kirjallisuus