الضرب القوي للرسوم: لماذا نأخذ أكبر المسافتين؟

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

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

• في الضرب القوي، يتجاور زوجان مختلفان إذا تغير إحداثي على حافة في عامله وبقي الآخر ثابتًا، أو تغير الإحداثيان على حافتين معًا. الرؤوس أزواج من رأسي العاملين. [1] [2] نعتمد عاملين بسيطين غير موجهين بلا حلقات أو أوزان، ونستبعد تساوي الزوجين حتى لا نضيف حلقة.
• للعامل AB BC والعامل 01 12 تسعة رؤوس: A0 A1 A2 B0 B1 B2 C0 C1 C2. المنتج القوي له 20 حافة: 12 تغير خانة واحدة و8 تغير الخانتين معًا.
• جيران تغيير خانة واحدة وجيران تغيير الخانتين ثلاث فئات منفصلة. درجة (a,b) هي dG(a)+dH(b)+dG(a)dH(b)؛ عند B1 تساوي 2+2+4=8، مقابل 4 في الديكارتي.
• مسافة الضرب القوي تساوي أكبر مسافتي الإحداثيين، بينما تجمع المسافتان في الضرب الديكارتي. [3] نطلب وجود الطريق في العاملين، ونقيس طول الطريق بعدد حوافه في النموذج غير الموزون. من A0 إلى C2 يحقق A0→B1→C2 العدد 2، ولا توجد حافة مباشرة A0-C2.
• كل طريق يحتاج عدد خطوات لا يقل عن كل مسافة في عاملها، فيحتاج الأكبر على الأقل. نحقق هذا الحد بمزامنة طريقين أقصر مع تثبيت الإحداثي الذي يصل مبكرًا؛ من A0 إلى C1 نحتاج خطوتين رغم اختلاف المسافتين 2 و1.
• الضرب القوي ليس الضرب المباشر الذي يفرض تغيير الخانتين في كل حافة، وليس مربع الديكارتي. A0-C0 ليست حافة قوية رغم أن مسافتها الديكارتية 2. وضرب ضلعين قويًا يعطي K4 بست حواف.
• راجعنا 64 زوجًا من عوامل ذات ثلاثة رؤوس، و576 درجة و5184 خانة مسافة، بالبحث بالعرض وفلويد. منها 16 زوجًا بعاملين متصلين و1296 خانة منتهية. الأعداد حصر محدد، ولا نضع مسافة منتهية عندما يغيب طريق في أحد العاملين.

ثلاث حالات لحافة واحدة

في الضرب القوي، يتجاور زوجان مختلفان إذا تغير إحداثي على حافة في عامله وبقي الآخر ثابتًا، أو تغير الإحداثيان على حافتين معًا. الرؤوس أزواج من رأسي العاملين. [1] [2]

نثبت عاملين: المسار A-B-C بحافتي AB وBC، والمسار 0-1-2 بحافتي 01 و12. لا توجد AC أو02. الأسماء A0 وB1 اختصار للزوجين (A,0) و(B,1)، وليست ضربًا لحرف في عدد.

بين A0 وB0 تتغير الأولى على AB وتثبت الثانية0. وبين A0 وA1 تثبت الأولىA وتتغير الثانية على01. وبين A0 وB1 يتغير الاثنان، على AB و01 معًا؛ الحالات الثلاث تقبل حافة قوية.

أما A0 وC0 فلا يتجاوران لأن AC ليست حافة في العامل. وكذلك A0 وC2: لا توجد AC ولا02. عبارة السماح بتغيير الإحداثيين لا تعني السماح بأي قفزة بين أسماء العاملين.

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

اثنتا عشرة حافة وثمانية أقطار

ننسخ AB وBC عند الأرقام0 و1 و2، فنحصل على ست حواف تغير الحرف وحده. وننسخ 01 و12 عند A وB وC، فتضاف ست تغير الرقم وحده. هذه الحواف الاثنتا عشرة هي حواف المنتج الديكارتي للعاملين.

لكل اقتران من حافة حرفية وحافة رقمية نضيف وصلتين تغيران الخانتين: AB مع01 تعطي A0-B1 وA1-B0. وعدد اقترانات حواف العاملين 2×2=4، فيعطي ثماني حواف إضافية.

مع AB و12 نضيف A1-B2 وA2-B1. ومع BC و01 نضيف B0-C1 وB1-C0، ومع BC و12 نضيف B1-C2 وB2-C1. لا تتداخل هذه الثماني مع حواف تغيير خانة واحدة.

المجموع20 حافة على تسعة أسماء. تقاطع قطرين بين دوائر الصورة لا يضيف رأسًا عاشرًا. الأقطار تصف نوع الحركة في ترتيب الرسم، ولا تحمل كلفة أطول من الحواف الأفقية أو الرأسية.

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

نجمع ثلاث فئات من الجيران

