الضرب الديكارتي للرسوم: هل نغير الإحداثيين معًا؟

الخلاصة السريعة

لا؛ في الضرب الديكارتي تتغير خانة واحدة على حافة في عاملها، وتبقى الأخرى ثابتة. عند جمع المسار A-B-C مع الضلع 0-1 نحصل على سلم بسبع حواف. تغيير الخانتين على حافتين معًا يصف الضرب المباشر هنا، ويعطي أربع حواف ومكونين، رغم بقاء الرؤوس الستة نفسها.

• في الضرب الديكارتي يتجاور زوجان إذا ثبت أحد الإحداثيين وتجاور الإحداثيان الآخران في عاملهما. [1] أما الضرب المباشر فيشترط تجاور الإحداثيين الأولين والثانيين معًا. [2]
• نختار عاملًا بالحواف AB وBC، وعاملًا بالضلع 01. الرؤوس الستة في الرسمين هي A0 A1 B0 B1 C0 C1؛ الرمز A0 اسم للزوج (A,0)، وليس حاصل ضرب حرف وعدد.
• شرط الخانة الواحدة يعطي AB في كل طبقة وBC في كل طبقة وثلاث وصلات بين الطبقتين: سبع حواف وسلم متصل. شرط الخانتين يعطي A0-B1 وA1-B0 وB0-C1 وB1-C0 فقط: أربع حواف ومكونين.
• درجة (a,b) تساوي مجموع درجتي a وb في الديكارتي، وحاصل ضربهما في المباشر. عند B0 نحصل على3 في الأول و2 في الثاني؛ عدد الرؤوس نفسه لا يضمن الدرجة أو الاتصال نفسه.
• للعاملين المتصلين، مسافة الديكارتي تساوي مجموع مسافتي الإحداثيين. من A0 إلى C1 نحتاج3 خطوات؛ المسار A0→B0→C0→C1 يحققها. في الرسم المباشر لا يوجد طريق بين هذين الطرفين في مثالنا.
• راجعنا16 زوجًا من عوامل مسماة بأحجام3 و2، وقارنّا بحث العرض بفلويد للمنتجين. في الأزواج الأربعة ذات العاملين المتصلين تحقق جمع المسافات في144 خانة؛ هذا نطاق محدود، لا جميع أحجام الرسوم.

الأزواج تحدد الرؤوس، والشرط يحدد الحواف

في الضرب الديكارتي يتجاور زوجان إذا ثبت أحد الإحداثيين وتجاور الإحداثيان الآخران في عاملهما. [1] أما الضرب المباشر فيشترط تجاور الإحداثيين الأولين والثانيين معًا. [2]

نثبت عاملين بسيطين غير موجهين وغير موزونين. الأول أسماؤه A وB وC، وحافتاه AB وBC؛ والثاني أسماؤه0 و1، وحافته الوحيدة01. لا توجد حلقات من رأس إلى نفسه أو حواف إضافية في أي عامل.

لكل اختيار من العامل الأول اختياران من الثاني، فتكون الرؤوس (A,0) و(A,1) و(B,0) و(B,1) و(C,0) و(C,1). سنختصرها إلى A0 A1 B0 B1 C0 C1. الخانة الأولى اسم في العامل الأول، والثانية اسم في العامل الثاني.

هذه القائمة واحدة في كلا الناتجين. لكنها لا تقول أي زوجين موصولان بحافة. لتحديد ذلك نحتاج شرط التجاور؛ تغيير الشرط مع الاحتفاظ بالرؤوس يمكن أن يغير عدد الحواف والدرجات والمكونات والمسافات.

إذا كان الطرفان A0 وB0، ثبتت الخانة الثانية0، وتحركت الأولى على الحافة AB؛ يقبلهما الشرط الديكارتي. وإذا كانا A0 وA1، ثبتت الأولىA وتحركت الثانية على01؛ يقبلهما الشرط نفسه.

أما A0 وB1 فتغيرت الخانتان، مع أن كل تغيير يوافق حافة في عامله. لا يقبلهما الديكارتي؛ يقبلهما المباشر. هذان الاختباران يميزان الشرطين قبل رسم كل الحواف، ولا نكتفي بالشكل الذي يوحي به ترتيب النقاط.

تغيير خانة واحدة يبني السلم

