Produsul direct al graficelor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 februarie 2021; verificările necesită 2 modificări .

Un produs cartezian sau direct [1] G H al graficelor G și H este un grafic astfel încât

Produsul cartezian poate fi recunoscut eficient în timp liniar [2] . Operația este comutativă ca operație pe clase de izomorfism de graf și, mai strict, graficele G H și H G sunt în mod natural izomorfe , dar operația nu este comutativă ca operație pe grafice etichetate. Operația este și asociativă , deoarece graficele ( F G ) H și F ( G H ) sunt izomorfe în mod natural.

Notația G × H este folosită ocazional și pentru produsul cartezian al graficelor, dar mai des este folosită pentru o altă construcție cunoscută sub numele de produs tensor al graficelor . Simbolul pătrat este mai des folosit și este lipsit de ambiguitate pentru produsul cartezian al graficelor. Afișează vizual cele patru muchii rezultate din produsul cartezian a două muchii [3]

Exemple

Astfel, produsul cartezian al a două grafice hipercube este un alt hipercub — Q i Q j =Q i+j .

Proprietăți

Dacă un grafic conex este un produs cartezian, acesta poate fi descompus unic într-un produs de factori primi, grafice care nu pot fi descompuse într-un produs de grafice [4] [5] . Totuși, Imrich și Klavzhar [6] au descris un grafic deconectat, care poate fi reprezentat în două moduri diferite ca un produs cartezian al graficelor simple:

(K 1 + K 2 + K 2 2 ) (K 1 + K 2 3 )=(K 1 + K 2 2 + K 2 4 ) (K 1 + K 2 ),

unde semnul plus înseamnă o uniune disjunsă iar superscriptul înseamnă un produs cartezian multiplu.

Un produs cartezian este un grafic tranzitiv de vârf dacă și numai dacă fiecare dintre factorii săi este tranzitiv de vârf [7] .

Un produs cartezian este bipartit dacă și numai dacă fiecare dintre factorii săi este bipartit. Mai general, numărul cromatic al unui produs cartezian satisface ecuația

χ(G H)=max {χ(G), χ(H)} [8] .

Conjectura lui Hedetniemi afirmă o egalitate înrudită pentru produsul tensor al graficelor . Numărul de independență al produselor carteziene nu este ușor de calculat, dar așa cum a arătat Vizing [5] , numărul de independență satisface inegalitățile

α( G )α( H ) + min{|V( G )|-α( G ),|V( H )|-α( H )} ≤ α( G H ) ≤ min{α( G ) |V ( H )|, α( H ) |V( G )|}.

Conjectura lui Vizing afirmă că numărul de dominanță al unui produs cartezian satisface inegalitatea

y( GH ) ≥ y( G )y( H ) .

Teoria grafurilor algebrice

Teoria algebrică a graficelor poate fi utilizată pentru a analiza produsul cartezian al graficelor. Dacă un graf are vârfuri și o matrice de adiacență , iar un graf are vârfuri și o matrice de adiacență , atunci matricea de adiacență a produsului cartezian a două grafice este dată de

,

unde denotă produsul Kronecker al matricelor și denotă matricea de identitate [9] .

Istorie

Potrivit lui Imrich și Klavzhar [6] , produsele carteziene ale graficelor au fost definite în 1912 de Whitehead și Russell . Produsul graficelor a fost redescoperit în mod repetat mai târziu, în special de Gert Sabidoussi [4] .

Note

  1. ↑ Vizing a folosit termenul de „produs cartezian”, în articolul „ Produs direct ” același produs este numit direct.
  2. ↑ ( Imrich și Peterin 2007 ). Pentru algoritmi de timp polinomial anteriori, vezi Feigenbaum, Hershberger , Schäffer 1985 și Aurenhammer, Hagauer, Imrich 1992 .
  3. ↑ Hahn, Sabidussi, 1997 .
  4. ↑ 1 2 Sabidussi, 1960 .
  5. ↑ 1 2 Vizing, 1963 .
  6. ↑ 1 2 Imrich, Klavžar, 2000 .
  7. ↑ Imrich, Klavžar, 2000 , p. Teorema 4.19.
  8. ↑ Sabidussi, 1957 .
  9. ↑ Kaveh, Rahami, 2005 .

Literatură

Link -uri