Iloczyn kartezjański grafów

Iloczyn kartezjański grafów.

W teorii grafów iloczyn kartezjański G □ H wykresów G i H jest takim wykresem, że :

• zbiór wierzchołków G V □ H jest iloczynem kartezjańskim V ( G × ( H ) ; ) I
• dwa wierzchołki ( u , u' ) i ( v , v' ) sąsiadują ze sobą w G □ H wtedy i tylko wtedy, gdy albo
  • u = v i u' sąsiaduje z v' w H , lub
  • u' = v' i u sąsiaduje z v w G .

Iloczyn kartezjański grafów jest czasem nazywany iloczynem pudełkowym grafów [Harary 1969].

Operacja jest asocjacyjna , ponieważ wykresy ( F □ G ) □ H i F □ ( G □ H ) są naturalnie izomorficzne . Operacja jest przemienna jako operacja na klasach izomorfizmu grafów, a silniej grafy G □ H i H □ G są naturalnie izomorficzne , ale nie jest przemienna jako operacja na grafach oznaczonych .

Notacja G × H była często używana dla iloczynów kartezjańskich grafów, ale obecnie jest częściej używana dla innej konstrukcji znanej jako iloczyn tensorowy grafów . Symbol kwadratu ma być intuicyjnym i jednoznacznym oznaczeniem iloczynu kartezjańskiego, ponieważ przedstawia wizualnie cztery krawędzie wynikające z iloczynu kartezjańskiego dwóch krawędzi.

Przykłady

• Iloczyn kartezjański dwóch krawędzi jest cyklem na czterech wierzchołkach: K ₂ □ K ₂ = C ₄ .
• Iloczyn kartezjański K ₂ i wykresu ścieżkowego jest grafem drabinkowym .
• Iloczyn kartezjański dwóch wykresów ścieżkowych jest wykresem siatkowym .
• Iloczyn kartezjański n krawędzi to hipersześcian:

${\ Displaystyle (K_ {2}) ^ {\ kwadrat n} = Q_ {n}.}$

Zatem iloczyn kartezjański dwóch wykresów hipersześcianu to kolejny hipersześcian: Q _ja □ Q _j = Q _{ja + j} .

• Iloczyn kartezjański dwóch wykresów medianowych to kolejny wykres medianowy.
• Grafem wierzchołków i krawędzi n- pryzmatu jest graf iloczynu kartezjańskiego K ₂ □ C _n .
• Graf wieży jest iloczynem kartezjańskim dwóch pełnych grafów.

Nieruchomości

Jeśli spójny graf jest iloczynem kartezjańskim, można go jednoznacznie rozłożyć na czynniki jako iloczyn czynników pierwszych, grafów, których nie można rozłożyć na iloczyny grafów. Jednak Imrich i Klavžar (2000) opisują rozłączony graf, który można wyrazić na dwa różne sposoby jako iloczyn kartezjański grafów pierwszych:

${\ Displaystyle (K_ {1} +K_{2}+K_{2}^{2})\mathbin {\kwadrat} (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2 }+K_{2}^{4})\mathbin {\kwadrat} (K_{1}+K_{2}),}$

gdzie znak plus oznacza sumę rozłączną , a indeksy górne oznaczają potęgowanie na iloczynach kartezjańskich.

Iloczyn kartezjański jest wierzchołkowo przechodni wtedy i tylko wtedy, gdy każdy z jego czynników jest przechodni.

Produkt kartezjański jest dwudzielny wtedy i tylko wtedy, gdy każdy z jego czynników jest. Mówiąc bardziej ogólnie, liczba chromatyczna iloczynu kartezjańskiego spełnia równanie

${\ Displaystyle \ chi (G \ mathbin {\ kwadrat} H) = \ max \ {\ chi (G), \ chi (H) \}.}$

Hipoteza Hedetniemiego stwierdza pokrewną równość dla iloczynu tensorowego grafów . Liczba niezależności iloczynu kartezjańskiego nie jest tak łatwa do obliczenia, ale jak Vizing (1963), spełnia ona nierówności

${\ Displaystyle \ alfa (G) \ alfa (H) + \ min \ {| V (G) | - \ alfa (G), | V (H) | - \ alfa (H) \} \ równoważnik \ alfa ( G\mathbin {\kwadrat} H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

Hipoteza Vizinga mówi, że liczba dominacji iloczynu kartezjańskiego spełnia nierówność

${\ Displaystyle \ gamma (G \ mathbin {\ kwadrat} H) \ geq \ gamma (G) \ gamma (H).}$

Iloczyn kartezjański wykresów odległości jednostkowych to kolejny wykres odległości jednostkowych.

Wykresy produktów kartezjańskich można skutecznie rozpoznawać w czasie liniowym .

Teoria grafów algebraicznych

Teorię grafów algebraicznych można wykorzystać do analizy iloczynu grafu kartezjańskiego. $G_$ wykres ma $\$ i sąsiedztwa $}$${\ Displaystyle \ mathbf {A} _ {1}}$ , a wykres ma ${\ Displaystyle n_$${2}}$ wierzchołki i $}$$Displaystyle n_ {2} \ razy n_$$, wtedy$ macierz sąsiedztwa sąsiedztwa iloczynu kartezjańskiego obu wykresów jest dana przez

