حاصل الضرب الديكارتي للرسوم البيانية

في نظرية المخططات ، يكون حاصل الضرب الديكارتي G □ H للمخططين G و H مخططًا بحيث:

• مجموعة رؤوس G □ H هي حاصل الضرب الديكارتي V ( G ) × V ( H ) ؛ و
• يكون الرأسان ( u , v ) و ( u' , v' ) متجاورين في G □ H إذا وفقط إذا كان أحدهما
  • u = u' و v مجاور لـ v' في H ، أو
  • v = v ' و u مجاور لـ u' في G.

يُطلق على حاصل الضرب الديكارتي للرسوم البيانية أحيانًا اسم حاصل الضرب الصندوقي للرسوم البيانية. ^{[ 1 ]}

العملية تجميعية ، حيث أن الرسمين البيانيين ( F □ G ) □ H و F □ ( G □ H ) متماثلان طبيعياً . وهي عملية تبديلية كعملية على فئات التماثل للرسوم البيانية، وبشكل أقوى، الرسمين البيانيين G □ H و H □ G متماثلان طبيعياً ، لكنها ليست عملية تبديلية كعملية على الرسوم البيانية ذات الرؤوس المُعَلَّمة .

كثيراً ما استُخدم الرمز G × H للدلالة على الضرب الديكارتي للرسوم البيانية، ولكنه يُستخدم الآن بشكل أكثر شيوعاً لنوع آخر من العمليات يُعرف باسم الضرب الموتري للرسوم البيانية . ويهدف رمز المربع إلى أن يكون رمزاً بديهياً لا لبس فيه للضرب الديكارتي، لأنه يُظهر بصرياً الحواف الأربعة الناتجة عن الضرب الديكارتي لحافتين. ^{[ 2 ]}

• الضرب الديكارتي لحافتين هو دورة على أربعة رؤوس: K ₂ □ K ₂ = C ₄ .
• حاصل الضرب الديكارتي لـ K ₂ ومخطط المسار هو مخطط سلمي .
• حاصل الضرب الديكارتي لمخططين مساريين هو مخطط شبكي .
• حاصل الضرب الديكارتي لـ n حافة هو مكعب فائق:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

وبالتالي، فإن حاصل الضرب الديكارتي لرسمين بيانيين مكعبين فائقين هو مكعب فائق آخر: Q _i □ Q _j = Q _i+j .

• حاصل الضرب الديكارتي لرسمين بيانيين وسيطيين هو رسم بياني وسيطي آخر.
• الرسم البياني للرؤوس والحواف لمنشور ذي n عنصر هو الرسم البياني للضرب الديكارتي K ₂ □ C _n .
• الرسم البياني للرخ هو حاصل الضرب الديكارتي لرسمين بيانيين كاملين.

إذا كان الرسم البياني المتصل عبارة عن حاصل ضرب ديكارتي، فإنه يمكن تحليله بشكل فريد كحاصل ضرب عوامل أولية، وهي رسوم بيانية لا يمكن تحليلها بدورها كحاصل ضرب رسوم بيانية أخرى. ^{[ 3 ]} ومع ذلك، يصف إمريش وكلافزار (2000) رسمًا بيانيًا غير متصل يمكن التعبير عنه بطريقتين مختلفتين كحاصل ضرب ديكارتي لرسوم بيانية أولية:

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

حيث تشير علامة الجمع إلى الاتحاد المنفصل ، وتشير الأرقام المرتفعة إلى الأس على حاصل الضرب الديكارتي. ويرتبط هذا بالهوية التي

${\displaystyle {\begin{aligned}(1+x+x^{2})(1+x^{3})&=(1+x^{2}+x^{4})(1+x)\\&=1+x+x^{2}+x^{3}+x^{4}+x^{5}\\&=(1+x)(1+x+x^{2})(1-x+x^{2})\end{aligned}}}$

