Декартів добуток або прямий добуток G H графів G і H — це граф, такий, що
- множина вершин графу G H — це декартів добуток V(G) × V(H)
- будь-які дві вершини (u, u') і (v, v') суміжні в G H тоді і тільки тоді, коли
- або u=v і u' суміжна v' в H
- або u' =v' і u суміжна v в G.
Декартів добуток можна розпізнати ефективно за лінійний час. Операція є комутативною як операція на класах ізоморфізмів графів, і строгіше, графи G H і H G природно ізоморфні, але операція не є комутативною як операція на розмічених графах. Операція є також асоціативною, оскільки графи (F G) H і F (G H) природно ізоморфні.
Позначення G × H часом використовується і для декартового добутку графів, але частіше воно використовується для іншої конструкції, відомої як тензорний добуток графів. Символ квадратика частіше використовується і є недвозначним для декартового добутку графів. Він показує візуально чотири ребра, що виходять внаслідок декартового добутку двох ребер.
Приклади
- Декартів добуток двох ребер є циклом з чотирма вершинами: K2 K2=C4.
- Декартів добуток K2 і шляху є драбиною.
- Декартів добуток двох шляхів є решіткою.
- Декартів добуток n ребер є гіперкубом:
- Таким чином, декартів добуток двох графів гіперкубів є іншим гіперкубом — Qi Qj=Qi+j.
- Декартів добуток двох є іншим медіанного графом.
- Граф вершин і ребер n-кутної призми є декартовим добутком K2 Cn.
- Туровий граф є декартовим добутком двох повних графів.
Властивості
Якщо зв'язний граф є декартовим добутком, його можна розкласти єдиним способом на добуток простих множників, графів, які не можна розкласти на добуток графів. Однак, Імріх і Клавжар описали незв'язний граф, який можна подати двома різними способами як декартовий добуток простих графів:
- (K1 + K2 + K22) (K1 + K23) = (K1 + K22 + K24) (K1 + K2), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.
Декартів добуток є вершинно-транзитивним графом тоді і тільки тоді, коли кожен з його множників є вершинно-транзитивним.
Декартів добуток є двочастковим тоді і тільки тоді, коли кожен з його множників є двочастковим. Загальніше, хроматичне число декартового добутку задовольняє рівнянню
- χ(G H)=max {χ(G), χ(H)}.
[ru] стверджує пов'язану рівність для тензорного добутку графів. Число незалежності декартових добутків непросто обчислити, але, як показав Візінг, число незалежності задовольняє нерівностям
- α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.
стверджує, що число домінування декартового добутку задовольняє нерівності
- γ(G H) ≥ γ(G)γ(H).
Алгебрична теорія графів
Алгебричну теорію графів можна використовувати для аналізу декартового добутку графів. Якщо граф має вершин і матрицю суміжності , а граф має вершин і матрицю суміжності , то матриця суміжності декартового добутку двох графів задається формулою
- ,
де означає добуток Кронекера матриць, а означає одиничну матрицю.
Історія
За Імріхом і Клавжару декартові добутки графів визначили 1912 року Вайтгед і Расселл. Добуток графів неодноразово перевідкривали пізніше, зокрема, Герт Сабідуссі.
Примітки
- Візінг використав термін «декартів добуток».
- (Imrich, Peterin, 2007). Для раніших алгоритмів поліноміального часу див. статтю Фейгенбаума, Гершберґерґа і Шеффера (Feigenbaum, Hershberger, Schäffer, 1985), а також статтю Авренгаммера, Гаґаувера і Імріха (Aurenhammer, Hagauer, Imrich, 1992).
- Hahn, Sabidussi, 1997.
- Sabidussi, 1960.
- Визинг, 1963.
- Imrich, Klavžar, 2000.
- Imrich, Klavžar, 2000, с. Theorem 4.19.
- Sabidussi, 1957.
- Kaveh, Rahami, 2005.
Література
- F. Aurenhammer, J. Hagauer, W. Imrich. Cartesian graph factorization at logarithmic cost per edge // Computational Complexity. — 1992. — Т. 2, вип. 4 (18 червня). — С. 331—349. — DOI: .
- Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer. A polynomial time algorithm for finding the prime factors of Cartesian-product graphs // . — 1985. — Т. 12, вип. 2 (18 червня). — С. 123—138. — DOI: .
- Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — (NATO Advanced Science Institutes Series) — . з джерела 17 листопада 2021
- Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — .
- Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Products. — A. K. Peters, 2008. — .
- Wilfried Imrich, Iztok Peterin. Recognizing Cartesian products in linear time // . — 2007. — Т. 307, вип. 3—5 (18 червня). — С. 472—483. — DOI: .
- A. Kaveh, H. Rahami. A unified method for eigendecomposition of graph products // Communications in Numerical Methods in Engineering with Biomedical Applications. — 2005. — Т. 21, вип. 7 (18 червня). — С. 377—388. — DOI: .
- G. Sabidussi. Graphs with given group and given graph-theoretical properties // . — 1957. — Т. 9 (18 червня). — С. 515—525. — DOI: .
- G. Sabidussi. Graph multiplication // . — 1960. — Т. 72 (18 червня). — С. 446—457. — DOI: .
- В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9 (18 червня). — С. 30—43.
Посилання
- Weisstein, Eric W. Декартів добуток графів(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Dekartiv dobutok abo pryamij dobutokG displaystyle square H grafiv G i H ce graf takij shomnozhina vershin grafu G displaystyle square H ce dekartiv dobutok V G V H bud yaki dvi vershini u u i v v sumizhni v G displaystyle square H todi i tilki todi koli abo u v i u sumizhna v v H abo u v i u sumizhna v v G Dekartiv dobutok grafiv Dekartiv dobutok mozhna rozpiznati efektivno za linijnij chas Operaciya ye komutativnoyu yak operaciya na klasah izomorfizmiv grafiv i strogishe grafi G displaystyle square H i H displaystyle square G prirodno izomorfni ale operaciya ne ye komutativnoyu yak operaciya na rozmichenih grafah Operaciya ye takozh asociativnoyu oskilki grafi F displaystyle square G displaystyle square H i F displaystyle square G displaystyle square H prirodno izomorfni Poznachennya G H chasom vikoristovuyetsya i dlya dekartovogo dobutku grafiv ale chastishe vono vikoristovuyetsya dlya inshoyi konstrukciyi vidomoyi yak tenzornij dobutok grafiv Simvol kvadratika chastishe vikoristovuyetsya i ye nedvoznachnim dlya dekartovogo dobutku grafiv Vin pokazuye vizualno chotiri rebra sho vihodyat vnaslidok dekartovogo dobutku dvoh reber PrikladiDekartiv dobutok dvoh reber ye ciklom z chotirma vershinami K2 displaystyle square K2 C4 Dekartiv dobutok K2 i shlyahu ye drabinoyu Dekartiv dobutok dvoh shlyahiv ye reshitkoyu Dekartiv dobutok n reber ye giperkubom K 2 n Q n displaystyle K 2 square n Q n dd Takim chinom dekartiv dobutok dvoh grafiv giperkubiv ye inshim giperkubom Qi displaystyle square Qj Qi j Dekartiv dobutok dvoh ye inshim mediannogo grafom Graf vershin i reber n kutnoyi prizmi ye dekartovim dobutkom K2 displaystyle square Cn Turovij graf ye dekartovim dobutkom dvoh povnih grafiv VlastivostiYaksho zv yaznij graf ye dekartovim dobutkom jogo mozhna rozklasti yedinim sposobom na dobutok prostih mnozhnikiv grafiv yaki ne mozhna rozklasti na dobutok grafiv Odnak Imrih i Klavzhar opisali nezv yaznij graf yakij mozhna podati dvoma riznimi sposobami yak dekartovij dobutok prostih grafiv K1 K2 K22 displaystyle square K1 K23 K1 K22 K24 displaystyle square K1 K2 de znak plyus oznachaye nezv yazne ob yednannya a verhnij indeks oznachaye kratnij dekartiv dobutok Dekartiv dobutok ye vershinno tranzitivnim grafom todi i tilki todi koli kozhen z jogo mnozhnikiv ye vershinno tranzitivnim Dekartiv dobutok ye dvochastkovim todi i tilki todi koli kozhen z jogo mnozhnikiv ye dvochastkovim Zagalnishe hromatichne chislo dekartovogo dobutku zadovolnyaye rivnyannyu x G displaystyle square H max x G x H ru stverdzhuye pov yazanu rivnist dlya tenzornogo dobutku grafiv Chislo nezalezhnosti dekartovih dobutkiv neprosto obchisliti ale yak pokazav Vizing chislo nezalezhnosti zadovolnyaye nerivnostyam a G a H min V G a G V H a H a G displaystyle square H min a G V H a H V G stverdzhuye sho chislo dominuvannya dekartovogo dobutku zadovolnyaye nerivnosti g G displaystyle square H g G g H Algebrichna teoriya grafivAlgebrichnu teoriyu grafiv mozhna vikoristovuvati dlya analizu dekartovogo dobutku grafiv Yaksho graf G 1 displaystyle G 1 maye n 1 displaystyle n 1 vershin i n 1 n 1 displaystyle n 1 times n 1 matricyu sumizhnosti A 1 displaystyle mathbf A 1 a graf G 2 displaystyle G 2 maye n 2 displaystyle n 2 vershin i n 2 n 2 displaystyle n 2 times n 2 matricyu sumizhnosti A 2 displaystyle mathbf A 2 to matricya sumizhnosti dekartovogo dobutku dvoh grafiv zadayetsya formuloyu A 1 2 A 1 E n 2 E n 1 A 2 displaystyle mathbf A 1 square 2 mathbf A 1 otimes mathbf E n 2 mathbf E n 1 otimes mathbf A 2 de displaystyle otimes oznachaye dobutok Kronekera matric a E n displaystyle mathbf E n oznachaye n n displaystyle n times n odinichnu matricyu IstoriyaZa Imrihom i Klavzharu dekartovi dobutki grafiv viznachili 1912 roku Vajtged i Rassell Dobutok grafiv neodnorazovo perevidkrivali piznishe zokrema Gert Sabidussi PrimitkiVizing vikoristav termin dekartiv dobutok Imrich Peterin 2007 Dlya ranishih algoritmiv polinomialnogo chasu div stattyu Fejgenbauma Gershbergerga i Sheffera Feigenbaum Hershberger Schaffer 1985 a takozh stattyu Avrengammera Gagauvera i Imriha Aurenhammer Hagauer Imrich 1992 Hahn Sabidussi 1997 Sabidussi 1960 Vizing 1963 Imrich Klavzar 2000 Imrich Klavzar 2000 s Theorem 4 19 Sabidussi 1957 Kaveh Rahami 2005 LiteraturaF Aurenhammer J Hagauer W Imrich Cartesian graph factorization at logarithmic cost per edge Computational Complexity 1992 T 2 vip 4 18 chervnya S 331 349 DOI 10 1007 BF01200428 Joan Feigenbaum John Hershberger Alejandro A Schaffer A polynomial time algorithm for finding the prime factors of Cartesian product graphs 1985 T 12 vip 2 18 chervnya S 123 138 DOI 10 1016 0166 218X 85 90066 6 Gena Hahn Gert Sabidussi Graph symmetry algebraic methods and applications Springer 1997 T 497 S 116 NATO Advanced Science Institutes Series ISBN 978 0 7923 4668 5 z dzherela 17 listopada 2021 Wilfried Imrich Sandi Klavzar Product Graphs Structure and Recognition Wiley 2000 ISBN 0 471 37039 8 Wilfried Imrich Sandi Klavzar Douglas F Rall Graphs and their Cartesian Products A K Peters 2008 ISBN 1 56881 429 1 Wilfried Imrich Iztok Peterin Recognizing Cartesian products in linear time 2007 T 307 vip 3 5 18 chervnya S 472 483 DOI 10 1016 j disc 2005 09 038 A Kaveh H Rahami A unified method for eigendecomposition of graph products Communications in Numerical Methods in Engineering with Biomedical Applications 2005 T 21 vip 7 18 chervnya S 377 388 DOI 10 1002 cnm 753 G Sabidussi Graphs with given group and given graph theoretical properties 1957 T 9 18 chervnya S 515 525 DOI 10 4153 CJM 1957 060 7 G Sabidussi Graph multiplication 1960 T 72 18 chervnya S 446 457 DOI 10 1007 BF01162967 V G Vizing Dekartovo proizvedenie grafov Vychislitelnye sistemy 1963 T 9 18 chervnya S 30 43 PosilannyaWeisstein Eric W Dekartiv dobutok grafiv angl na sajti Wolfram MathWorld