Räkna Tjocklek

I grafteorin är tjockleken på en graf G  det minsta antalet plana subgrafer i vilka kanterna på en graf G kan brytas ner . Det vill säga, om det finns en uppsättning k plana grafer med samma uppsättning hörn, vars förening ger grafen G , då är tjockleken på grafen G högst k [1] [2] [3] [4 ] .

En plan graf har alltså tjocklek 1. Grafer med tjocklek 2 kallas biplanära grafer . Begreppet tjocklek har sitt ursprung i Frank Hararis antagande från 1962 att varje graf med 9 hörn, antingen sig själv eller dess komplement , är icke- plan . Problemet är likvärdigt med att avgöra om hela grafen K 9 är biplanär (den är inte biplanär, så gissningen är sann) [5] . En omfattande genomgång av ämnet graftjocklek (från 1998) är av Mutzel, Odenthal och Scharbrodt [6] .

Specifika grafer

Tjockleken på en komplett graf med n hörn, K n , är

förutom fallen n = 9, 10 , för vilka tjockleken är tre [7] [8] .

Med undantag för några få fall är tjockleken på den kompletta tvådelade grafen Ka ,b [7] [9]

Relaterade uppgifter

Vilken skog som helst är plan, och vilken plan graf som helst kan delas upp i tre skogar eller mindre. Sålunda är tjockleken på någon graf G inte större än arborecity av samma graf (det minsta antalet skogar som grafen kan brytas ner i) och inte mindre än arborecity dividerat med tre [10] . Tjockleken på en graf G är relaterad till en annan standardinvariant , degeneration , definierad som det maximala över alla subgrafer i en graf G av subgrafens minimigrad. Om en graf med n hörn har tjockleken t , så överstiger inte antalet kanter t (3 n − 6) , vilket innebär att degenerationen inte överstiger 6 t − 1 . Å andra sidan, om degenerationen av en graf är lika med D , överstiger dess trädighet och tjocklek inte D .

Tjocklek är nära relaterad till problemet med samtidig häckning [11] . Om två eller flera plana grafer har samma uppsättning av hörn, så är det möjligt att bädda in alla dessa grafer i ett plan med kantrepresentationer som kurvor, så att alla hörn kommer att ha samma position i alla ritningar. Det kan dock visa sig att konstruktionen av sådana ritningar är omöjlig om linjesegment används .

En annan grafinvariant, den rätlinjiga tjockleken eller geometriska tjockleken av en graf G , räknar det minsta antalet plana grafer till vilka G kan dekomponeras med begränsningen att de alla kan ritas samtidigt med hjälp av linjesegment. Boktjocklek (eller boktjocklek) lägger till begränsningen att alla hörn måste ligga på ett veck (bokbindning). Men till skillnad från trädighet och degeneration finns det inget direkt samband mellan dessa kvantiteter [12] .

Beräkningskomplexitet

Att beräkna tjockleken på en given graf är NP-hårt , och att kontrollera att tjockleken är högst två är NP-komplett [ 13] . Men förhållandet till träighet tillåter att tjockleken approximeras med en approximationsfaktor på 3 i polynomtid .

Anteckningar

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

Litteratur