رسم بياني ثنائي الأجزاء

يمكن وصف الرسوم البيانية ثنائية الأجزاء بعدة طرق مختلفة:

• يكون الرسم البياني غير الموجه ثنائي الأجزاء إذا وفقط إذا لم يحتوي على دورة فردية . ^{[ 13 ] [ 14 ]}
• يكون الرسم البياني ثنائي الأجزاء إذا وفقط إذا كان قابلاً للتلوين بلونين (أي أن عدده اللوني أقل من أو يساوي 2). ^{[ 3 ]}
• يكون الرسم البياني ثنائي الأجزاء إذا وفقط إذا كان كل ضلع ينتمي إلى عدد فردي من الروابط ، وهي مجموعات فرعية دنيا من الأضلاع التي يؤدي حذفها إلى زيادة عدد مكونات الرسم البياني. ^{[ 15 ]}
• يكون الرسم البياني ثنائي الأجزاء إذا وفقط إذا كان طيف الرسم البياني متناظرًا. ^{[ 16 ]}

في الرسوم البيانية ثنائية الأجزاء، يساوي حجم غطاء الرؤوس الأدنى حجم المطابقة القصوى ؛ وهذا ما يُعرف بنظرية كونيغ . ^{[ 17 ] [ 18 ]} وهناك صيغة بديلة ومكافئة لهذه النظرية، وهي أن مجموع حجم المجموعة المستقلة القصوى وحجم المطابقة القصوى يساوي عدد الرؤوس. في أي رسم بياني لا يحتوي على رؤوس معزولة، يساوي مجموع حجم غطاء الحواف الأدنى وحجم المطابقة القصوى عدد الرؤوس. ^{[ 19 ]} وبدمج هذه المساواة مع نظرية كونيغ، نستنتج أنه في الرسوم البيانية ثنائية الأجزاء، يساوي حجم غطاء الحواف الأدنى حجم المجموعة المستقلة القصوى، ويساوي مجموع حجم غطاء الحواف الأدنى وحجم غطاء الرؤوس الأدنى عدد الرؤوس.

تتعلق فئة أخرى من النتائج ذات الصلة بالرسوم البيانية الكاملة : كل رسم بياني ثنائي الأجزاء، ومكمل كل رسم بياني ثنائي الأجزاء، والرسم البياني الخطي لكل رسم بياني ثنائي الأجزاء، ومكمل الرسم البياني الخطي لكل رسم بياني ثنائي الأجزاء، كلها كاملة. من السهل إثبات كمال الرسوم البيانية ثنائية الأجزاء ( عددها اللوني اثنان، وحجم زمرتها القصوى اثنان أيضًا)، لكن كمال مكملات الرسوم البيانية ثنائية الأجزاء أقل وضوحًا، وهو إعادة صياغة أخرى لنظرية كونيغ. كانت هذه إحدى النتائج التي حفزت التعريف الأولي للرسوم البيانية الكاملة. ^{[ 20 ]} كمال مكملات الرسوم البيانية الخطية للرسوم البيانية الكاملة هو إعادة صياغة أخرى لنظرية كونيغ، وكمال الرسوم البيانية الخطية نفسها هو إعادة صياغة لنظرية سابقة لكونيغ، مفادها أن كل رسم بياني ثنائي الأجزاء له تلوين حواف باستخدام عدد من الألوان يساوي درجته القصوى.

وفقًا لنظرية الرسم البياني الكامل القوي ، تتميز الرسوم البيانية الكاملة بخصائص رسوم بيانية محظورة تُشبه تلك الخاصة بالرسوم البيانية ثنائية الأجزاء: يكون الرسم البياني ثنائي الأجزاء إذا وفقط إذا لم يكن لديه دورة فردية كرسم بياني فرعي، ويكون الرسم البياني كاملًا إذا وفقط إذا لم يكن لديه دورة فردية أو مكملها كرسم بياني فرعي مُستحث . تُشكل الرسوم البيانية ثنائية الأجزاء، والرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء، ومكملاتها، أربعة من الفئات الخمس الأساسية للرسوم البيانية الكاملة المستخدمة في برهان نظرية الرسم البياني الكامل القوي. ^{[ 21 ]} ويترتب على ذلك أن أي رسم بياني فرعي من رسم بياني ثنائي الأجزاء هو أيضًا ثنائي الأجزاء لأنه لا يمكن أن يكتسب دورة فردية. ^{[ 22 ]}