كلا العاملين${\displaystyle 1+x^{3}}$و${\displaystyle 1+x^{2}+x^{4}}$ليست كثيرات حدود غير قابلة للاختزال ، لكن عواملها تتضمن معاملات سالبة، وبالتالي لا يمكن تحليل الرسوم البيانية المقابلة لها. وبهذا المعنى، فإن فشل التحليل الفريد على الرسوم البيانية (التي قد تكون منفصلة) يُشبه القول بأن كثيرات الحدود ذات المعاملات الصحيحة غير السالبة هي شبه حلقة لا تتمتع بخاصية التحليل الفريد .

يكون حاصل الضرب الديكارتي متعدياً على الرؤوس إذا وفقط إذا كان كل عامل من عوامله متعدياً على الرؤوس. ^{[ 4 ]}

يكون حاصل الضرب الديكارتي ثنائي الأجزاء إذا وفقط إذا كان كل عامل من عوامله كذلك. وبشكل أعم، فإن العدد اللوني لحاصل الضرب الديكارتي يحقق المعادلة التالية:

${\displaystyle \chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.}$^{[ 5 ]}

تنصّ حدسية هيديتنييمي على مساواة ذات صلة بالنسبة لحاصل الضرب الموتري للرسوم البيانية . لا يُمكن حساب عدد الاستقلال لحاصل الضرب الديكارتي بسهولة، ولكن كما بيّن فيزينغ (1963)، فإنه يُحقق المتباينات.

${\displaystyle \alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

تنص فرضية فيزينغ على أن عدد الهيمنة في حاصل الضرب الديكارتي يحقق المتباينة

${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).}$

يُعدّ حاصل الضرب الديكارتي للرسوم البيانية ذات المسافة الواحدة رسمًا بيانيًا آخر ذا مسافة واحدة. ^{[ 6 ]}

يمكن التعرف على الرسوم البيانية للضرب الديكارتي بكفاءة، في وقت خطي . ^{[ 7 ]}

عدد الحواف | E ( G □ H )| يساوي | V ( G )|| E ( H )| + | V ( H )|| E ( G )| .

يمكن استخدام نظرية الرسم البياني الجبرية لتحليل حاصل ضرب الرسم البياني الديكارتي. إذا كان الرسم البياني${\displaystyle G_{1}}$لديه${\displaystyle n_{1}}$الرؤوس و${\displaystyle n_{1}\times n_{1}}$مصفوفة التجاور${\displaystyle \mathbf {A} _{1}}$والرسم البياني${\displaystyle G_{2}}$لديه${\displaystyle n_{2}}$الرؤوس و${\displaystyle n_{2}\times n_{2}}$مصفوفة التجاور${\displaystyle \mathbf {A} _{2}}$إذن، تُعطى مصفوفة التجاور للجداء الديكارتي لكلا الرسمين البيانيين بالصيغة التالية:

