مربع الرسم البياني: هل يكفي تربيع مصفوفة التجاور؟

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

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

• قوة الرسم تحتفظ برؤوسه وتصل بين رأسين إذا وجد طريق لا يزيد طوله على الأس المطلوب. [1] ومربع الرسم هو قوته الثانية. [2] سنقصر الحافة على رأسين مختلفين في رسم بسيط غير موجه وبلا أوزان.
• في المسار AB BC CD، مربع الرسم حوافه AB AC BC BD CD؛ نضيف AC وBD ونحتفظ بالأصل. الخانات الموجبة لمربع المصفوفة خارج القطر تعطي AC وBD فقط، فتفقد الحواف الأصلية الثلاث.
• نسمي مصفوفة التجاور M والناتج الصحيح Q. خارج القطر نضع1 إذا كانت خانة M+M² موجبة، و0 خلاف ذلك؛ على القطر نضع0. قطر M² في مثالنا (1,2,2,1) يعد العودة في خطوتين، ولا يضيف حلقات.
• في الدورة AB BC CD AD، خانة AC في M² تساوي2 لوجود وسيطين B وD، لكنها تعطي حافة واحدة في Q؛ مربع الدورة K4 بست حواف. وفي مثلث، تنجح الخانات الموجبة خارج القطر وحدها، دون أن تصبح قاعدة عامة.
• إضافة رأس معزول E إلى المسار تبقيه معزولًا في المربع. لا يصل التربيع بين مكونات منفصلة ولا يفصل مكونًا قديمًا؛ الطريق بين مكونات مختلفة ما زال غير موجود.
• في رسم متصل، مسافة المربع تساوي ceil(d/2)، حيث d المسافة الأصلية وceil تقريب إلى الأعلى. بين A وD تصبح3 خطوات خطوتين: A→C→D. طول خطوة المربع قد يغطي خطوتين في الأصل، ولا نقسم طول خط مرسوم.
• راجعنا1024 رسمًا مسمى على خمسة رؤوس، وقارنّا25600 خانة تجاور بين حساب المسافة وصيغة المصفوفة. في728 رسمًا متصلًا راجعنا18200 خانة مسافة لقاعدة التقريب؛ النطاق لا يشمل كل الأحجام أو الأوزان والاتجاهات.

الرؤوس نفسها، والحافة يقررها الطريق القصير

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

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

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

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

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

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

المسار يكشف الحواف التي تضيع

نختار A وB وC وD بالحواف AB وBC وCD فقط. المسافات من A إلى B وC وD هي1 و2 و3. ومن B إلى C وD هي1 و2، ومن C إلى D هي1. هذه الأزواج الستة تكفي لحصر حواف المربع.

AB وBC وCD تبقى لأنها مسافات1. ونضيف AC من الطريق A→B→C، وBD من B→C→D، لأن كل منهما بطول2. لا نضيف AD؛ الطريق الوحيد بين الطرفين في المدخل طوله3.

إذن حواف المربع هي AB وAC وBC وBD وCD، وعددها5. درجاته في ترتيب الأسماء (2,3,3,2). لم نحذف A أوD، ولم نحول كل زوج ممكن إلى حافة؛ الزوج AD لا يزال غير متجاور في الناتج.

لو أخذنا الخانات الموجبة من M² خارج القطر وحدها، لحصلنا على AC وBD فقط. لا يوجد سير من خطوتين بين A وB في هذا المسار: جار A الوحيد B، ثم لا توجد حلقة BB للخطوة الثانية. ينطبق الأمر على BC وCD أيضًا.

هاتان الحافتان تعطيان مكونين، A مع C وB مع D، رغم أن الرسم الأصلي متصل. هذا فشل التفسير الذي استخدم بالضبط خطوتين، وليس فشل تعريف مربع الرسم الذي يقبل خطوة واحدة أيضًا.

الصورة الرئيسية تقارن الحواف الخمس الصحيحة بالحافتين المستخرجتين من M² وحده بعد تجاهل القطر. الذهبية في الناتج الصحيح هي AC وBD المضافتان، والزرقاء حواف الأصل. المواضع لا تحدد عضوية الحافة؛ الأسماء والقائمة تفعل ذلك.

العدد في الخانة ليس دائمًا0 أو1

بترتيب A B C D، صفوف M هي (0,1,0,0) و(1,0,1,0) و(0,1,0,1) و(0,0,1,0). عند ضرب المصفوفة في نفسها، خانة الطرفين u وv تجمع M[u,w]M[w,v] على كل اسم وسيط w.

كل حاصل ضرب يساوي1 عندما توجد الحافتان u-w وw-v، ويساوي0 خلاف ذلك. إذن الخانة تعد اختيارات الوسيط لسير من خطوتين. هذا ضرب مصفوفات صفًا في عمود؛ تربيع كل عنصر على حدة يبقي الواحدات والأصفار القديمة ولا يعطي هذا الحساب.

