ضم رسمين: هل نعيد استعمال ألوان الاتحاد؟

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

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

• ضم رسمين لهما مجموعتا رؤوس منفصلتان يتكون من اتحادهما مع كل الحواف التي تصل مجموعة بالأخرى. [1] سنعمل على رسوم بسيطة غير موجهة وبلا حلقات، وتكون مجموعتا الأسماء غير فارغتين.
• اتحاد AB BC مع DE يضم خمسة رؤوس وثلاث حواف ويحتاج2؛ يمكن أن يشترك A وC وD في لون واحد لأن D ليس جارًا لهما في الاتحاد.
• الضم يضيف AD AE BD BE CD CE ويبقي الحواف الأصلية؛ يصبح العدد9، والدرجات (3,4,3,4,4). لا تضاف AC داخل العامل الأول.
• في الضم تتباعد مجموعتا الألوان: كل رأس من الأولى جار لكل رأس من الثانية. لذلك الأقل a+b، ويمكن بلوغه بتلوين العاملين بألوان منفصلة؛ في الاتحاد المنفصل الأقل max(a,b).
• ضم عاملين بلا حواف على2 و3 رؤوس يعطي K2,3 بلونين، لا كاملًا على خمسة. وضم حافتين يعطي K4 بأربعة ألوان؛ الحواف الداخلية هي التي تفرق المثالين.
• المثلث مع رأس منفصل يحتاج3 في الاتحاد، ثم4 بعد الضم؛ المعزول القديم يتصل بكل رأس من العامل الآخر غير الفارغ. القاعدة هنا للرؤوس، لا لألوان الحواف.
• راجعنا80 زوجًا من عاملين صغيرين،64 لثلاثة مع ثلاثة و16 لثلاثة مع اثنين، ببحث عن أقل تلوين وفحص الحواف والدرجات. لا يشمل ذلك كل الأحجام أو أداء برامج.

الضم يحفظ العاملين ويضيف كل الحواف العابرة

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

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

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

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

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

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

ثلاث حواف في الاتحاد، ولونان يكفيان

نضع في الجهة الأولى مسارًا برؤوس A وB وC وحواف AB وBC. وفي الثانية رأسين D وE وحافة DE. المجموعتان منفصلتان، ولا توجد حافة من A أوB أوC إلى D أوE في الاتحاد.

لدينا خمسة رؤوس وثلاث حواف. نعطي A وC لونًا أزرق وB أحمر. وفي الجهة الأخرى نعيد استعمال الأزرق عند D والأحمر عند E. طرفا كل من AB وBC وDE مختلفان، فهذا تلوين صحيح بلونين.

وجود AB يمنع لونًا واحدًا؛ إذن أقل عدد للاتحاد2. كذلك يحتاج المسار نفسه2 لأن فيه حافة ويقبل تناوب اللونين، وتحتاج DE العدد نفسه. لم نجمع2 و2 لأننا نستطيع إعادة استعمال مجموعتي الألوان.

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

درجات الرؤوس في ترتيب A B C D E هي (1,2,1,1,1). مجموعها6، وهو ضعفا عدد الحواف3. هذه الدرجات تخص الاتحاد قبل إضافة الوصلات العابرة؛ سنراجعها ثانية في الناتج.

الحواف الست العابرة تمنع مشاركة اللون

نضم العاملين نفسيهما. نحتفظ بـAB وBC وDE، ونضيف AD وAE وBD وBE وCD وCE. هذه ست حواف عابرة: ثلاثة اختيارات من الأولى مضروبة في اختيارين من الثانية. يصبح العدد الكلي9، والرؤوس ما زالت خمسة.

لا يجوز الآن أن يشترك D مع A أوB أوC في لون، لأن D متصل بكل واحد منها. وينطبق الأمر على E. كما لا يجوز أن يتشارك D وE لونًا، لأن DE من الحواف الأصلية الباقية.

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

ولمنع ثلاثة، انظر إلى الرؤوس A وB وD وE فقط. الحواف AB وDE موجودتان، والحواف AD وAE وBD وBE أضيفت بالضم. كل زوج من هذه الأربعة متجاور؛ تحتاج أربعة ألوان مختلفة. يجتمع الحد الأدنى4 مع التلوين الذي يبلغه.

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