${\displaystyle \mathbf {A} _{1\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$،

أين${\displaystyle \otimes }$يرمز إلى حاصل ضرب كرونكر للمصفوفات و${\displaystyle \mathbf {I} _{n}}$يشير إلى${\displaystyle n\times n}$مصفوفة الوحدة . ^{[ 8 ]} وبالتالي فإن مصفوفة التجاور لمنتج الرسم البياني الديكارتي هي مجموع كرونكر لمصفوفات التجاور للعوامل.

إذا نظرنا إلى الرسم البياني كفئة تمثل رؤوسها عناصرها، وتمثل مساراتها مساراتها، فإن الضرب الديكارتي للرسوم البيانية يُقابل الضرب الموتري للفئات. يُعد الضرب الديكارتي للرسوم البيانية أحد ضربين للرسوم البيانية يحولان فئة الرسوم البيانية وتشاكلاتها إلى فئة أحادية مغلقة متناظرة (بدلاً من كونها أحادية متناظرة فقط)، والآخر هو الضرب الموتري للرسوم البيانية . ^{[ 9 ]} التماثل الداخلي${\displaystyle [G,H]}$بالنسبة للضرب الديكارتي للرسوم البيانية، توجد تشاكلات رسوم بيانية من${\displaystyle G}$ل${\displaystyle H}$^{[ 9 ]} كرؤوس و" تحويلات غير طبيعية " بينها كحواف.

وفقًا لإمريش وكلافزار (2000) ، تم تعريف الضرب الديكارتي للرسوم البيانية في عام 1912 بواسطة وايتهيد وراسل . وقد أعيد اكتشافها مرارًا وتكرارًا لاحقًا، ولا سيما بواسطة جيرت سابيدوسي ( 1960 ) . 

• أورينهامر، ف .؛ هاغاور، ج.؛ إمريش، و. (1992)، "تحليل الرسم البياني الديكارتي بتكلفة لوغاريتمية لكل حافة"، التعقيد الحسابي ، 2 (4): 331-349 ، doi : 10.1007/BF01200428 ، MR 1215316 .
• فيجنباوم، جوان ؛ هيرشبيرجر، جون ؛ شافر، أليخاندرو أ. (1985)، "خوارزمية زمنية متعددة الحدود لإيجاد العوامل الأولية لرسوم بيانية حاصل الضرب الديكارتي"، الرياضيات التطبيقية المنفصلة ، ​​12 (2): 123-138 ، doi : 10.1016/0166-218X(85)90066-6 ، MR 0808453 .
• هان، جينا؛ تارديف، كلود (1997)، "تشاكلات الرسوم البيانية: البنية والتناظر" ، في هان، جينا؛ سابيدوسي، جيرت (محرران)، تناظر الرسوم البيانية: الأساليب الجبرية والتطبيقات ، سلسلة معاهد العلوم المتقدمة التابعة لحلف الناتو ج: العلوم الرياضية والفيزيائية، المجلد  497، دار نشر كلوير الأكاديمية، ص  116، ISBN 978-0-7923-4668-5.
• هاراري، فرانك (1969)، نظرية الرسم البياني ، أديسون-ويسلي، MR 0256911 ، OL 5687805M  .
• هورفات، بوريس؛ بيسانسكي، توماز (2010)، "حاصل ضرب الرسوم البيانية ذات المسافة الوحدوية"، الرياضيات المتقطعة ، 310 (12): 1783-1792 ، doi : 10.1016/j.disc.2009.11.035 ، MR 2610282 .
• إمريش، ويلفريد ؛ كلافزار، ساندي (2000)، رسوم بيانية للمنتجات: البنية والتعرف ، وايلي، ISBN 0-471-37039-8.
• إمريش, ويلفريد ; كلافجار، ساندي؛ Rall، Douglas F. (2008)، الرسوم البيانية ومنتجاتها الديكارتية ، AK Peters، ISBN 1-56881-429-1.
• إمريش، ويلفريد ؛ بيترين، إيزتوك (2007)، "التعرف على الضرب الديكارتي في زمن خطي"، الرياضيات المتقطعة ، 307 ( 3-5 ): 472-483 ، doi : 10.1016/j.disc.2005.09.038 ، MR 2287488 .
• كافيه، أ.؛ رحامي، ح. (2005)، "طريقة موحدة لتحليل القيم الذاتية لمنتجات الرسوم البيانية"، مجلة الاتصالات في الطرق العددية في الهندسة مع التطبيقات الطبية الحيوية ، 21 (7): 377-388 ، doi : 10.1002/cnm.753 ، MR 2151527 .
• سابيدوسي، ج. (1957)، "الرسوم البيانية ذات المجموعة المعطاة والخصائص النظرية للرسوم البيانية المعطاة"، المجلة الكندية للرياضيات ، 9 : 515-525 ، doi : 10.4153/CJM-1957-060-7 ، MR 0094810 .
• Sabidussi، G. (1960)، “Graph multiplication”، Mathematische Zeitschrift ، 72 : 446– 457، دوى : 10.1007 / BF01162967 ، hdl : 10338.dmlcz/102459 ، MR 0209177 .
• فيزينغ، في جي (1963)، "الضرب الديكارتي للرسوم البيانية"، أنظمة الفيزياء ، 9 : 30-43 ، MR 0209178 .
• ويبر، مارك (2013)، "المنتجات الحرة لجبر المؤثرات العليا"، نظرية وتطبيقات الفئات ، 28 ( 2): 24-65.

• وايسشتاين، إريك دبليو. "رسم بياني للضرب الديكارتي" . عالم الرياضيات .