Număr Grosimea

În teoria grafurilor, grosimea unui graf G  este cel mai mic număr de subgrafe plane în care muchiile unui graf G pot fi descompuse . Adică, dacă există o mulțime de k grafice plane având același set de vârfuri, a căror unire dă graficul G , atunci grosimea graficului G este de cel mult k [1] [2] [3] [4 ] .

Astfel, un grafic plan are grosimea 1. Graficele cu grosimea 2 se numesc grafice biplanare . Conceptul de grosime își are originea în conjectura lui Frank Harari din 1962 că orice graf cu 9 vârfuri, fie el însuși, fie complementul său , este neplanar . Problema este echivalentă cu determinarea dacă graficul complet K 9 este biplanar (nu este biplanar, deci conjectura este adevărată) [5] . O revizuire cuprinzătoare pe tema grosimii graficului (din 1998) este făcută de Mutzel, Odenthal și Scharbrodt [6] .

Grafice specifice

Grosimea unui graf complet cu n vârfuri, K n , este

cu excepția cazurilor n = 9, 10 , pentru care grosimea este de trei [7] [8] .

Cu excepția câtorva cazuri, grosimea graficului bipartit complet K a,b este [7] [9]

Sarcini conexe

Orice pădure este plană și orice grafic planar poate fi descompus în trei păduri sau mai puțin. Astfel, grosimea oricărui grafic G nu este mai mare decât arborecitatea aceluiași grafic (numărul minim de păduri în care poate fi descompus graficul) și nu mai mică decât arborecitatea împărțită la trei [10] . Grosimea unui grafic G este legată de un alt invariant standard , degenerarea , definită ca maximul peste toate subgrafele unui grafic G al gradului minim al subgrafului. Dacă un graf cu n vârfuri are grosimea t , atunci numărul muchiilor sale nu depășește t (3 n − 6) , ceea ce presupune că degenerarea nu depășește 6 t − 1 . Pe de altă parte, dacă degenerarea unui grafic este egală cu D , atunci arborele și grosimea acestuia nu depășesc D .

Grosimea este strâns legată de problema cuibăririi simultane [11] . Dacă două sau mai multe grafice plane au același set de vârfuri, atunci este posibil să se încorporeze toate aceste grafice într-un plan cu reprezentări de muchii ca curbe, astfel încât toate vârfurile să aibă aceeași poziție în toate desenele. Cu toate acestea, se poate dovedi că construirea unor astfel de desene este imposibilă dacă sunt utilizate segmente de linie .

Un alt invariant de grafic, grosimea rectilinie sau grosimea geometrică a unui grafic G , numără cel mai mic număr de grafice plane în care G poate fi descompus cu constrângerea că toate pot fi desenate simultan folosind segmente de linie. Grosimea cărții (sau grosimea cărții) adaugă constrângerea că toate vârfurile trebuie să se afle pe un pliu (legare cărți). Totuși, spre deosebire de arbore și degenerescență, nu există o relație directă între aceste cantități [12] .

Complexitate computațională

Calcularea grosimii unui grafic dat este NP-hard , iar verificarea ca grosimea este de cel mult două este NP-complet [ 13] . Totuși, relația cu lemnositatea permite aproximarea grosimii cu un factor de aproximare de 3 în timp polinomial .

Note

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

Literatură