مبرهنة منغر: مساران بلا حافة مشتركة قد يمران بالرأس نفسه

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

لأن عدم مشاركة الحواف لا يمنع المرور بنقطة مشتركة. المساران P₁=A→x→V→y→B وP₂=A→u→V→w→B مختلفان في حوافهما كلها، لكن V رأس داخلي في كليهما. في مثالنا أكبر عدد بلا حافة مشتركة2، وأكبر عدد بلا رأس داخلي مشترك1؛ حذف V يقطع الاتصال بين A وB.

• نثبت A وB طرفين غير متجاورين، ونرسم الحواف Ax وxV وVy وyB وAu وuV وVw وwB. لا أسهم ولا أوزان؛ الرؤوس السبعة مختلفة، والمسار البسيط لا يكرر رأسًا في قائمته.
• P₁ يستخدم {Ax,xV,Vy,yB}، وP₂ يستخدم {Au,uV,Vw,wB}. لا حافة في المجموعتين معًا. لكن مجموعة الرؤوس الداخلية للأول {x,V,y} وللثاني {u,V,w}، وتقاطعها {V}. مشاركة الطرفين A وB مسموحة في المقارنة الداخلية.
• لدينا مساران بلا حافة مشتركة، ولا يمكن ثلاثة؛ كل مسار يبدأ من A على Ax أوAu، وأي مسارين يستعملان الحافة الأولى نفسها يتشاركان حافة. إذن الحد الأقصى2.
• كل مسار من A إلى B يمر بـV، لذلك لا يوجد زوج دون رأس داخلي مشترك. يوجد مسار واحد، فيكون الحد الأقصى1. المجموعة S={V} تفصل الطرفين؛ حذف A أوB ممنوع في اختبار فصل الرؤوس هنا.
• الحافتان T={Ax,Au} تعزلان A بعد حذفهما. وحافة واحدة لا تقطع المسارين P₁ وP₂ معًا لأنهما لا يشتركان في حافة. إذن أقل عدد من الحواف اللازمة للفصل2، رغم أن أقل عدد من الرؤوس1.
• مساواة منغر بين عدد المسارات الداخلية المستقلة وأقل فاصل من الرؤوس تخص وحدة العد نفسها. [1] لا نستبدل الرؤوس بالحواف في طرف واحد من المقارنة. مثالنا عن اتصال A بـB، ولا يطلب زيارة كل الرؤوس أو اختيار مطابقة.

حدد الطرفين ونوع المشاركة الممنوعة

لدينا سبعة رؤوس: A وB وV وx وu وy وw. نثبت A بداية وB نهاية؛ لا توجد حافة AB. حروف x وu وy وw الصغيرة أسماء رؤوس، وليست متغيرات نبدل قيمها أثناء القراءة.

الحواف الثماني كلها هي Ax وxV وVy وyB وAu وuV وVw وwB. الحافة غير موجهة، لذلك Ax وxA اسمان للاتصال نفسه. الرسم بلا حلقات ذاتية أو حواف مكررة؛ تقاطع خطوط الصفحة لا يضيف رأسًا.

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

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

قارن الحواف ثم الرؤوس الداخلية

نختار P₁=A→x→V→y→B وP₂=A→u→V→w→B. كل قائمة مسار بسيط من أربعة انتقالات؛ لا يتكرر رأس داخل أي قائمة، وكل انتقال من الحواف الثماني المحددة.

حواف P₁ هي {Ax,xV,Vy,yB}، وحواف P₂ هي {Au,uV,Vw,wB}. لا يظهر اسم حافة في المجموعتين معًا حتى بعد اعتبار الاتجاه المعكوس اسمًا للحافة نفسها. لذلك المساران بلا حافة مشتركة.

الرؤوس الداخلية للأول {x,V,y}، وللثاني {u,V,w}. يشتركان في V. لا ننقذ الادعاء بالقول إن الدخول إلى V من x يختلف عن الدخول إليه من u؛ ما نمنعه في هذا الشرط هو تكرر الرأس نفسه بين المسارين.

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

في اللوحة اليمنى من الصورة الرئيسية، الأخضر لحواف P₁ والذهب لحواف P₂، ولون V المختلف يبرز الرأس الداخلي المشترك. لا توجد حافة تجمع اللونين في هذا الرسم.

