رسم الحواف: هل يعيد المثلث الناتج أصلًا واحدًا؟

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

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

• في رسم الحواف، تقابل كل حافة أصلية رأسًا جديدًا، ويتجاور رأسان جديدان عندما تشترك حافتاهما في طرف. [1] نعمل برسوم بسيطة غير موجهة؛ هذا تحويل لشبكة، لا مخطط خطي لبيانات زمنية.
• التطابق المعروف بين ناتجي المثلث والنجمة الثلاثية مذكور في المرجع. [1] في قوائمنا، e1 وe2 وe3 تتجاور كلها زوجيًا، لكن الأصلين لهما ثلاثة رؤوس وأربعة رؤوس على الترتيب.
• في المثلث، نقاط اشتراك أزواج الحواف هي B وA وC؛ لا رأس يجمع الحواف الثلاث. في النجمة تشترك الأزواج كلها في A، وهو طرف مشترك للجميع؛ الناتج يسجل الاشتراك الزوجي فقط.
• إضافة D معزولًا إلى المثلث لا تضيف رأسًا في الناتج، لأن D لا يدخل حافة. هذا الأصل والنجمة لهما أربعة رؤوس وثلاث حواف، وناتجاهما متطابقان، لكن الأول غير متصل والثاني متصل.
• المسار AB BC CD يعطي رؤوس الناتج e1 وe2 وe3 بحافتي e1–e2 وe2–e3 فقط. لا تتجاور e1 وe3 لأن AB وCD لا تشتركان في طرف؛ الناتج ليس مثلثًا. ودرجة الرأس الذي يمثل uv هي d(u)+d(v)−2 في الرسم البسيط.
• فحصنا جميع75 رسمًا مسمى على واحد إلى أربعة رؤوس. منها44 متصلًا تمثل10 أنواع بنيوية، وتعطي9 أنواع ناتجة؛ التصادم الوحيد في هذا النطاق هو زوج المثلث والنجمة. وراجعنا205 حالات لهوية درجة رأس الناتج.

الحافة الأصلية تصبح رأسًا جديدًا

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

نثبت مجموعة الرؤوس وقائمة الحواف قبل التحويل. نسمي الحواف بحسب ترتيب القائمة e1 وe2 وe3، لا بحسب مكان الخط في الصورة. ثم ننشئ رأسًا جديدًا يحمل اسم كل حافة؛ أسماء رؤوس الأصل مثل A وB لا تصبح تلقائيًا رؤوسًا في الناتج.

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

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

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

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

مثلث ونجمة يعطيان القائمة نفسها

للمثلث رؤوس A B C وحواف مرتبة AB ثم BC ثم AC. إذن e1 تمثل AB، وe2 تمثل BC، وe3 تمثل AC. رؤوس الأصل الثلاثة درجاتها2، والحواف الثلاث تصل بينها جميع الأزواج.

AB وBC تشتركان في B، فتوجد الحافة e1–e2 في الناتج. AB وAC تشتركان في A، فتوجد e1–e3. BC وAC تشتركان في C، فتوجد e2–e3. بذلك يعطينا التحويل مثلثًا على رؤوس e1 وe2 وe3.

أما النجمة فرؤوسها A B C D، وحوافها المرتبة AB ثم AC ثم AD. A هو المركز، وكل من B وC وD ورقة متصلة بالمركز فقط. الدرجات (3,1,1,1)، ولا توجد حواف بين الأوراق.

هنا أيضًا تتجاور e1 مع e2، وe1 مع e3، وe2 مع e3: كل زوج من الحواف الأصلية يلتقي في A. قائمة تجاور الناتج هي نفسها التي حسبناها للمثلث، رغم اختلاف عدد رؤوس الأصل وقائمة درجاته.

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

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

الاشتراك الزوجي لا يثبت طرفًا للجميع

الفرق الذي أخفاه الناتج يظهر عندما نسأل عن الطرف المشترك لكل الحواف معًا. في المثلث، مجموعة أطراف e1 هي {A,B}، وأطراف e2 هي {B,C}، وأطراف e3 هي {A,C}. تقاطع الثلاث فارغ.

ومع ذلك، تقاطع أطراف e1 وe2 وحدهما هو {B}، وتقاطع e1 وe3 هو {A}، وتقاطع e2 وe3 هو {C}. كل زوج يجد طرفًا، لكن الطرف يختلف من زوج إلى آخر. لهذا يكون الناتج كامل التجاور بين رؤوسه الثلاثة.

في النجمة، المجموعات هي {A,B} و{A,C} و{A,D}. جميع التقاطعات الزوجية هي {A}، وتقاطع المجموعات الثلاث هو {A} أيضًا. يوجد في هذا الأصل رأس واحد يضم الحواف كلها.

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

لا يعني هذا أن التحويل يفقد كل معلومات الأصل. فهو يحتفظ، مثلًا، بأن الحافتين AB وBC تلتقيان في المثال الأول. لكنه لا يرفق اسم B تلقائيًا بالحافة e1–e2، ولا يميز بهذه الحافة وحدها مصدر الالتقاء عن حالة المركز المشترك.

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

الرأس المعزول يختفي دون تغيير الناتج

نضيف الآن D إلى مجموعة رؤوس المثلث، ونبقي الحواف AB وBC وAC فقط. لا يتصل D بأي رأس، فتكون درجته0. الأصل الجديد له أربعة رؤوس وثلاث حواف، ودرجاته (2,2,2,0).

قائمة الحواف لم تتغير، لذلك لا تتغير أسماء رؤوس الناتج ولا أزواج التجاور بينها. ما زلنا نحصل على المثلث e1–e2 وe1–e3 وe2–e3. لا يظهر رأس جديد يمثل D، لأنه ليس حافة أصلية.

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

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

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

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

المسار يضبط قاعدة التجاور والدرجة

للمسار المقارن رؤوس A B C D وحواف مرتبة AB ثم BC ثم CD. درجات الأصل (1,2,2,1). e1 وe2 تتجاوران لأن AB وBC تلتقيان في B، وe2 وe3 تتجاوران لأن BC وCD تلتقيان في C.

أما AB وCD فمجموعتا أطرافهما منفصلتان. لذلك لا توجد حافة e1–e3، ويكون الناتج مسارًا من ثلاثة رؤوس وحافتين، بدرجات (1,2,1). تساوي عدد الحواف الأصلية3 مع حواف الأمثلة السابقة لا يجبر ناتجًا مثلثًا.

يمكن مراجعة الدرجة دون بناء المصفوفة كلها. للحافة uv في رسم بسيط، عدد الحواف الأخرى عند u هو d(u)−1، وعند v هو d(v)−1. المجموعتان منفصلتان: لا حافة مختلفة تصل u وv مرة أخرى في مدخل بسيط.

إذن درجة الرأس الذي يمثل uv في الناتج هي d(u)+d(v)−2. في وسط المسار، BC لها طرفان بدرجة2، فتكون درجة e2 هي2. وعند AB نجد1+2−2=1، وكذلك عند CD؛ تطابق هذه الحسابات درجات الناتج المحسوب من الأزواج.

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

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

حصر محدود وشروط القراءة العكسية

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

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

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

كما راجعنا هوية d(u)+d(v)−2 لكل حافة في المدخلات75، فكانت205 حالات صحيحة. هذا عدد حالات الحواف، وليس205 رسومًا أو أنواعًا. وتبقى المراجعة محدودة بالرؤوس من واحد إلى أربعة؛ لا تثبت وحدها حكمًا لكل أحجام الرسوم.

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

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