Laske paksuus

Graafiteoriassa graafin G paksuus  on pienin määrä tasomaisia ​​aligraafia , joihin graafin G reunat voidaan jakaa . Eli jos on joukko k tasograafia, joilla on samat kärkijoukot ja joiden yhdistäminen antaa graafin G , niin graafin G paksuus on enintään k [1] [2] [3] [4 ] .

Siten tasograafin paksuus on 1. Kaavioita, joiden paksuus on 2, kutsutaan kaksitasoisiksi graafiksi . Paksuuden käsite sai alkunsa Frank Hararin vuoden 1962 oletuksesta, jonka mukaan mikä tahansa graafi, jossa on 9 kärkeä, joko itse tai sen komplementti , on ei- tasomainen . Tehtävä vastaa sen määrittämistä, onko täydellinen graafi K 9 kaksitasoinen (se ei ole kaksitasoinen, joten olettamus on totta) [5] . Mutzel, Odenthal ja Scharbrodt [6] ovat laatineet kattavan katsauksen graafin paksuuden aiheesta (vuodesta 1998) .

Tietyt kaaviot

Täydellisen graafin , jossa on n kärkeä, paksuus K n , on

lukuun ottamatta tapauksia n = 9, 10 , joiden paksuus on kolme [7] [8] .

Muutamia tapauksia lukuun ottamatta täydellisen kaksiosaisen graafin Ka a,b paksuus on [7] [9]

Aiheeseen liittyvät tehtävät

Mikä tahansa metsä on tasomainen, ja mikä tahansa tasograafi voidaan jakaa kolmeen metsään tai vähemmän. Siten minkään graafin G paksuus ei ole suurempi kuin saman graafin arborecity (minimimäärä metsiä, joihin graafi voidaan hajottaa) eikä pienempi kuin puusto jaettuna kolmella [10] . Kuvaajan G paksuus liittyy toiseen vakioinvarianttiin , degeneraatioon , joka määritellään aligraafin minimiasteen graafin G kaikkien aligraafien maksimiksi. Jos graafin, jossa on n kärkeä, paksuus t , niin sen reunojen lukumäärä ei ylitä t (3 n − 6) , mikä tarkoittaa, että degeneraatio ei ylitä 6 t − 1 . Toisaalta, jos graafin degeneraatio on yhtä suuri kuin D , niin sen puuisuus ja paksuus eivät ylitä D .

Paksuus liittyy läheisesti samanaikaisen pesiytymisen ongelmaan [11] . Jos kahdella tai useammalla tasograafilla on sama pistejoukko, on mahdollista upottaa kaikki nämä graafit tasoon, jossa on reunaesitykset käyrinä, jolloin kaikilla pisteillä on sama paikka kaikissa piirustuksissa. Voi kuitenkin osoittautua, että tällaisten piirustusten rakentaminen on mahdotonta, jos käytetään viivasegmenttejä .

Toinen graafin invariantti, graafin G suoraviivainen paksuus tai geometrinen paksuus , laskee pienimmän määrän tasokaavioita, joihin G voidaan hajottaa sillä rajoituksella, että ne kaikki voidaan piirtää samanaikaisesti janaja käyttämällä. Kirjan paksuus (tai kirjan paksuus) lisää rajoituksen, jonka mukaan kaikkien kärkien on oltava taitteessa (kirjan sidonta). Toisin kuin puuisuus ja rappeutuminen, näiden suureiden välillä ei ole suoraa yhteyttä [12] .

Laskennallinen monimutkaisuus

Tietyn graafin paksuuden laskeminen on NP-kovaa ja sen tarkistaminen, että paksuus on enintään kaksi, on NP-täydellinen [ 13] . Suhde puumaisuuteen mahdollistaa kuitenkin paksuuden approksimoinnin polynomiajassa likimääräisellä kertoimella 3 .

Muistiinpanot

  1. ↑ Tutte, 1963 , s. 567-577.
  2. ↑ Mutzel, Odenthal, Scharbrodt, 1998 , s. 59-73.
  3. ↑ Christian, 2009 .
  4. ↑ Alekseev, Gonchakov, 1976 , s. 212.
  5. ↑ Mäkinen, Poranen, 2012 , s. 76-87.
  6. ↑ Petra Mutzel, Thomas Odenthal ja Mark Scharbrodt, The Thickness of Graphs: A Survey arkistoitu 3. maaliskuuta 2016 Wayback Machinessa
  7. ↑ 1 2 Mutzel, Odenthal, Scharbrodt, 1998 .
  8. ↑ Alekseev, Gonchakov, 1976 , s. 212-230.
  9. ↑ Beineke, Harary, Moon, 1964 , s. 1-5.
  10. ↑ Dean, Hutchinson, Scheinerman, 1991 , s. 147-151.
  11. ↑ Brass et ai., 2007 , s. 117-130.
  12. ↑ Eppstein, 2004 , s. 75-86.
  13. ↑ Mansfield, 1983 , s. 9-23.

Kirjallisuus