لماذا أكبر عدد بلا حافة مشتركة2؟

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

للرأس A حافتان فقط هما Ax وAu. كل مسار من A إلى B يبدأ بإحداهما. لو اخترنا ثلاثة مسارات، لاضطر اثنان منها إلى الحافة الأولى نفسها، فيفشل شرط عدم مشاركة الحواف.

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

يمكن أيضًا اختيار A→x→V→w→B وA→u→V→y→B؛ حوافهما غير مشتركة، ويشتركان في V أيضًا. المثال لا يدعي أن الزوج الأول هو الاختيار الوحيد.

كل المسارات تمر بـV، وفاصل الرؤوس حجمه1

إذا حذفنا V وحوافه المتصلة به، بقيت الحافتان Ax وAu في جهة A، وبقيت yB وwB في جهة B. لا توجد حافة بين الجهتين؛ المكون الأول رؤوسه {A,x,u} والثاني {B,y,w}.

هذا يكشف أن كل مسار من A إلى B في الأصل يحتاج V. لذلك أي مسارين بين الطرفين يتشاركان هذا الرأس الداخلي، فلا يمكن اختيار زوج دون مشاركة رأس داخلي.

يوجد مسار واحد مثل P₁، ومن ثم أكبر عدد من المسارات التي لا تتشارك داخليًا هو1، وليس0. المجموعة S={V} تفصل بين A وB، فيكون أقل عدد مطلوب من الرؤوس على الأكثر1.

لا يمكن فاصل من صفر رؤوس، لأن الطرفين متصلان في الرسم الأصلي. إذن أقل عدد1 بالضبط. نمنع حذف A أوB من الفاصل؛ إزالة الطرف نفسه ليست اختبارًا للمسارات بين طرفين باقين.

تقرر صيغة منغر لرأسين غير متجاورين مساواة أقل عدد من الرؤوس الفاصلة بأكبر عدد من المسارات المستقلة في رؤوسها الداخلية. [1] شاهد المسار وفاصل V يوضحان العدد1 هنا؛ المثال لا يبرهن المبرهنة لكل رسم.

قطع حافتين يختلف عن حذف رأس واحد

نعود إلى الرسم الأصلي، ونحذف Ax وAu فقط، مع إبقاء جميع الرؤوس. يصبح A معزولًا، فلا مسار منه إلى B. المجموعة T={Ax,Au} فاصل من حافتين، وليست مجموعة من رأسين.

هل تكفي حافة واحدة؟ خذ أي حافة وحاول حذفها. لا تستطيع أن تنتمي إلى P₁ وP₂ معًا، لأن حوافهما غير مشتركة. لذلك يبقى أحد المسارين كاملًا، ويظل A متصلًا بـB.

إذن أقل عدد من الحواف للفصل لا يقل عن2. والفاصل المعروض ذو الحافتين يحقق2، فيثبت أقل عدد. هذا البرهان عن الرسم المحدد، ويعد الحواف بدل الرؤوس.

عند حذف V نزيل معه أربع حواف: xV وVy وuV وVw. لا نعد العملية حذف حافة واحدة لمجرد أننا اخترنا اسمًا واحدًا V؛ وحدة العد في ذلك الفحص رأس، وفي فحص T حافة.

يلخص الجدول العددين ووحدة كل منهما. الصورة الداخلية تعرض نتيجتي الحذف من الرسم الأصلي نفسه: حذف V يترك مكونين من ثلاثة رؤوس، وحذف Ax وAu يبقي V ويعزل A.

لا تخلط اختبار المسارات بمسألة أخرى

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

في مثالنا توجد أربعة مسارات بسيطة من A إلى B: نختار x أوu قبل V، ثم y أوw بعده. جميعها تمر بـV. تغيير اختيار الفرع لا يزيل هذا الرأس، حتى عندما يجعل حواف مسارين مختلفة بالكامل.

لا نطلب أن يزور المسار كل رأس في الرسم؛ P₁ لا يزور u أوw. ولا نختار حواف مطابقة لا تتلاقى داخل المسار، لأن الحواف المتتالية تلتقي في الرأس الوسيط عمدًا. موضوعنا عدد مسارات مستقلة بين طرفين مثبتين.

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

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