مقالات

5.4: الرسوم البيانية ثنائية الأجزاء - الرياضيات


لقد رأينا بالفعل كيف تنشأ الرسوم البيانية ثنائية الأجزاء بشكل طبيعي في بعض الظروف. هنا نستكشف الرسوم البيانية ثنائية الأجزاء أكثر قليلاً.

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

التعريف: المسافة بين الرؤوس

المسافة بين القمم (v ) و (w ) ، ( d (v ، w) ) ، هي طول أقصر مسافة بين الاثنين. إذا لم يكن هناك سير بين (v ) و (ث ) ، تكون المسافة غير محددة.

نظرية 5.4.2

(G ) ثنائي إذا وفقط إذا كانت جميع الممرات المغلقة في (G ) متساوية الطول.

دليل

الاتجاه إلى الأمام سهل ، كما نوقش أعلاه.

افترض الآن أن جميع مناحي مغلقة لها أطوال متساوية. قد نفترض أن (G ) متصل ؛ إذا لم يكن الأمر كذلك ، فإننا نتعامل مع كل مكون متصل بشكل منفصل.

لنفترض أن (v ) هو رأس (G ) ، وليكن (X ) مجموعة من جميع الرؤوس على مسافة متساوية من (v ) ، و (Y ) تكون مجموعة الرؤوس عند مسافة فردية من (v ). ندعي أن جميع حواف (G ) تربط رأس (X ) برأس (Y ). افترض لا ؛ ثم هناك نقاط متجاورة (u ) و (ث ) بحيث يكون ( د (ت ، ش) ) و ( د (ت ، ث) ) نفس التكافؤ. ثم هناك مسيرة مغلقة من (v ) إلى (u ) إلى (w ) إلى (v ) بطول ( d (v ، u) +1+ d (v، w ) ) وهو أمر غريب وهو تناقض.

(ميدان)

المسيرة المغلقة التي توفر التناقض ليست بالضرورة دورة ، ولكن يمكن علاج ذلك ، مما يوفر نسخة مختلفة قليلاً من النظرية.

النتيجة الطبيعية 5.4.3

(G ) ثنائي إذا وفقط إذا كانت جميع الدورات في (G ) متساوية الطول.

دليل

مرة أخرى ، الاتجاه الأمامي سهل ، ومرة ​​أخرى نفترض أن (G ) متصل. كما في السابق ، لنكن (v ) رأس (G ) ، دع (X ) يكون مجموعة من جميع الرؤوس على مسافة متساوية من (v ) ، و (Y ) تكون المجموعة من القمم على مسافة فردية من (v ). إذا كان رأسان في (X ) متجاورين ، أو إذا كان هناك رأسان متجاوران في (Y ) ، فكما في الإثبات السابق ، هناك مسار مغلق بطول فردي.

لإنهاء الإثبات ، يكفي إظهار أنه إذا كان هناك مسيرة مغلقة بطول فردي ، فهناك دورة ذات طول فردي. والدليل بالاستقراء على طول المسيرة المغلقة.

إذا لم يكن لدى (W ) رؤوس متكررة ، فقد انتهينا. خلاف ذلك ، افترض أن المشي مغلق

$$ v = v_1 ، e_1 ، ldots ، v_i = v ، ldots ، v_k = v = v_1. $$

ثم

$$ v = v_1 ، ldots ، v_i = v quad hbox {and} quad v = v_i ، e_i ، v_ {i + 1} ، ldots ، v_k = v $$

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

(ميدان)

غالبًا ما يكون من المفيد النظر في خصائص الرسم البياني في السياق المحدود للرسوم البيانية ثنائية الأجزاء (أو أنواع خاصة أخرى من الرسم البياني). على سبيل المثال ، ماذا يمكننا أن نقول عن دورات هاملتون في رسوم بيانية بسيطة ثنائية الأجزاء؟ افترض أن قسم رؤوس الرسم البياني الثنائي هو (X ) و (Y ). نظرًا لأن أي دورة تتناوب بين رؤوس جزأين من الرسم البياني ثنائي الجزء ، إذا كانت هناك دورة هاميلتون إذن (| X | = | Y | ge2 ). في مثل هذه الحالة ، تكون درجة كل رأس على الأكثر (n / 2 ) ، حيث (n ) هو عدد الرؤوس ، أي (n = | X | + | Y | ). وبالتالي فإن حالة الركاز () d (v) + d (w) ge n ) عندما (v ) و (w ) غير متجاورتين) تكافئ ( d (v) = n / 2 ) للجميع (v ). هذا يعني أن الرسم البياني البسيط الوحيد الثنائي الذي يفي بشرط الركاز هو الرسم البياني الكامل من جزئين (K_ {n / 2، n / 2} ) ، حيث يكون للجزئين الحجم (n / 2 ) ويكون كل رأس (X ) مجاورًا لكل رأس (Y ). المحصلة هي أن خاصية Ore لا تقدم معلومات مثيرة للاهتمام حول الرسوم البيانية ثنائية الأجزاء.

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

نلاحظ ، بشكل عام ، أن الرسم البياني الكامل ثنائي الأجزاء (K_ {m ، n} ) هو رسم بياني ثنائي مع (| X | = م ) ، (| Y | = n ) ، وكل رأس من (X ) مجاور لكل رأس من (Y ). الرسوم البيانية الوحيدة مع دورات هاميلتون هي تلك التي (م = ن ).


شاهد الفيديو: الرسم البياني للخط المستقيم الصف الثامن. كامبريدج. easy math. الاستاذ أحمد دسوقي (ديسمبر 2021).