نحصل على صفوف M²: (1,0,1,0) و(0,2,0,1) و(1,0,2,0) و(0,1,0,1). مثلًا خانة AC تساوي1 بوسيط B، وخانة AD صفر. وخانة BB تساوي2 لوجود B→A→B وB→C→B.

على القطر نعود إلى الرأس الذي بدأنا منه، فيكون عدد هذه الرحلات مساويًا لدرجة الرأس الأصلية. لهذا قطر M² هو (1,2,2,1). الرحلة A→B→A تستعمل الحافة AB مرتين، فتتكون من خطوتين، لكنها ليست حلقة AA؛ لا نستبدل رحلة العودة بحافة ذاتية.

نرمز إلى مصفوفة مربع الرسم الصحيح بالحرف Q. إذا اختلف طرفا الخانة، نضع Q[u,v]=1 عندما M[u,v]+M²[u,v]>0، ونضع0 إذا كان المجموع صفرًا. وعلى القطر نثبت Q[u,u]=0 مهما كان عداد العودة.

إضافة M تحفظ طرق الخطوة الواحدة، وM² يضيف طرق الخطوتين. التحويل إلى1 يجيب عن وجود واحد على الأقل بدل تسجيل عدد الوسطاء. لذلك ليست Q مساوية عدديًا لـM+M²، وليست مساوية لـM² حتى بعد إلغاء قطره.

صفوف Q في المسار هي (0,1,1,0) و(1,0,1,1) و(1,1,0,1) و(0,1,1,0). الجدول يثبت ترتيب الأسماء ويتيح مراجعة الفرق بين العداد والمصفوفة الثنائية. مجموع واحدات Q يساوي10، أي ضعفا الحواف الخمس غير الموجهة.

وسيطان لا يصنعان حافتين متكررتين

نأخذ دورة على A B C D بالحواف AB وBC وCD وAD. كل رأس له جاران. بين A وC طريق من خطوتين عبر B وطريق آخر عبر D؛ لذلك خانة AC في M² تساوي2، وخانة BD كذلك2.

أما خانات الحواف الأصلية الأربع في M² فصفر: في هذه الدورة لا يوجد سير من خطوتين بين رأسين متجاورين. إذا اكتفينا بالخانات الموجبة خارج القطر، أخذنا AC وBD فقط مرة أخرى، وفقدنا حواف الدورة.

في مربع الدورة تبقى الأربع وتضاف AC وBD؛ يصبح كل زوج من رأسين مختلفين متجاورًا. لدينا K4 بست حواف، ودرجة3 عند كل اسم. القيمة2 في العداد لم تجعل AC حافتين؛ الرسم البسيط يضع حافة واحدة للزوج.

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

وللتحكم نثبت مثلث ABC بالحواف AB وAC وBC. لكل زوج مختلف وسيط واحد هو الاسم الثالث، فتكون خانات M² خارج القطر موجبة للحواف الثلاث الأصلية نفسها. مربع المثلث هو المثلث، لأن كل طرفين متجاوران من البداية.

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

خطوة جديدة قد تختصر خطوتين قديمتين

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

المسافة الأصلية لا تزيد على طول ذلك السير، لذلك d≤2s. بما أن s عدد صحيح، فهو لا يقل عن ceil(d/2)، أي نأخذ نصف المسافة ونقربه إلى الأعلى. هذا حد أدنى لطول طريق في المربع، لا قسمة لطول خط مطبوع.

نحققه بأخذ طريق أقصر في الأصل وتجميع حوافه في أزواج متتابعة. كل زوج يصبح حافة في المربع، وتبقى حافة منفردة في النهاية إذا كان العدد فرديًا. نحصل على طريق بعدد ceil(d/2) من الحواف الجديدة؛ إذن الحد هو المسافة الفعلية.

بين A وD في المسار الأصلي d=3. الطريق A→C→D في المربع يستخدم الحافة الجديدة AC ثم الأصلية CD، فيعطي2. لا يعطي1، لأن AD ليست حافة في المربع. وإذا كانت المسافة الأصلية2، تصبح1؛ وعند الطرف نفسه تبقى0.

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

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

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

فحص الخانات والمسافات وحدوده

راجعنا جميع1024 قائمة حواف على خمسة رؤوس ثابتة. لكل رسم حسبنا المسافات بالبحث بالعرض، وبنينا المربع من شرط المسافة1 أو2، ثم بنيناه مستقلًا من خانات M+M² الموجبة خارج القطر مع قطر صفري.

في كل مصفوفة25 خانة، فكان عدد خانات التجاور المقارنة1024×25=25600. راجعنا أيضًا أن قطر M² يساوي درجات الأصل، وأن المربع لا يغير إمكان الوصول بين المكونات. هذه رسوم مسماة، لا1024 نوعًا بعد حذف إعادة الأسماء.

من المدخلات728 رسمًا متصلًا. لكل منها قارنا25 خانة مسافة في المربع مع ceil(d/2)، فكان العدد728×25=18200. راجعنا الأمثلة المعلنة كذلك؛ الفحص الشامل الإضافي لخمسة رؤوس، ولا يحصي جميع الأحجام.

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

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

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