بالنسبة للرأس، يُطلق على عدد الرؤوس المجاورة درجة الرأس ويُرمز لها بـ${\displaystyle \deg v}$تنص صيغة مجموع الدرجات للرسم البياني ثنائي الأجزاء على أن ^{[ 23 ]}

${\displaystyle \sum _{v\in V}\deg v=\sum _{u\in U}\deg u=|E|\,.}$

تسلسل درجات الرسم البياني ثنائي الأجزاء هو زوج من القوائم، تحتوي كل منها على درجات الجزأين.${\displaystyle U}$و${\displaystyle V}$على سبيل المثال، يحتوي الرسم البياني الثنائي الكامل K _3,5 على تسلسل درجات${\displaystyle (5,5,5),(3,3,3,3,3)}$تتشابه الرسوم البيانية الثنائية المتماثلة في تسلسل الدرجات. ومع ذلك ، فإن تسلسل الدرجات لا يُحدد، بشكل عام، الرسم البياني الثنائي بشكل فريد؛ ففي بعض الحالات، قد تتشابه الرسوم البيانية الثنائية غير المتماثلة في تسلسل الدرجات.

تُعرف مسألة تحقيق الرسم البياني الثنائي بأنها مسألة إيجاد رسم بياني ثنائي بسيط تكون فيه متتالية الدرجات عبارة عن قائمتين معطيتين من الأعداد الطبيعية. (يمكن تجاهل الأصفار اللاحقة لأنه من السهل تحقيقها بإضافة عدد مناسب من الرؤوس المعزولة إلى الرسم البياني الموجه).

مصفوفة التجاور الثنائي للرسم البياني ثنائي الأجزاء${\displaystyle (U,V,E)}$هي مصفوفة (0,1) بحجم${\displaystyle |U|\times |V|}$تحتوي هذه المصفوفة على قيمة واحد لكل زوج من الرؤوس المتجاورة وقيمة صفر للرؤوس غير المتجاورة. ^{[ 24 ]} يمكن استخدام مصفوفات التجاور الثنائي لوصف التكافؤ بين الرسوم البيانية ثنائية الأجزاء، والرسوم البيانية الفائقة، والرسوم البيانية الموجهة.

الرسم البياني الفائق هو بنية تركيبية، مثل الرسم البياني غير الموجه، لها رؤوس وحواف، ولكن قد تكون الحواف مجموعات عشوائية من الرؤوس بدلاً من أن يكون لها نقطتا نهاية فقط. الرسم البياني ثنائي الأجزاء${\displaystyle (U,V,E)}$يمكن استخدام هذا النموذج لنمذجة مخطط فائق حيث U هي مجموعة رؤوس المخطط الفائق، وV هي مجموعة حواف المخطط الفائق، و E تحتوي على حافة من رأس المخطط الفائق v إلى حافة المخطط الفائق e تحديدًا عندما يكون v أحد طرفي e . وبموجب هذا التناظر، فإن مصفوفات التجاور الثنائي للمخططات ثنائية الأجزاء هي نفسها مصفوفات الوقوع للمخططات الفائقة المقابلة. وكحالة خاصة من هذا التناظر بين المخططات ثنائية الأجزاء والمخططات الفائقة، يمكن تفسير أي مخطط متعدد (مخطط قد توجد فيه حافتان أو أكثر بين نفس الرأسين) على أنه مخطط فائق تكون فيه بعض حواف المخطط الفائق لها مجموعات متساوية من الأطراف، ويتم تمثيله بمخطط ثنائي الأجزاء لا يحتوي على تجاورات متعددة وتكون فيه جميع الرؤوس على أحد جانبي التقسيم الثنائي من الدرجة الثانية. ^{[ 25 ]}

