Gradul de numărare

Gradul k (scris G k ) al unui graf nedirecționat G este un alt graf care are același set de vârfuri , iar două vârfuri ale acestui graf sunt adiacente dacă distanța dintre aceste vârfuri din graficul original G nu depășește k . Pentru a indica gradul unui grafic, se folosește o terminologie similară puterilor numerelor - G 2 se numește pătratul graficului G , G 3 se numește cubul [1] .

Gradul unui grafic nu trebuie confundat cu înmulțirea unui grafic în sine, care (spre deosebire de gradul unui grafic) are în general mult mai multe vârfuri decât graficul original.

Proprietăți

Dacă diametrul unui grafic este d , atunci gradul lui d este un grafic complet [2] . Dacă o familie de grafuri are o lățime de clică mărginită , atunci același lucru este valabil și pentru puterile d -a ale grafurilor familiei pentru orice d fix [3] .

Plansa de colorat

Colorarea graficelor pătrate poate fi folosită pentru a atribui frecvențe membrilor rețelei fără fir, astfel încât să nu interfereze doi membri între ei și cu orice alt vecin comun [4] , precum și pentru a găsi o reprezentare grafică a graficelor cu rezoluție unghiulară mare [5] ] .

Atât numărul cromatic, cât și degenerarea gradului k al unui graf plan cu gradul maxim de vârf Δ sunt egale cu , unde limita de degenerare arată că se poate folosi algoritmul de colorare greedy pentru a colora graficul cu acel număr de culori [4] . Pentru cazul unui graf pătrat planar, Wegner a presupus în 1977 că numărul cromatic al unui astfel de graf nu depășește , iar în prezent se știe că numărul cromatic nu depășește [6] [7] . Mai general, pentru orice grafic cu degenerare d și grad maxim Δ, degenerarea pătrată a graficului este O ( d Δ), astfel încât multe tipuri de grafice rare , altele decât graficele plane, au, de asemenea, un număr cromatic pătrat proporțional cu Δ.

Deși numărul cromatic al unui pătrat al unui graf neplanar cu gradul maxim Δ poate fi proporțional cu Δ 2 în cel mai rău caz , este mai mic pentru graficele cu circumferință mare și este limitat la O(Δ 2 /log Δ) [8] în acest caz .

Problema determinării numărului minim de culori pentru colorarea unui grafic pătrat este NP-grea chiar și pentru cazul planar [9]

Hamiltonian

Cubul oricărui graf conectat conține în mod necesar un ciclu hamiltonian [10] . Pătratul unui graf conectat nu va conține neapărat un ciclu hamiltonian, iar problema determinării că un astfel de ciclu este conținut într-un pătrat este NP-complet [11] . Cu toate acestea, conform teoremei lui Fleischner , pătratul unui graf legat de vârfuri-2 este întotdeauna hamiltonian [12] .

Complexitate computațională

Gradul k al unui grafic cu n vârfuri și m muchii poate fi obținut în timp O( mn ) prin aplicarea căutării pe lățimea întâi , care se efectuează pe fiecare vârf al graficului pentru a găsi distanța față de toate celelalte vârfuri. Alternativ, dacă A este matricea de adiacență a graficului modificat în așa fel încât să nu existe elemente zero pe diagonala principală, atunci elementele nenule ale matricei A k dau matricea de adiacență de gradul k al graficul [13] , ceea ce presupune că construcția gradului k al graficului poate fi realizată într-un timp egal, până la un factor logaritmic, cu timpul înmulțirii matricei .

Având în vedere un grafic, a determina dacă acesta este un pătrat al altui grafic este o problemă NP-completă [14] . Mai mult, este o problemă NP-complet să se determine dacă un grafic este puterea k a unui alt grafic pentru orice număr dat k  ≥ 2 și, de asemenea, dacă este puterea k a unui grafic bipartit pentru k  > 2 [15] .

Subgrafe generate

Un semipătrat al unui graf bipartit G este un subgraf al graficului G 2 generat de o parte a graficului G . Graficele hărților sunt semipătrate ale graficelor plane [16] , graficele cuburilor înjumătățite sunt semipătrate ale graficelor hipercubice [17] .

Gradele de frunze sunt subgrafe ale gradelor de arbori generate de frunzele de arbori [18] .

Note

  1. ↑ Bondy, Murty, 2008 , p. 82.
  2. ^ Weisstein , Eric W. Graph Power  pe site- ul Wolfram MathWorld .
  3. ↑ Todinca, 2003 , p. 370–382.
  4. ↑ 1 2 Agnarsson, Halldorsson, 2000 , p. 654–662.
  5. ↑ Formann, Hagerup, Haralambides et al., 1993 , p. 1035–1052.
  6. ↑ F. & H. Kramer, 2008 , p. 422–426.
  7. ↑ Molloy, Salavatipour, 2005 , p. 189–213.
  8. ↑ Alon, Mohar, 2002 , p. 1–10.
  9. ↑ Agnarsson și Halldórsson ( Agnarsson, Halldórsson 2000 ) listează în publicația lor dovezile de hârtie ale durității NP pentru cazul graficelor generale (lucrări de McCormick (1983) și lucrări de Lin și Skiena (Lin, Skiena, 1995)) și pentru grafice plane (articole de Ramanathan și Lloyd (Ramanathan, Lloyd, 1992-1993)).
  10. ↑ Bondy, Murty, 2008 , p. 105.
  11. ↑ Underground, 1978 , p. 323.
  12. ↑ Diesel, 2012 .
  13. ↑ Hammack, Imrich, Klavžar, 2011 .
  14. ↑ Motwani, Sudan, 1994 , p. 81-88.
  15. ↑ Le, Nguyen, 2010 , p. 238–249.
  16. ↑ Chen, Grigni, Papadimitriou, 2002 , p. 127–138.
  17. ↑ Shpektorov, 1993 .
  18. ↑ Nishimura, Ragde, Thilikos, 2002 , p. 69–108.

Literatură