Cub parțial

În teoria grafurilor, un cub parțial este un subgraf al unui hipercub care păstrează distanțele (în termeni de grafice) - distanța dintre oricare două vârfuri ale subgrafului este aceeași ca în graficul original [1] . În mod echivalent, un cub parțial este un grafic ale cărui vârfuri pot fi etichetate cu șiruri de biți de aceeași lungime, astfel încât distanța dintre două vârfuri din grafic să fie egală cu distanța Hamming dintre cele două etichete. Acest marcaj se numește marcajul Hamming și reprezintă o încorporare izometrică a unui cub parțial într-un hipercub.


Istorie

V. Firsov [2] a fost primul care a studiat înglobarea izometrică a graficelor în hipercuburi. Graficele care permit astfel de înglobări au fost descrise de D. Djokovic [3] și P. Winkler [4] și au fost numite ulterior „cuburi parțiale”. O linie independentă de cercetare asupra acelorași structuri în terminologia familiilor de mulțimi , mai degrabă decât etichetarea hipercuburilor, a fost dezvoltată, printre alții, de către V. Kuzmin și S. Ovchinnikov [5] , precum și Falmagnet și Doinon [6] [7] .

Exemple

Orice copac este un cub parțial. Să presupunem că un arbore T are m muchii și numerele acestor muchii (în ordine arbitrară) de la 0 la m  - 1. Alegem un vârf rădăcină arbitrar r pentru arbore și atribuim fiecărui vârf v o etichetă (șir de biți) m biți lung, care conține 1 în poziția i dacă muchia i se află pe calea de la r la v în arborele T . De exemplu, vârful r însuși va avea o etichetă cu zerouri, iar toate vârfurile adiacente acestuia vor avea un 1 în aceeași poziție și așa mai departe. Apoi, distanța Hamming dintre oricare două etichete va fi egală cu distanța dintre vârfurile corespunzătoare ale arborelui, astfel încât această etichetare arată că arborele T este un cub parțial.

Orice grafic hipercub este el însuși un cub parțial, care poate fi marcat cu diferite șiruri de biți cu o lungime egală cu dimensiunea hipercubului.

Exemple mai complexe:

Raportul Djokovic–Winkler

Multe teoreme despre cuburile parțiale se bazează direct sau indirect pe o relație binară definită pe muchiile graficului. Această relație, descrisă pentru prima dată de Djokovic [3] , este notă cu . Winkler a dat o definiție echivalentă a relației în termeni de distanță [4] . Două muchii și sunt în relație (scris ) dacă . Această relație este reflexivă și simetrică , dar, în general, nu tranzitivă .

Winkler a arătat că un graf conex este un cub parțial dacă și numai dacă este bipartit și relația este tranzitivă [12] [13] . În acest caz, relația formează o relație de echivalență și fiecare clasă de echivalență separă două subgrafe conectate ale graficului unul de celălalt. O etichetă Hamming poate fi obținută prin alocarea unui bit în fiecare etichetă pentru fiecare clasă de echivalență a relației Djokovic-Winkler. Într-unul dintre cele două subgrafe conectate separate printr-o relație de echivalență a muchiei, etichetele au 0 în poziția corespunzătoare, iar în celălalt subgraf conectat, toate etichetele din aceeași poziție au 1.

Recunoaștere

Cuburile parțiale pot fi recunoscute și marcajul Hamming pentru ele este construit în timp , unde este numărul de vârfuri ale graficului [14] . Având în vedere un cub parțial, se pot construi în mod direct clase de echivalență Djokovic-Winkler utilizând căutarea pe lățimea întâi de la fiecare vârf în timpul total . Algoritmul de recunoaștere accelerează căutarea în timp prin utilizarea paralelismului la nivel de biți pentru a efectua mai multe căutări pe lățimea întâi într-o singură trecere a graficului, apoi folosind un algoritm separat pentru a verifica dacă rezultatul este un aspect de cub parțial valid.

Dimensiune

