Operații pe grafice

Operațiile pe grafice formează grafice noi din cele vechi. Operațiunile pot fi împărțite în următoarele categorii principale.

Operații unice (unare)

O singură operație creează un nou grafic dintr-un grafic vechi.

Operații elementare

Uneori, această clasă de operații se numește operații de editare a graficelor. Ei creează un nou grafic din graficul original prin modificări locale simple, cum ar fi adăugarea sau eliminarea unui vârf sau arc, îmbinarea sau împărțirea vârfurilor, micșorarea graficului și așa mai departe.

Operații complexe

Operațiile compuse creează un nou grafic din cel inițial cu modificări complexe, cum ar fi:

• grafic liniare
• Grafic dual
• Complement de grafic
• Conte minor
• Gradul graficului : Al- lea k grad G k al graficului G este un supergraf format prin adăugarea tuturor arcelor dintre toate perechile de vârfuri ale lui G cu distanța de cel mult k . A doua putere a unui grafic se mai numește și pătratul său .
• Conversie Delta-Star
• Contele Mychelski (Mychelskian)

Operații duble (binare)

Operația binară creează un nou grafic din cele două grafice originale G1(V1, E1) și G2(V2, E2) :

• O uniune de graf disjunc, sau pur și simplu o uniune de graf,  este un graf care conține uniunea mulțimilor de vârfuri (disjunse) V1 și V2 a grafurilor și a mulțimilor de arc, adică [1] . Operația este comutativă și asociativă (pentru graficele neetichetate ).
• Legătura a două grafuri este unirea a două grafuri, în care se adună toate arcele care leagă vârfurile ambelor grafuri (adică arcele, ale căror vârfuri sunt preluate din grafuri diferite) [1] . Operația este comutativă (pentru grafice neetichetate).
• Produsul graficelor bazat pe produsul direct al mulțimilor de vârfuri:
  • Produsul direct al graficelor [1] este o operație comutativă și asociativă (pentru graficele neetichetate).
  • Produsul lexicografic al graficelor [1] . Operația nu este nici comutativă, nici asociativă.
  • Produs puternic al graficelor .
  • Produsul tensor al graficelor , uneori numit și produs direct sau produs Kronecker . Operația este comutativă (pentru grafice neetichetate).
  • Produs în zig-zag [2] .

Fie [N] mulțimea numerelor întregi de la 1 la N. Pentru a determina produsul în zig-zag, se folosesc k- grafice regulate , ale căror arce sunt colorate în k culori. Pentru fiecare culoare i și vârf v , fie v [ i ] vecinul vârfului v conectat printr-un arc de culoare i . Fie G1 un graf D1-regular peste [N1] și G2 un graf D2-regular peste [D1]. Atunci produsul în zig-zag al lui H este graficul cu mulțimea de vârfuri [N1] × [D1], în care pentru orice n din [N1], d din [D1] și i, j din [D2], vârful (n , d) este conectat la ( n [ d [ i ]], d [ i ][ j ]). Această definiție este folosită pentru a construi expandoare .

• Alte operațiuni pe grafice numite „produs”:
  • Produsul rădăcină al graficelor . Operația nu este nici comutativă, nici asociativă.
  • Produsul coronal al graficelor G1 și G2 (definit de Frucht și Harari [3] ) este un grafic care este unirea unei copii a graficului G1 și |V1| copii ale graficului G2 (|V1| este numărul de vârfuri ale graficului G1), în care fiecare vârf al copiei lui G1 este conectat la toate vârfurile tuturor copiilor lui G2.
• Crearea de grafice paralel-secvențiale :
  • compoziție paralelă. Operația este comutativă (pentru grafice neetichetate) [4] .
  • compoziție secvențială. Operația este necomutativă [4] .
  • Compoziția surselor (fuziunea surselor). Operație comutativă (pentru grafice neetichetate).
• Contele Hajosh .

Note

1. ↑ 1 2 3 4 F. Harari . Teoria graficelor = Teoria graficelor / Traducere din engleză și prefață de V.P. Kozyrev. - 2. - M. : Editorial URSS, 2003. - 296 p.
2. ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Unde de entropie, produsul grafic în zig-zag și noi expansori de grad constant  // Annals of Mathematics . - 2002. - T. 155 , nr. 1 . - S. 157-187 . - doi : 10.2307/3062153 . — .
3. ↑ Robert Frucht și Frank Harary . „Pe coroanele a două grafice”, Aequationes Math. 4:322-324, 1970.
4. ↑ 1 2 Evstigneev V. A., Kasyanov V. N. Series-parallel poset // Dicționar de grafice în informatică / Editat de prof. Viktor Nikolaevici Kasyanov. - Novosibirsk: SRL „Editura Științifică Siberiană”, 2009. - V. 17. - (Proiectarea și optimizarea programelor). - ISBN 978-591124-036-3 .