يمكن استخدام إعادة تفسير مماثلة لمصفوفات التجاور لإظهار تطابق تام بين الرسوم البيانية الموجهة (على عدد معين من الرؤوس المُصنفة، مع السماح بالحلقات الذاتية) والرسوم البيانية ثنائية الأجزاء المتوازنة، التي لها نفس عدد الرؤوس على جانبي التقسيم الثنائي. فعلى سبيل المثال، يمكن أن تكون مصفوفة التجاور لرسم بياني موجه ذي n رأسًا أي مصفوفة (0,1) بحجم n.${\displaystyle n\times n}$ويمكن إعادة تفسير ذلك على أنه مصفوفة التجاور لرسم بياني ثنائي الأجزاء يحتوي على n رأسًا على كل جانب من جوانب تقسيمه الثنائي. ^{[ 26 ]} في هذا البناء، يكون الرسم البياني ثنائي الأجزاء هو الغطاء المزدوج ثنائي الأجزاء للرسم البياني الموجه.

من الممكن اختبار ما إذا كان الرسم البياني ثنائي الأجزاء، وإرجاع إما تلوين ثنائي (إذا كان ثنائي الأجزاء) أو دورة فردية (إذا لم يكن كذلك) في وقت خطي ، باستخدام البحث العميق أولاً (DFS). الفكرة الأساسية هي تعيين لون لكل رأس يختلف عن لون والده في غابة البحث العميق أولاً، وذلك بترتيب اجتياز مسبق لغابة البحث العميق أولاً. سيؤدي هذا بالضرورة إلى تلوين ثنائي للغابة الممتدة التي تتكون من الحواف التي تربط الرؤوس بآبائها، ولكنه قد لا يلون بعض الحواف غير التابعة للغابة بشكل صحيح. في غابة البحث العميق أولاً، تكون إحدى نقطتي نهاية كل حافة غير تابعة للغابة سلفًا للنقطة الأخرى، وعندما يكتشف البحث العميق أولاً حافة من هذا النوع، يجب عليه التحقق من أن هذين الرأسين لهما لونان مختلفان. إذا لم يحدث ذلك، فإن المسار في الغابة من السلف إلى الفرع، بالإضافة إلى الحافة ذات اللون الخاطئ، يشكل دورة فردية، والتي تُعاد من الخوارزمية مع نتيجة مفادها أن الرسم البياني ليس ثنائي الأجزاء. ومع ذلك، إذا انتهت الخوارزمية دون اكتشاف دورة فردية من هذا النوع، فيجب تلوين كل حافة بشكل صحيح، وتعيد الخوارزمية التلوين مع نتيجة مفادها أن الرسم البياني ثنائي الأجزاء. ^{[ 27 ]}

بدلاً من ذلك، يمكن استخدام إجراء مشابه مع البحث بالعرض أولاً بدلاً من البحث بالعمق أولاً. وكما في السابق، يُعطى كل عقدة اللون المعاكس للون عقدة الأصل في غابة البحث، وذلك بترتيب البحث بالعرض أولاً. إذا وُجدت حافة تربط رأسًا مُلوّنًا مسبقًا بنفس اللون عند تلوينه، فإن هذه الحافة، بالإضافة إلى المسارات في غابة البحث بالعرض أولاً التي تربط طرفيها بأقدم سلف مشترك لهما ، تُشكّل دورة فردية. إذا انتهت الخوارزمية دون العثور على دورة فردية بهذه الطريقة، فهذا يعني أنها وجدت تلوينًا صحيحًا، ويمكن الاستنتاج بثقة أن الرسم البياني ثنائي الأجزاء. ^{[ 28 ]}

بالنسبة لرسوم بيانية التقاطع لـ${\displaystyle n}$باستخدام القطع المستقيمة أو الأشكال البسيطة الأخرى في المستوى الإقليدي ، من الممكن اختبار ما إذا كان الرسم البياني ثنائي الأجزاء وإرجاع إما تلوين ثنائي أو دورة فردية في الزمن${\displaystyle O(n\log n)}$باستخدام ترميز Big O ، على الرغم من أن الرسم البياني نفسه قد يحتوي على ما يصل إلى${\displaystyle O(n^{2})}$الحواف. ^{[ 29 ]}

