الضرب المعجمي: هل تبقى مسافة الطبقة؟

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

قد تصبح أقصر. في مثالنا تحتفظ طبقة A بحواف المسار الثلاث، لكن الطريق A0→B0→A3 يختصر المسافة من 3 إلى 2. إذا كان رأس الطبقة معزولًا في العامل الأول، فلا توجد طبقة مجاورة نستعملها، وتبقى المسافة الداخلية 3.

• الضرب المعجمي يضم رؤوس الأزواج. إذا تجاور الإحداثيان الأولان، تتصل الأزواج مهما كان الإحداثيان الثانيان؛ وعند تساوي الأولين نرجع إلى تجاور الثانيين. ويسمى أيضًا تركيب الرسوم. [1] نعمل على عوامل غير فارغة بسيطة غير موجهة بلا حلقات أو أوزان، والأسماء مثل A0 تمثل أزواجًا.
• للعامل AB BC والعامل 01 12 23 اثنا عشر رأسًا في ثلاث طبقات، وأربع رؤوس في كل طبقة. توجد 9 حواف داخلية و 32 بين الطبقات المتجاورة، فالمجموع 41. لا توجد حواف بين طبقتي A وC مباشرة.
• درجة (a,b) هي 4dG(a)+dH(b) في المثال. A0 درجته 5 وB1 درجته 10 ؛ عمومًا نستبدل 4 بعدد رؤوس العامل الثاني، ولا نجمع درجتين فقط.
• بين طبقتين مختلفتين، مسافة الضرب المعجمي هي مسافة رأسيهما في العامل الأول. داخل طبقة ذات جار في العامل الأول نأخذ min(dH,2)؛ وداخل طبقة رأس معزول تبقى مسافة العامل الثاني. [2] في المثال A0 وA3 مسافتهما 2 بلا حافة مباشرة، وبين A0 وC3 المسافة 2 أيضًا عبر طبقة B.
• احذف BC من العامل الأول، فيصبح C معزولًا. تظل طبقة C مسارًا، فتكون مسافة C0-C3 هي 3. وإذا لم يوجد طريق داخل العامل الثاني، تبقى غير قابلة للوصول في هذه الطبقة المعزولة؛ وجود جار للطبقة كان سيتيح خطوتين.
• ترتيب العاملين مؤثر: المسار الثلاثي أولًا والرباعي ثانيًا يعطيان 41 حافة، وعكسهما يعطي 35 مع بقاء عدد الرؤوس 12. لذلك لا نستبدل ترتيب الطبقات والنسخ ضمنيًا.
• راجعنا 64 زوجًا من عوامل ذات ثلاثة رؤوس، و 576 درجة و 5184 خانة مسافة. منها 1296 حالة داخل طبقة لها جار، و 432 داخل طبقة معزولة، و 3456 بين طبقتين مختلفتين. هذه فئات متنافية تغطي الحصر، لا احتمالات عامة.

حافة العامل الأول تصل طبقتين كاملتين

الضرب المعجمي يضم رؤوس الأزواج. إذا تجاور الإحداثيان الأولان، تتصل الأزواج مهما كان الإحداثيان الثانيان؛ وعند تساوي الأولين نرجع إلى تجاور الثانيين. ويسمى أيضًا تركيب الرسوم. [1]

نختار المسار A-B-C بحافتي AB وBC، والمسار 0-1-2-3 بحواف 01 و 12 و 23. لكل حرف نسخة من الرؤوس الأربعة الرقمية: A0 A1 A2 A3 ، ثم B0 B1 B2 B3 ، ثم C0 C1 C2 C3.

نسمي الرؤوس ذات الحرف نفسه طبقة. داخل طبقة A مثلًا، يثبت الإحداثي الأول، فيتقرر التجاور من المسار الرقمي: A0-A1 وA1-A2 وA2-A3. لا توجد A0-A3 داخلها.

بسبب AB، يصل كل رأس من طبقة A بكل رأس من طبقة B. لذلك توجد A0-B0 وA0-B3 وA3-B0 ، رغم أن 0 و 3 غير متجاورين في العامل الثاني. وجود AB يكفي للحافة العابرة.

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

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

نحتفظ بثلاث نسخ من المسار

لكل طبقة ثلاث حواف داخلية، فتحتفظ الطبقات A وB وC بتسع حواف. لا نغير مسار 0-1-2-3 داخل النسخة؛ مصدر الاختصار الذي سنعرضه هو الحواف خارجها.

بين A وB أربع اختيارات للرأس في الأولى وأربع في الثانية، أي 16 حافة. وبين B وC العدد نفسه. المجموع 9+16+16=41 حافة على 12 رأسًا مسمى. لا نعد الحافة في الاتجاه المعاكس مرة ثانية.

A0 وA3 غير متجاورين، لكنهما يتصلان كلاهما بـB0. إذن A0→B0→A3 طريق من حافتين. ويمكن استعمال B1 أوB2 أوB3 وسيطًا أيضًا؛ شاهد الطريق الأقصر لا يلزم أن يكون وحيدًا.

داخل طبقة A وحدها يوجد A0→A1→A2→A3 بطول 3. إدخال طريق خارجي بطول 2 لا يعني أن الرسم المستحث على طبقة A تغير: حوافه ما زالت حواف المسار، ومسافته إذا منعنا الخروج تظل 3.