درجة كل رأس من المسار تزيد2، لأننا وصلناه برأسي الجهة الثانية. ودرجة D وE تزيد3. الدرجات النهائية (3,4,3,4,4)، ومجموعها18، وهو ضعفا الحواف9. الصورة الرئيسية تميز الحواف الأصلية من الست المضافة.

لماذا نجمع العددين في الضم ونأخذ الأكبر في الاتحاد؟

لتكن أقل ألوان العامل الأول a، والثاني b. في أي تلوين صحيح لضمّهما، لا يمكن أن يظهر لون واحد في الجهتين: أي رأسين من جهتين مختلفتين متجاوران. لذلك مجموعتا الألوان المستعملتان منفصلتان.

كل جهة ما زالت تحتوي رسمها الأصلي بكل حوافه، فلا تستطيع استعمال أقل من عددها الأدنى. تحتاج الأولى على الأقل a، والثانية على الأقل b، وبسبب انفصال الألوان يحتاج الناتج على الأقل a+b.

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

في الاتحاد المنفصل لا توجد حواف عابرة، فيمكن إعادة تسمية ألوان الجهة الأصغر لتستعمل من ألوان الأكبر. هكذا يكفي max(a,b). ولا يكفي أقل منه لأن الجهة التي تحتاج العدد الأكبر تحتفظ بحوافها؛ إذن هذا هو العدد الأدنى للاتحاد.

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

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

رأسان بلا حواف مع ثلاثة لا يصنعان كاملًا على خمسة

للتأكد من أن الضم ليس جعل كل الرؤوس متجاورة، نأخذ عاملًا بلا حواف على A وB، وآخر بلا حواف على C وD وE. يحتاج كل عامل غير فارغ لونًا واحدًا، لأن لا حافة تمنع مشاركة اللون داخله.

اتحادهما خمسة رؤوس بلا حواف، فيكفي لون واحد. ضمهما يضيف AC وAD وAE وBC وBD وBE فقط. نعطي A وB الأزرق، وC وD وE الأحمر؛ كل حافة تصل لونين مختلفين، ووجود AC يمنع الواحد. الناتج يحتاج2، لا5.

لا توجد AB أوCD أوCE أوDE في هذا الناتج، فهو الكامل ثنائي التجزئة K2,3، وليس الكامل على خمسة. عبارة كل الحواف في تعريف الضم تخص الأزواج العابرة بين العاملين، ولا تلغي غياب الحواف الداخلية.

كضبط آخر، ابدأ بحافة AB وحافة CD في مجموعتين. اتحادهما يحتاج2، لكن الضم يحتفظ بهما ويضيف AC وAD وBC وBD. صار لدينا الكامل على أربعة بست حواف؛ كل رأسين متجاوران فيحتاج4. الفرق هو حواف العاملين التي كانت غائبة في المثال السابق.

وأخيرًا خذ مثلث ABC ورأسًا منفصلًا D. في الاتحاد يمكن إعطاء D أحد ألوان المثلث، فيبقى الأقل3. بعد الضم نضيف AD وBD وCD؛ يصبح D جارًا للجميع ويحتاج لونًا رابعًا، والناتج كامل على أربعة.

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

عدد الحواف والدرجات، وما راجعه الفحص

عدد الحواف النهائي يساوي حواف العامل الأول زائد حواف الثاني زائد n×m. لا نكرر حافة عابرة في اتجاهين، لأن الرسم غير موجه. ويزيد عدد جيران رأس في الأولى بمقدار m، وفي الثانية بمقدار n.

راجعنا جميع64 زوجًا من رسوم مسماة على ثلاثة رؤوس في كل عامل: لكل عامل8 قوائم حواف، فيكون العدد8×8=64. وأضفنا جميع16 زوجًا عندما يكون الأول على ثلاثة والثاني على رأسين:8×2=16. المجموع80 زوجًا، وليس80 نوعًا بعد حذف إعادة الأسماء.

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

هذا فحص محدود لأحجام معينة، لا تعداد لجميع الرسوم أو قياس لسرعة خوارزمية. الحجة عن فصل الألوان وتعويض تسمياتها تشرح القاعدة العامة في النموذج المحدد؛ لا نستبدلها بمجرد نجاح80 تجربة.

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

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