Dimensiunea izometrică a unui cub parțial este dimensiunea minimă a unui hipercub în care un grafic poate fi încorporat izometric și este egală cu numărul de clase de echivalență ale relației Djokovic-Winkler. De exemplu, dimensiunea izometrică a unui arbore cu vârfuri este egală cu numărul muchiilor acestuia, . Încorporarea unui cub parțial într-un hipercub de această dimensiune este unică până la simetriile hipercubului [15] [16] .

Orice hipercub și, prin urmare, orice cub parțial, poate fi încorporat izometric într- o rețea întreagă , iar dimensiunea rețelei pentru un cub parțial este dimensiunea minimă a unei rețele întregi în care poate fi încorporat un cub parțial. Dimensiunea rețelei se poate dovedi a fi semnificativ mai mică decât dimensiunea izometrică. De exemplu, pentru un copac, este egal cu jumătate din numărul de frunze din copac (rotunjit la cel mai apropiat număr întreg). Dimensiunea unei rețele pentru orice graf și încorporarea într-o rețea de dimensiune minimă pot fi găsite în timp polinomial printr-un algoritm bazat pe găsirea celei mai mari potriviri într-un graf auxiliar [17] .

Sunt definite alte tipuri de dimensiuni parțiale de cub, pe baza unor structuri mai specifice [18] [19] .

Aplicații în teoria grafurilor chimice

Înglobările izometrice ale graficelor într-un hipercub au aplicații importante în teoria graficelor chimice . Un grafic benzoid este un grafic format din vârfuri și muchii situate pe un ciclu și în interiorul unui ciclu într-o rețea hexagonală . Astfel de grafice sunt graficele moleculare ale hidrocarburilor benzoide , o clasă mare de molecule organice. Fiecare astfel de grafic este un cub parțial. Etichetarea Hamming a unui astfel de grafic poate fi utilizată pentru a calcula indicele Wiener al moleculei corespunzătoare, care poate fi folosit pentru a prezice unele proprietăți chimice [20] . O altă structură moleculară formată din carbon, structura diamantului , corespunde și cuburilor parțiale [18] .

Note

  1. ↑ Ovchinnikov, 2011 , p. 127, Definiția 5.1.
  2. ↑ Firsov, 1965 .
  3. ↑ 1 2 Djokovic, 1973 .
  4. ↑ 12 Winkler , 1984 .
  5. ↑ Kuzmin, Ovchinnikov, 1975 .
  6. ↑ Falmagne, Doignon, 1997 .
  7. ↑ Ovchinnikov, 2011 , p. 174.
  8. ↑ Ovchinnikov, 2011 , p. 163–165, Secțiunea 5.11, „Grafe mediane”.
  9. ↑ Ovchinnikov, 2011 , p. 207–235, capitolul 7, „Aranjamente hiperplane”.
  10. ↑ Eppstein, 2006 .
  11. ↑ Ovchinnikov, 2011 , p. 144–145, Secțiunea 5.7, „Produse carteziane ale cuburilor parțiale”.
  12. ↑ Winkler, 1984 , p. Teorema 4.
  13. ↑ Ovchinnikov, 2011 , p. 29, 139, Definiția 2.13, Teorema 5.19.
  14. ↑ Eppstein, 2008 .
  15. ↑ Ovchinnikov, 2011 , p. 142–144, Secțiunea 5.6, „Dimensiunea izometrică”.
  16. ↑ Ovchinnikov, 2011 , p. 157–162, Secțiunea 5.10, „Unicitatea înglobărilor izometrice”.
  17. ↑ Hadlock, Hoffman, 1978 ; Eppstein, 2005 ; Ovchinnikov, 2011 , capitolul 6, „Înglobări de zăbrele”, pp. 183–205.
  18. ↑ 12 Eppstein , 2009 .
  19. ↑ Cabello, Eppstein, Klavžar, 2011 .
  20. ↑ Klavžar, Gutman, Mohar, 1995 , Propozițiile 2.1 și 3.1; Imrich, Klavžar, 2000 , p. 60; Ovchinnikov, 2011 , Secțiunea 5.12, „Lungimea medie și indicele Wiener”, pp. 165–168.

Literatură