نثبت الثانية0، فننسخ حافتي العامل الأول إلى A0-B0 وB0-C0. وبالمثل عند الثانية1 نحصل على A1-B1 وB1-C1. هاتان طبقتان، في كل منهما مسار من ثلاث نقاط وحافتين.

ثم نثبت الأولى عند A، فننسخ01 إلى A0-A1. نفعل الشيء نفسه عند B وعند C، فتضاف B0-B1 وC0-C1. لدينا أربع حواف داخل الطبقتين وثلاث حواف بينهما، أي سبع حواف معلنة بلا زيادات.

الصورة الرئيسية على اليسار تعرض هذه الحواف. الخط الأفقي يغير الحرف ويثبت الرقم، والرأسي يغير الرقم ويثبت الحرف. هذا ترتيب اختير لتوضيح القاعدة؛ الاتجاه في الصفحة ليس جزءًا من تعريف الحافة غير الموجهة.

هذا المدخل رسم سلمي من حاصل ضرب مسار بضلع. [1] يمكن الوصول بين أي رأسين: نتحرك بالحرف في طبقته حتى نصل إلى الحرف المطلوب، ثم نغير الرقم عنده إن لزم. لا نحتاج قطري A0-B1 أو B0-C1 لتحقيق الاتصال.

في النموذج غير الموزون كل حافة خطوة واحدة. طول الخط في الصورة لا يجعل الحافة الأفقية أكثر كلفة من الرأسية، ولا يجعل رسم نقطتين متقاربتين دليلًا على وجود وصلة بينهما. نقرأ قائمة الحواف أولًا ثم نحسب الطريق.

تغيير الخانتين يترك مكونين

نطبق الشرط الآخر على الرؤوس نفسها. الحافة AB مع01 تعطي A0-B1 وA1-B0؛ والحافة BC مع01 تعطي B0-C1 وB1-C0. لا نضيف A0-A1 لأن الحرف ثابت، ولا A0-B0 لأن الرقم ثابت.

إذن توجد أربع حواف. المكون الأول مساره A0-B1-C0، والثاني مساره A1-B0-C1. المجموعتان منفصلتان؛ لا يوجد طرف لحافة في إحداهما وطرفها الآخر في الثانية وفق القائمة المعلنة.

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

نستطيع إثبات الانفصال دون الاعتماد على الصورة. نعطي الحروف A وB وC القيم0 و1 و2، ونضيف إليها الرقم الثاني. في كل حافة من المباشر تتغير قيمة الحرف بمقدار1 والرقم بمقدار1؛ تغير المجموع زوجي، فيبقى نوعه زوجيًا أو فرديًا.

A0 وB1 وC0 لها مجاميع زوجية، وA1 وB0 وC1 فردية. لا تستطيع خطوة من هذا الرسم نقلنا من مجموعة إلى الأخرى. وبوجود مسار يربط الثلاثة داخل كل مجموعة، ثبت أن العدد مكونان بالضبط، لا مجرد وجود انفصال ما.

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

الدرجة تكشف الفرق محليًا

لرأس (a,b) في الديكارتي، جيرانه نوعان: جيران a مع إبقاء b، وجيران b مع إبقاء a. النوعان لا يتداخلان في العاملين البسيطين؛ الأول يغير الأولى فقط والثاني يغير الثانية فقط. لذلك درجة الزوج مجموع درجتي مكونيه.

في المباشر نختار جارًا لـa وجارًا لـb في الخطوة نفسها. كل اختيار من الأول يمكن اقترانه بكل اختيار من الثاني، والأزواج الناتجة مختلفة، فيكون عدد الجيران حاصل ضرب الدرجتين. هذه حجة عد، لا ضرب لأسماء الرؤوس.

في المسار درجتا A وC تساويان1 ودرجة B تساوي2. وفي الضلع درجة0 ودرجة1 كلتاهما1. لذلك درجتا B0 وB1 في الديكارتي تساويان2+1=3، وفي المباشر2×1=2؛ بقية الرؤوس لها2 في الأول و1 في الثاني.

الجدول يراجع الأسماء بالترتيب A0 A1 B0 B1 C0 C1. مجموع درجات الديكارتي14، وبقسمة كل طرفي الحافة نحصل على7 حواف. وفي المباشر المجموع8، فيعطي4. لا نستعمل الدرجة وحدها لاستنتاج الاتصال، بل نستعملها لفحص قوائم الحواف.

