متمم الرسم: هل نقلب أصفار القطر إلى واحدات؟

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

لا نقلب أصفار القطر إلى واحدات في متمم رسم بسيط بلا حلقات. نقلب خانات التجاور خارج القطر فقط، ونترك القطر صفرًا. في مثال A B C D E F تصبح الحواف الخمس الأصلية غائبة، وتظهر الحواف العشر الأخرى. إذا كانت J كلها واحدات وI مصفوفة الوحدة، فالمصفوفة الصحيحة C=J−I−M، أما W=J−M فيضيف ست حلقات ذاتية.

• متمم الرسم يحتفظ بمجموعة الرؤوس ويأخذ الحواف الغائبة بين هذه الرؤوس. [1] نعمل هنا على رسم بسيط غير موجه بلا حلقات أو أوزان، ونعد كل حافة مرة واحدة.
• المسار AB BC CD DE EF يضم خمس حواف على ستة رؤوس. توجد15 وصلة ممكنة بين رأسين مختلفين؛ يأخذ المتمم الوصلات العشر الباقية ولا يضيف رأسًا أو يحذفه.
• مصفوفة التجاور في الرسم البسيط بلا حلقات ذات قطر صفري وخانات متناظرة للرسم غير الموجه. [2] نثبت ترتيب A B C D E F ونقلب الخانات خارج القطر فقط.
• نعرف J بأنها مصفوفة الواحدات وI بأنها الوحدة. C=J−I−M يبقي القطر صفرًا، بينما W=J−M يجعل خانات القطر الست1؛ لهذا لا يمثل W متمم الرسم البسيط المطلوب.
• درجات المسار (1,2,2,2,2,1)، ودرجات المتمم (4,3,3,3,3,4). كل درجتين متناظرتين تجمعان إلى5. تطبيق عملية المتمم الصحيحة مرتين يعيد المصفوفة الأصلية.
• فحصنا المصفوفة المعلنة وراجعنا القطر والحواف والدرجات، ثم اختبرنا المتمم مرتين على جميع1024 رسمًا بسيطًا ذا خمسة رؤوس ثابتة. نطاق الفحص خمسة رؤوس؛ لا ندعي حصر الرسوم ذات الستة رؤوس كلها.

نحتفظ بالرؤوس ونبدل الحواف الممكنة

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

الأسماء A وB وC وD وE وF تمثل ستة رؤوس مختلفة. حافة AB هي حافة BA نفسها، ولا نعدها مرتين. لا أوزان ولا اتجاهات ولا حواف متكررة. والصورة وسيلة لعرض القائمة؛ تقاطع خطين دون دائرة مسماة لا يضيف رأسًا جديدًا.

توجد15 مجموعة من رأسين مختلفين في هذه الأسماء الستة. نستطيع عدها بدءًا بـA مع الخمسة الآخرين، ثم B مع الأربعة اللاحقين، ثم C مع ثلاثة، ثم D مع اثنين، ثم E مع F. الناتج5+4+3+2+1=15.

لا ندخل AA أوBB في هذه القائمة. الحافة التي تبدأ من الرأس نفسه وتنتهي عنده حلقة ذاتية، وهي خارج المدخل الذي اتفقنا عليه. لذلك غيابها لا يعني أننا سنضيفها عند تكوين المتمم؛ فضاء الحواف الممكنة استبعدها أولًا.

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

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

من خمس حواف في المسار إلى عشر في المتمم

نبدأ بالحواف AB وBC وCD وDE وEF فقط. يصل هذا المسار الرؤوس بالترتيب A ثم B ثم C ثم D ثم E ثم F. ليس فيه AF، وليس فيه اتصال مباشر بين A وC؛ إمكانية السير عبر B لا تحول AC إلى حافة موجودة.

نكتب الأزواج التي يغيب اتصالها المباشر: AC وAD وAE وAF وBD وBE وBF وCE وCF وDF. عددها10. هذه هي حواف المتمم في مثالنا، وتظل أسماء الرؤوس الستة كما كانت في المسار.

يمكن فحص القائمة رأسًا رأسًا. A متصل في المسار بـB فقط، فيتصل في المتمم بـC وD وE وF. B متصل في المسار بـA وC، فيصبح جيرانه في المتمم D وE وF. الحافة AB اختفت، والحافة AF ظهرت.

C كان جارًا لـB وD، فأصبح جيرانه A وE وF. وD كان جارًا لـC وE، فأصبح جيرانه A وB وF. ثم E يتصل في المتمم بـA وB وC، وF يتصل بـA وB وC وD. هذه القراءة تعيد الحواف العشر نفسها دون إضافة أسماء.

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

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

خانات التجاور والقطر في ترتيب واحد

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