${\ Displaystyle \ mathbf {A} _ {1 \ mathbin {\ kwadrat} 2} = \ mathbf {A} _ {1} \ czasami \ mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$ ,

gdzie oznacza $iloczyn$ macierzy Kroneckera $_$ oznacza $_$ _ _ Macierz sąsiedztwa iloczynu wykresu kartezjańskiego jest zatem sumą Kroneckera macierzy sąsiedztwa czynników.

Teoria kategorii

Postrzegając graf jako kategorię , której obiektami są wierzchołki, a morfizmami ścieżki w grafie, iloczyn kartezjański grafów odpowiada zabawnemu iloczynowi tensorowemu kategorii. Iloczyn kartezjański grafów jest jednym z dwóch produktów grafowych, które zamieniają kategorię grafów i homomorfizmów grafów w symetryczną zamkniętą kategorię monoidalną (w przeciwieństwie do czysto symetrycznej monoidalnej), drugim jest iloczynem tensorowym grafów . Wewnętrzny hom $i$${$ \ H $jako$ nienaturalne przekształcenia ” między krawędzie.

Historia

Według Imricha i Klavžara (2000) iloczyny kartezjańskie grafów zostały zdefiniowane w 1912 roku przez Whiteheada i Russella . Później były wielokrotnie odkrywane na nowo, zwłaszcza przez Gerta Sabidussiego ( 1960 ).

Notatki

•   Aurenhammer, F .; Hagauer, J.; Imrich, W. (1992), „Kartezjańska faktoryzacja grafów przy logarytmicznym koszcie na krawędź”, Computational Complexity , 2 (4): 331–349, doi : 10,1007 / BF01200428 , MR 1215316 .
•   Feigenbaum, Joanna ; Hershberger, Jan ; Schäffer, Alejandro A. (1985), „Algorytm czasu wielomianowego do znajdowania czynników pierwszych wykresów iloczynów kartezjańskich”, Discrete Applied Mathematics , 12 (2): 123–138, doi : 10,1016 / 0166-218X (85) 90066 -6 , MR 0808453 .
•   Hahn, Gena; Sabidussi, Gert (1997), Graf symetria: metody i zastosowania algebraiczne , NATO Advanced Science Institutes Series, tom. 497, Springer, s. 116, ISBN 978-0-7923-4668-5 .
•   Horwat, Borys; Pisanski, Tomaž (2010), „Produkty wykresów odległości jednostkowych”, Matematyka dyskretna , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR 2610282 .
•   Imrich, Wilfried ; Klavžar, Sandi (2000), Wykresy produktów: struktura i rozpoznawanie , Wiley, ISBN 0-471-37039-8 .
•   Imrich, Wilfried ; Klavžar, Sandi; Rall, Douglas F. (2008), Wykresy i ich iloczyny kartezjańskie , AK Peters, ISBN 1-56881-429-1 .
•   Imrich, Wilfried ; Peterin, Iztok (2007), „Rozpoznawanie iloczynów kartezjańskich w czasie liniowym”, Matematyka dyskretna , 307 (3–5): 472–483, doi : 10.1016/j.disc.2005.09.038 , MR 2287488 .
•   Kaveh, A.; Rahami, H. (2005), „Ujednolicona metoda rozkładu własnego produktów grafowych”, Communications in Numerical Methods in Engineering with Biomedical Applications , 21 (7): 377–388, doi : 10.1002/cnm.753 , MR 2151527 .
•   Sabidussi, G. (1957), „Wykresy z daną grupą i podanymi właściwościami grafów teoretycznych”, Canadian Journal of Mathematics , 9 : 515–525, doi : 10.4153/CJM-1957-060-7 , MR 0094810 .
•   Sabidussi, G. (1960), "Mnożenie wykresów", Mathematische Zeitschrift , 72 : 446–457, doi : 10.1007/BF01162967 , hdl : 10338.dmlcz/102459 , MR 0209177 .
•   Vizing, VG (1963), „Iloczyn kartezjański grafów”, Vycisl. Sistemy , 9 : 30–43, MR 0209178 .
• Weber, Mark (2013), „Wolne produkty wyższych algebr operowych”, TAC , 28 (2): 24–65 .

Linki zewnętrzne

• Weisstein, Eric W. „Wykres iloczynu kartezjańskiego” . MathWorld .