ناتج الرسم البياني

في نظرية المخططات ، يُعدّ ضرب المخططات عملية ثنائية على المخططات _{. تحديدًا} ، هي عملية تأخذ مخططين G1 و _G2 وتنتج مخططًا H بالخصائص التالية:

• مجموعة رؤوس H هي حاصل الضرب الديكارتي V ( G ₁ ) × V ( G ₂ ) ، حيث V ( G ₁ ) و V ( G ₂ ) هما مجموعتا رؤوس G ₁ و G ₂ ، على التوالي .
• يتم توصيل رأسين ( a1 _, a2 ₎ و ( b1 , b2 ) من H بواسطة حافة ، إذا _وفقط إذا _تم استيفاء شرط _حول a1 _, b1 في G1 _و a2 , _b2 في G2 .​_​​

تختلف نواتج الرسم البياني في تحديد ماهية هذا الشرط تحديدًا. يتعلق الأمر دائمًا بما إذا كانت الرؤوس a _و b في الرسم _{البياني} G متساوية _أم متصلة بحافة.

تختلف المصطلحات والرموز المستخدمة في منتجات الرسوم البيانية المحددة في الأدبيات بشكل كبير؛ حتى لو كان ما يلي يُعتبر معياريًا إلى حد ما، يُنصح القراء بالتحقق من التعريف الذي يستخدمه مؤلف معين لمنتج الرسم البياني، خاصة في النصوص القديمة.

حتى مع التعريفات الأكثر شيوعًا، لا يوجد اتساق دائم في المراجع حول كيفية التعامل مع الحلقات الذاتية . وقد تفشل الصيغ المذكورة أدناه لحساب عدد الحواف في عملية الضرب عند تضمين الحلقات الذاتية. على سبيل المثال، حاصل الضرب الموتري لحلقة ذاتية ذات رأس واحد مع نفسها هو حلقة ذاتية أخرى ذات رأس واحد مع${\displaystyle E=1}$وليس${\displaystyle E=2}$كما في الصيغة${\displaystyle E_{G\times H}=2E_{G}E_{H}}$أقترح ذلك.

يوضح الجدول التالي أكثر منتجات الرسوم البيانية شيوعًا، مع${\displaystyle \sim }$يشير إلى "متصل بحافة إلى"، و${\displaystyle \not \sim }$للدلالة على عدم التجاور. بينما${\displaystyle \not \sim }$يسمح بالمساواة،${\displaystyle \not \simeq }$يعني ذلك أنه يجب أن تكون متميزة وغير متجاورة. رموز العمليات المذكورة هنا ليست قياسية بأي حال من الأحوال، خاصة في الأوراق القديمة.

اسم	شرط لـ${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$		عدد الحواف${\displaystyle {\begin{array}{cc}v_{1}=\vert \mathrm {V} (G_{1})\vert &v_{2}=\vert \mathrm {V} (G_{2})\vert \\e_{1}=\vert \mathrm {E} (G_{1})\vert &e_{2}=\vert \mathrm {E} (G_{2})\vert \end{صفيف}}}$	مثال
		مع${\displaystyle a_{n}~{\text{rel}}~b_{n}}$يُختصر إلى${\displaystyle {\text{rel}}_{n}}$
المنتج الديكارتي (المنتج المعبأ)${\displaystyle G_{1}\square G_{2}}$	${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$${\displaystyle \lor }$${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}=b_{2}}$	${\displaystyle =_{1}~\sim _{2}}$${\displaystyle \lor }$${\displaystyle \sim _{1}~=_{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}}$
حاصل الضرب الموتري (حاصل ضرب كرونكر، حاصل الضرب الفئوي)${\displaystyle G_{1}\times G_{2}}$	${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle \sim _{1}~\sim _{2}}$	${\displaystyle 2~e_{1}~e_{2}}$
منتج قوي (منتج عادي، منتج AND)${\displaystyle G_{1}\boxtimes G_{2}}$${\displaystyle =(G_{1}\times G_{2})\cup (G_{1}\square G_{2})}$	${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$${\displaystyle \lor }$${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}=b_{2}}$${\displaystyle \lor }$${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle =_{1}~\sim _{2}}$${\displaystyle \lor }$${\displaystyle \sim _{1}~=_{2}}$${\displaystyle \lor }$${\displaystyle \sim _{1}~\sim _{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}~+~2~e_{1}~e_{2}}$
منتج معجمي${\displaystyle G_{1}\cdot G_{2}}$أو${\displaystyle G_{1}[G_{2}]}$	${\displaystyle a_{1}\sim b_{1}}$${\displaystyle \lor }$${\displaystyle a_{1}=b_{1}~\land ~a_{2}\sim b_{2}}$	${\displaystyle \sim _{1}}$${\displaystyle \lor }$${\displaystyle =_{1}~\sim _{2}}$	${\displaystyle v_{1}~e_{2}~+~e_{1}~v_{2}^{2}}$
المنتج المشترك (المنتج الانفصالي، [ 1 ] منتج OR)${\displaystyle G_{1}*G_{2}}$أو${\displaystyle G_{1}\lor G_{2}}$${\displaystyle =G_{1}[G_{2}]\cup G_{2}[G_{1}]}$${\displaystyle ={\overline {\;{\overline {G_{1}}}\boxtimes {\overline {G_{2}}}\;}}}$	${\displaystyle a_{1}\sim b_{1}}$${\displaystyle \lor }$${\displaystyle a_{2}\sim b_{2}}$	${\displaystyle \sim _{1}}$${\displaystyle \lor }$${\displaystyle \sim _{2}}$	${\displaystyle v_{1}^{2}~e_{2}~+~e_{1}~v_{2}^{2}~-~2~e_{1}~e_{2}}$
منتج معياري${\displaystyle G_{1}\diamond G_{2}}$${\displaystyle =(G_{1}\boxtimes G_{2})\cup ({\overline {G_{1}}}\times {\overline {G_{2}}})}$	${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}}$${\displaystyle \lor }$${\displaystyle a_{1}\not \simeq b_{1}~\land ~a_{2}\not \simeq b_{2}}$	${\displaystyle \sim _{1}~\sim _{2}}$${\displaystyle \lor }$${\displaystyle \not \simeq _{1}~\not \simeq _{2}}$
منتج متجذر	انظر المقال		${\displaystyle v_{1}~e_{2}~+~e_{1}}$
منتج متعرج	انظر المقال		انظر المقال	انظر المقال
منتج بديل
المنتج المتماثل [ 2 ] [ 4 ]${\displaystyle G_{1}\ltimes G_{2}}$	${\displaystyle a_{1}=b_{1}}$${\displaystyle \lor }$${\displaystyle a_{1}\sim b_{1}~\land ~a_{2}\not \sim b_{2}}$	${\displaystyle =_{1}}$${\displaystyle \lor }$${\displaystyle \sim _{1}~\not \sim _{2}}$	${\displaystyle v_{1}v_{2}(v_{2}-1)/2+e_{1}(v_{2}^{2}-2e_{2})}$

بشكل عام، يتم تحديد ناتج الرسم البياني بأي شرط لـ${\displaystyle (a_{1},a_{2})\sim (b_{1},b_{2})}$يمكن التعبير عن ذلك من حيث${\displaystyle a_{n}=b_{n}}$و${\displaystyle a_{n}\sim b_{n}}$.

يترك${\displaystyle K_{2}}$ليكن الرسم البياني الكامل على رأسين (أي حافة واحدة). الرسوم البيانية الناتجة${\displaystyle K_{2}\square K_{2}}$،${\displaystyle K_{2}\times K_{2}}$، و${\displaystyle K_{2}\boxtimes K_{2}}$تبدو تمامًا مثل الرسم البياني الذي يمثل المؤثر. على سبيل المثال،${\displaystyle K_{2}\square K_{2}}$هي دورة رباعية (مربع) و${\displaystyle K_{2}\boxtimes K_{2}}$هو الرسم البياني الكامل على أربعة رؤوس.

ال${\displaystyle G_{1}[G_{2}]}$يُستخدم رمز الضرب المعجمي للتذكير بأن هذا الضرب ليس تبادليًا. يبدو الرسم البياني الناتج وكأنه استبدال نسخة من${\displaystyle G_{2}}$لكل رأس من${\displaystyle G_{1}}$.

• عمليات الرسم البياني

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