تُعدّ مسألة اجتياز الدورات الفردية مسألة حسابية من فئة NP-كاملة ، وتطرح السؤال التالي: إذا كان لدينا رسم بياني G = ( V , E ) وعدد k ، فهل توجد مجموعة من k رأسًا يؤدي حذفها من G إلى جعل الرسم البياني الناتج ثنائي الأجزاء؟ ^{[ 30 ]} تُصنّف هذه المسألة ضمن المسائل ذات المعاملات الثابتة ، أي أنه يمكن تحديد زمن تشغيل خوارزمية يكون زمن تشغيلها محدودًا بدالة متعددة الحدود لحجم الرسم البياني مضروبة في دالة أكبر لـ k . ^{[ 31 ]} يُستمد اسم اجتياز الدورات الفردية من حقيقة أن الرسم البياني يكون ثنائي الأجزاء إذا وفقط إذا لم يحتوِ على دورات فردية . وبالتالي، لحذف رؤوس من رسم بياني بهدف الحصول على رسم بياني ثنائي الأجزاء، يجب "الوصول إلى جميع الدورات الفردية"، أو إيجاد ما يُسمى بمجموعة اجتياز الدورات الفردية . في الرسم التوضيحي، تحتوي كل دورة فردية في الرسم البياني على الرؤوس الزرقاء (الأدنى)، لذا فإن إزالة تلك الرؤوس تقتل جميع الدورات الفردية وتترك رسمًا بيانيًا ثنائي الأجزاء. 

تُعدّ مشكلة تقسيم الحواف إلى جزأين مشكلة خوارزمية تتمثل في حذف أقل عدد ممكن من الحواف لجعل الرسم البياني ثنائي الأجزاء، وهي أيضًا مشكلة مهمة في خوارزميات تعديل الرسوم البيانية. كما أن هذه المشكلة قابلة للحل باستخدام معلمات ثابتة ، ويمكن حلها في وقت محدد.${\textstyle O\left(2^{k}m^{2}\right)}$، ^{[ 32 ]} حيث k هو عدد الحواف المراد حذفها و m هو عدد الحواف في الرسم البياني المدخل.

التطابق في الرسم البياني هو مجموعة جزئية من حوافه، لا يشترك أي ضلعين منها في نقطة نهاية واحدة. تُعرف خوارزميات ذات زمن متعدد الحدود لحل العديد من مسائل التطابق، بما في ذلك التطابق الأقصى (إيجاد تطابق يستخدم أكبر عدد ممكن من الحواف)، والتطابق ذي الوزن الأقصى ، والزواج المستقر . ^{[ 33 ]} في كثير من الحالات، تكون مسائل التطابق أسهل حلًا على الرسوم البيانية ثنائية الأجزاء مقارنةً بالرسوم البيانية غير ثنائية الأجزاء، ^{[ 34 ]} والعديد من خوارزميات التطابق، مثل خوارزمية هوبكروفت-كارب للتطابق ذي العدد الأقصى ^{[ 35 ]} ، تعمل بشكل صحيح فقط على المدخلات ثنائية الأجزاء.

كمثال بسيط، لنفترض أن مجموعة${\displaystyle P}$يبحث جميع الأشخاص عن وظائف من بين مجموعة${\displaystyle J}$من الوظائف، حيث لا يكون جميع الأشخاص مناسبين لجميع الوظائف. يمكن نمذجة هذا الوضع كرسم بياني ثنائي الأجزاء${\displaystyle (P,J,E)}$حيث يربط ضلع كل باحث عن عمل بكل وظيفة مناسبة. ^{[ 36 ]} يصف التوافق التام طريقةً لتلبية احتياجات جميع الباحثين عن عمل وشغل جميع الوظائف في آنٍ واحد؛ إذ تُقدّم نظرية هول للزواج توصيفًا للرسوم البيانية ثنائية الأجزاء التي تسمح بالتوافق التام. يطبّق البرنامج الوطني لتنسيق الإقامة أساليب مطابقة الرسوم البيانية لحلّ هذه المشكلة لطلاب الطب الباحثين عن عمل في الولايات المتحدة ووظائف الإقامة في المستشفيات . ^{[ 37 ]}

يُعد تحليل دولماج -مندلسون تحليلًا هيكليًا للرسوم البيانية الثنائية الأجزاء، وهو مفيد في إيجاد المطابقات القصوى. ^{[ 38 ]}