صف A في M هو (0,1,0,0,0,0)، وصف B هو (1,0,1,0,0,0)، وصف C هو (0,1,0,1,0,0). الخانة الأولى من صف A تخص AA، والثانية تخص AB. وجود الرأس A ثابت، والصفر الأول يصف غياب الحلقة فقط.

صف D في M هو (0,0,1,0,1,0)، وصف E هو (0,0,0,1,0,1)، وصف F هو (0,0,0,0,1,0). مجموع خانات M التي تساوي1 هو10، لأن الحواف الخمس تظهر في موضعين متناظرين لكل حافة.

لنسم مصفوفة المتمم الصحيح C. صفوف A وB وC فيها هي (0,0,1,1,1,1) و(0,0,0,1,1,1) و(1,0,0,0,1,1). يبقى الصفر القطري في موضعه، بينما تتبادل الواحدات والأصفار خارج القطر دورها من M إلى C.

صفوف D وE وF في C هي (1,1,0,0,0,1) و(1,1,1,0,0,0) و(1,1,1,1,0,0). مجموع الواحدات20، أي ضعفا الحواف العشر. عند مراجعة الخانة CF نقرأ1 من صف C وعمود F، ونجد أيضًا1 في الخانة FC.

الحرف C يستخدم هنا أيضًا اسمًا لرأس في القائمة. حين نقول «مصفوفة C» نقصد جدول الستة صفوف، وحين نقول «الرأس C» نقصد الاسم الثالث. يمكن تغيير رمز المصفوفة، لكن لا نغير ترتيب الأعمدة أثناء فحص الأرقام.

لماذا نطرح I بعد قلب الواحدات؟

نعرف J بأنها مصفوفة من ستة صفوف وستة أعمدة، وجميع خاناتها1. ونعرف I بأنها مصفوفة الوحدة ذات1 على القطر و0 خارجه. التعريفان مختلفان: J لها36 خانة1، وI لها ست خانات1 فقط.

إذا حسبنا W=J−M فنحن نطرح كل خانة من1. خارج القطر نحصل على النتيجة المطلوبة: الحافة الأصلية ذات1 تصبح0، والوصلة الغائبة ذات0 تصبح1. لكن على القطر كان M يملك0، فيصبح كل موضع قطري في W مساويًا1.

هذه الواحدات الست تصف AA وBB وCC وDD وEE وFF. لذلك الناتج لا يمثل المتمم البسيط المطلوب؛ أدخل ست حلقات ذاتية. ليست المشكلة في ترتيب الصفوف أو جمع الحواف مرتين، بل في تطبيق القلب على أزواج استبعدناها من البداية.

نطرح I لتصحيح تلك المواضع فقط: C=J−I−M. على القطر نحسب1−1−0=0، وخارجه تكون خانة I صفرًا، فنحصل على1−0−M. وهكذا تبقى عملية القلب كما نريد خارج القطر ويزول أثرها غير المرغوب على القطر.

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

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

الدرجات والمتمم الثاني يفحصان النتيجة

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

نحصل على درجات المتمم (4,3,3,3,3,4). كل درجتين للرأس نفسه في الرسمين تجمعان إلى5: درجة A الأصلية1 ودرجة A في المتمم4، ودرجة C الأصلية2 ودرجته الجديدة3. لا نقارن درجة A بدرجة رأس آخر لمجرد تشابه الرقم.

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

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

لو أخذنا متمم الرسم الصحيح مرة ثانية، فسنعيد AB وBC وCD وDE وEF ونزيل الحواف العشر الأخرى. لكل زوج خارج القطر، القلب مرتين يعيد الخانة الأولى:1−(1−x)=x. وعلى القطر نثبت0 في المرحلتين.

يمكن مراجعة ذلك أيضًا بالرموز: J−I−(J−I−M)=M. لا نستنتج صحة عملية ما من رجوعها مرتين وحده؛ فالقلب الشامل الخاطئ يرجع مرتين أيضًا لكنه يدخل حلقات في المرحلة الوسطى. يجب فحص نوع الرسم والقطر إلى جانب خاصية الرجوع.

فحص محدد ثم برهان الخانة الواحدة

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

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

في كل مدخل اختبرنا أن القطر يبقى صفرًا، وأن مجموع درجتي الرأس في الأصل والمتمم يساوي4، وأن المتمم الثاني يعيد المصفوفة الأولى. كما طابقت أعداد الحواف العلاقة: العدد الأصلي مع عدد المتمم يساوي10 للأزواج الممكنة بين الرؤوس الخمسة.

لا ندعي أن هذا الاختبار حصر جميع32768 رسمًا على ستة رؤوس. المثال الرئيس ستة رؤوس، والفحص الشامل الإضافي خمسة. أما حجة الخانة الواحدة فتبين السبب مباشرة: خارج القطر نقلب1 و0، وعلى القطر نحافظ على0 وفق تعريف المدخل.

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

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