Taivutuksen minimointi

Graafeja visualisoitaessa , kun graafin reunat esitetään katkoviivoilla ( katkopisteissä yhdistettyjen segmenttien sarja ), on toivottavaa minimoida katkosten määrä reunaa kohti (jota joskus kutsutaan käyrän monimutkaisuus ) [1] tai kokonaismäärä katkoksista kuvassa [2] . Taivutuksen minimointi on algoritminen tehtävä löytää kaaviokuvio, joka minimoi määritetyt arvot [3] [4] .

Kierteiden poissulkeminen

Klassinen esimerkki mutkan minimoinnista on Farin teoreema , jonka mukaan mikä tahansa tasograafi voidaan piirtää ilman mutkia, eli voit löytää tasograafin upotuksen, jossa kaikki reunat esitetään segmenteillä [5] .

Graafiesitystä, jossa reunat eivät ole taittuneet ja ovat samansuuntaisia ​​akselien kanssa, kutsutaan joskus suorakaiteen muotoiseksi esitykseksi ja se on yksi muunnelmista ortogonaalisen reunaleikkauksen esityksestä , jossa kaikki reunaleikkaukset ovat suorissa kulmissa [6] . Kuitenkin sen määrittäminen, onko tasograafilla suorakaiteen muotoinen esitys, on NP-täydellinen tehtävä [7] . On myös NP-täydellinen ongelma määrittää, onko mielivaltaisella graafilla suorakaiteen muotoinen esitys tietyillä reunaleikkauksilla [6] .

Taivutuksen minimointi

Tamassia osoitti, että taittumien minimointi tasograafien ortogonaalisessa kuviossa, jossa kärjet sijaitsevat kokonaislukuhilan solmuissa ja reunat piirretään katkoviivoina, jotka koostuvat akselien suuntaisista segmenteistä, voidaan suorittaa polynomissa . aikaa siirtämällä ongelma minimikustannusvirran löytämisen ongelmaan [8 ] [9] . Jos kuitenkin muutetaan tapaa, jolla tasograafi on upotettu, mutkan minimointiongelmasta tulee NP-täydellinen ja se on ratkaistava menetelmillä, kuten kokonaislukuohjelmointi , mikä ei takaa sekä tarkkaa ratkaisua että nopeaa toimintaa [10] .

Useita mutkia per reuna

Monet graafin piirustustyylit sallivat taivutukset, mutta rajoitetulla tavalla näiden esitysten käyrän monimutkaisuus (kiertymien enimmäismäärä reunaa kohti) on rajoitettu johonkin vakioon. Tämän vakion antamista kasvaa voidaan käyttää parantamaan piirustuksen muita ominaisuuksia, kuten aluetta [1] . Joissakin tapauksissa muotoilu voi olla mahdollista vain, kun hölkkärit on ratkaistu. Esimerkiksi jokaisella graafilla ei ole esitystä, jossa on ortogonaalinen reunaleikkaus ilman mutkia tai käyrän monimutkaisuus kaksi, mutta missä tahansa graafissa on tällainen kuvio käyrän monimutkaisuuden kolmella [11] .

Muistiinpanot

  1. ↑ 1 2 Di Giacomo, Didimo, Liotta, Meijer, 2011 , s. 565–575.
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 15-16.
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 145.
  4. ↑ Osto, 1997 , s. 248–261.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 140.
  6. ↑ 1 2 Eades, Hong, Poon, 2010 , s. 232-243.
  7. ↑ Garg, Tamassia, 2001 , s. 601–625.
  8. ↑ Tamassia, 1987 , s. 421–444.
  9. ↑ Cornelsen, Karrenbauer, 2012 , s. 635–650.
  10. ↑ Mutzel, Weiskircher, 2002 , s. 484–493.
  11. ↑ Didimo, Eades, Liotta, 2009 , s. 206-217.

Kirjallisuus