بين A0 وC3 ، يحقق A0→B0→C3 خطوتين. الحافة المباشرة غير موجودة لأن AC غائبة؛ لذلك لا تكون المسافة 1. الإحداثي الرقمي في C3 لا يمنع الوصول بحافة من الطبقة الوسطى.

كل جار في الأول يجلب طبقة كاملة

لرأس (a,b)، كل جار لـa في العامل الأول يمنح جميع رؤوس نسخة العامل الثاني جيرانًا. إذا كان عدد رؤوس العامل الثاني m، فهذا النوع يعطي m×dG(a) جيران.

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

في المثال m=4. درجة A في المسار الأول 1 ودرجة 0 في الثاني 1 ، فتكون درجة A0 هي 4×1+1=5. أما B1 فدرجتا مكونيه 2 و 2 ، فيكون 4×2+2=10.

درجات كل من طبقتي A وC هي (5,6,6,5)، ودرجات طبقة B هي (9,10,10,9). مجموع الدرجات 82 ، وهو ضعفا 41 حافة. هذا يراجع قائمة الاتصال ولا يحدد وحده أقصر مسافة.

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

نخرج ونعود عندما يوجد جار

بين طبقتين مختلفتين، مسافة الضرب المعجمي هي مسافة رأسيهما في العامل الأول. داخل طبقة ذات جار في العامل الأول نأخذ min(dH,2)؛ وداخل طبقة رأس معزول تبقى مسافة العامل الثاني. [2]

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

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

عندما توجد مسافة داخلية منتهية dH، يجتمع الطريق الداخلي مع طريق الخطوتين، فيكون الأقصر min(dH,2). وإذا لم يوجد طريق داخلي بين رأسين مختلفين، يظل الطريق الخارجي بطول 2 موجودًا ما دام لرأس الطبقة جار.

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

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

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

استثناء الطبقة التي لا تستطيع الخروج

نغير العامل الأول إلى الحافة AB مع الرأس C معزولًا، ونبقي العامل الثاني 0-1-2-3 كما هو. الطبقتان A وB متصلتان بكل الحواف العابرة، لكن لا حافة تصل طبقة C بأي طبقة أخرى.

تحتفظ طبقة C بالحواف C0-C1 وC1-C2 وC2-C3 فقط. من C0 إلىC3 الطريق الداخلي طوله 3 ، ولا نستطيع استعمال B0 وسيطًا، لأن C0-B0 وB0-C3 غير موجودتين في هذا المدخل.

إذن قاعدة min(dH,2) تحتاج وجود جار لرأس الطبقة في العامل الأول. في طبقة C المعزولة تبقى المسافة dH نفسها؛ وعند الطرف نفسه 0 ، وإذا كانت الطبقة غير متصلة يبقى ما بين مكونيها غير قابل للوصول.

على الطرف الآخر، يبقى A0→B0→A3 بطول 2 لأن AB ما زالت موجودة. عزل C لا يلغي الاختصار داخل طبقة A، ولا يلزم أن يغير جواب كل طرفين في الرسم.

يمكن أن يكون رأس العامل الأول معزولًا بينما رؤوس طبقته لها حواف داخلية؛ في مثال C، درجتا C0 وC3 تساويان 1 وC1 وC2 تساويان 2. لا نصف كل رأس من الطبقة بأنه معزول لمجرد عزل الحرف في العامل الأول.

تبديل العاملين يغير الطبقات

في ترتيبنا الأول نأخذ ثلاث طبقات، كل منها نسخة من مسار بأربعة رؤوس. أعطت نسخ المسار 9 حواف وروابط العامل الأول 32 ، فكان العدد 41.

إذا وضعنا المسار الرباعي أولًا والثلاثي ثانيًا، صارت لدينا أربع طبقات، كل منها ثلاثة رؤوس. الحواف الداخلية 4×2=8 ، وبين كل طبقتين متجاورتين 3×3=9 ؛ توجد ثلاث وصلات في العامل الأول، فتضيف 27. المجموع 35.

العدد الكلي للرؤوس 12 في الترتيبين، لكن اختلاف عدد الحواف يمنع أن يكون الرسمان نفس البنية حتى بعد إعادة تسمية الرؤوس. فلا نعكس ترتيب العاملين كأنه مجرد قلب أسماء الإحداثيات.

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

لا نستعمل هنا ضمًا كاملًا لكل الطبقات ولا سؤالًا عن عدد ألوانها. بعض روابط الطبقات قد تغيب مثل AC، وبعض طبقاتها قد تنعزل؛ تلك الخيارات جزء من العامل الأول وتؤثر في المسافة.

ثلاث فئات في حصر المسافات

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

راجعنا 576 درجة، أي 64×9 ، و 5184 خانة مسافة، أي 64×81. تطابق بحث العرض وفلويد، وراجعت كل درجة صيغة m×dG(a)+dH(b).

قسمنا خانات المسافة إلى 3456 بين طبقتين مختلفتين، و 1296 داخل طبقة ذات جار، و 432 داخل طبقة معزولة. هذه الفئات متنافية ومجموعها 5184 ؛ ليست فحوصًا إضافية نضمها إلى العدد نفسه.

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

المثال الرئيس 12 رأسًا من عاملين بحجمي 3 و 4 ، بينما الحصر الإضافي بحجمي 3 و 3. راجعنا المثال وعكس الترتيب والتحكم المعزول مستقلًا، ولا نزعم حصر جميع أحجام العوامل أو قياس سرعة برنامج.

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