للرأس (a,b)، اختر جارًا لـa وثبت b؛ هذه الفئة لها dG(a) جيران. وثبت a واختر جارًا لـb؛ الثانية لها dH(b). وأخيرًا اختر جارًا من كل عامل؛ الثالثة لها dG(a)dH(b).

الفئات لا تتداخل في عاملين بسيطين بلا حلقات: الأولى تغير الأولى فقط، والثانية الثانية فقط، والثالثة الاثنتين. لذلك نجمع أعدادها ونحصل على dG(a)+dH(b)+dG(a)dH(b).

في B1، درجة كل مكون2، فدرجة الزوج8. بالفعل يتصل B1 بكل الأسماء الثمانية الأخرى في هذا المثال. وفي A0 نجد1+1+1=3، وجيرانه B0 وA1 وB1 فقط.

الدرجات بالترتيب A0 A1 A2 B0 B1 B2 C0 C1 C2 هي (3,5,3,5,8,5,3,5,3). مجموعها40، أي ضعفا الحواف العشرين. في الديكارتي الدرجات (2,3,2,3,4,3,2,3,2)، ومجموعها24.

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

نسير بالإحداثيين في الوقت نفسه

مسافة الضرب القوي تساوي أكبر مسافتي الإحداثيين، بينما تجمع المسافتان في الضرب الديكارتي. [3] نطلب وجود الطريق في العاملين، ونقيس طول الطريق بعدد حوافه في النموذج غير الموزون.

افترض أن طول الطريق الأقصر من a إلى c في العامل الأول هو r، ومن b إلى d في الثاني هو s. في كل خطوة قوية يستطيع كل إحداثي عبور حافة واحدة على الأكثر، أو البقاء حيث هو.

إسقاط طريق المنتج على العامل الأول مع حذف مواضع الثبات يعطي سيرًا في هذا العامل. إذا كان طريق المنتج طوله k فلا يزيد عدد خطوات الإسقاط على k، لذلك r≤k. وبالمثل s≤k، فيكون k≥max(r,s).

نحقق الحد بأخذ طريق أقصر في كل عامل وبدء السير بهما معًا. عندما ينتهي الأقصر نثبت إحداثيه ونواصل الآخر. كل خطوة تغير الخانتين أو خانة واحدة على حواف مسموحة؛ ينتهي الاثنان بعد max(r,s) خطوات.

في مثال A0 وC2، نأخذ A→B→C و0→1→2 معًا. يظهر A0→B1→C2 بطول2. لا يمكن طول1 لأن الطرفين ليسا متجاورين، وحد العامل الأول وحده يطلب خطوتين.

وللطرفين A0 وC1 المسافتان2 و1. يحقق A0→B1→C1 خطوتين: في الأولى نغير الاثنتين، وفي الثانية نثبت الرقم1. هذا يبين دور السماح بخانة واحدة؛ لا نضطر إلى مواصلة تحريك الرقم بعد وصوله.

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

لماذا لا نسميه مربع الديكارتي؟

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

A0→B0→C0 طريق ديكارتي بطول2. مع ذلك A0-C0 ليست حافة قوية لأن الحرفين A وC غير متجاورين. أما A0→B0→B1 بطول2 في الديكارتي، وطرفاه A0 وB1 يتجاوران قويًا لأن AB و01 حافتان.

ولا يساوي الضرب المباشر: المباشر يأخذ حركة الخانتين فقط. القوي يحتفظ بها ويضيف حركات الخانة الواحدة. الطريق A0→B1→C1 يحتاج في نهايته خانة واحدة، فتكون هذه الحافة قوية وليست مباشرة.

لضبط العد نأخذ ضلع AB وضلع 01. على الأزواج الأربعة A0 A1 B0 B1 توجد أربع حواف لتغيير خانة واحدة وقطران لتغيير الاثنتين. يصبح الناتج القوي K4 بست حواف؛ وليس دورة الحواف الأربع وحدها.

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

حصر صغير وبرهان مستقل

ثلاثة رؤوس مسماة تتيح ثلاث حواف ممكنة، أي 2³=8 رسوم بسيطة. اخترنا كل مدخل للأول وكل مدخل للثاني، فكان العدد8×8=64 زوجًا مرتبًا. لكل منتج تسعة رؤوس، ولم نحذف مدخلًا بعد إعادة التسمية.

بنينا الحواف من حالات التجاور الثلاث، ثم راجعناها من حاصل ضرب مجموعتي الجيران مع الرأس نفسه، بعد استبعاد الزوج الذي لم يتحرك. طابقت القائمتان في كل حالة، وراجعنا576 درجة، أي64×9.

حسبنا المسافات ببحث العرض وبخوارزمية فلويد مستقلًا، وقارنا5184 خانة، أي64×81. طابق القوي أكبر مسافتي العاملين عندما وجد الطريقان، وطابق الديكارتي مجموعهما. وعندما غاب أحدهما بقيت الخانة غير قابلة للوصول.

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

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

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