ولحساب عدد حواف الديكارتي عمومًا في هذا النموذج، لكل رأس في العامل الثاني نسخة من حواف الأول، ولكل رأس في الأول نسخة من حواف الثاني. [1] هنا العدد2×2+3×1=7. لا نخلطه مع عدد الرؤوس3×2=6، أو مع2×2×1=4 للشرط المباشر.

تساوي عدد الرؤوس في الناتجين لا يعني أن لدينا الرسم نفسه. حتى أسماء الأزواج يمكن أن تبقى ثابتة بينما تتغير درجة B0 من3 إلى2 وتتغير عضوية الطريق. افحص شرط الحافة أو قائمتها قبل استعمال أي نتيجة تعتمد على الرسم.

لماذا تجمع المسافة في الديكارتي؟

نفترض الآن أن العاملين متصلان. كل خطوة ديكارتية تغير خانة واحدة، على حافة في عامل تلك الخانة. إذا ذهبنا من (a,b) إلى (c,d)، فإن خطوات الخانة الأولى تشكل سيرًا من a إلى c في العامل الأول، والثانية سيرًا من b إلى d في الثاني.

عدد خطوات الأولى لا يقل عن مسافتها الأقصر، وكذلك الثانية. والخطوات لا تحسب في الفئتين معًا، لأن الحافة تغير خانة واحدة فقط. لذلك طول أي طريق في المنتج لا يقل عن مجموع المسافتين في العاملين.

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

من A0 إلى C1، المسافة من A إلى C في المسار2، ومن0 إلى1 في الضلع1؛ المجموع3. المسار A0→B0→C0→C1 شاهد بثلاث خطوات. والمسار A0→A1→B1→C1 شاهد آخر بالطول نفسه؛ ليس الأقصر بالضرورة وحيدًا.

الصورة الداخلية تلون أحد الشاهدين في كل لوحة على السلم نفسه. المجموعتان لا تضيفان حافة قطرية ولا تحذفان غيرها؛ اللون يبرز الطريق المحدد. يتغير موضع خطوة تغيير الرقم دون أن يتغير طول الطريق النهائي.

قائمة المسافات من A0 في ترتيب الجدول هي (0,1,1,2,2,3). في المباشر لا يصل A0 إلى C1 أصلًا في هذا المدخل؛ اختلاف زوجية المجموع يثبت ذلك. لا نضع العدد3 في خانة طريق غير موجود، ولا نستعمل جمع المسافات كقاعدة للمنتج الآخر.

ما الذي راجعناه وما الذي يتغير؟

راجعنا جميع ثماني قوائم حواف ممكنة على ثلاثة أسماء ثابتة، وكلتا قائمتي الحواف على اسمين ثابتين: وجود الضلع أو غيابه. بذلك لدينا8×2=16 زوجًا من العوامل المسماة، ونبني الديكارتي والمباشر لكل زوج من قاعدة التجاور.

فحصنا عدد الحواف والدرجات وقارنّا جميع المسافات بين بحث العرض وحساب فلويد في كلا المنتجين. أربعة أزواج من المدخلات لها عاملان متصلان؛ لكل منتج ديكارتي منها ستة رؤوس و36 خانة مسافة، فراجعنا4×36=144 خانة لجمع المسافتين.

هذه ليست16 نوعًا مختلفًا بعد حذف إعادة التسمية، ولا جميع الرسوم بكل أحجامها. كذلك لا تعطي نتيجة التنفيذ وحدها برهانًا عامًا؛ الحجة العامة للدرجة وجمع المسافة سبقت الحساب، والبرنامج راجع أمثلة ضمن نطاق معلن.

لا ندعي أن قواعد حاصل الضرب أو السلم نتيجة جديدة. الجديد في العرض هو المدخل الصغير المعلن وقوائمه وشاهدا الطريق ومراجعة التغير في الشرط على الرؤوس نفسها. لم نستعمل صور المرجعين أو برنامجًا ذا نتيجة غير معروضة بدل الحساب.

نستبعد الأوزان والاتجاهات والحلقات من هذا المقال. إذا تغير النموذج وجب إعادة معنى الحافة والدرجة والطول. وفي حجة جمع المسافة طلبنا عاملين متصلين حتى يوجد الطريق المطلوب في كليهما؛ لا نفرض عددًا منتهيًا لطريق بين مكونات منفصلة.

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