الرسم البياني للمقارنة

في نظرية الرسم البياني ، الرسم البياني للمقارنة هو رسم بياني غير موجه يربط بين أزواج من العناصر القابلة للمقارنة مع بعضها البعض في ترتيب جزئي . كما تم تسمية الرسوم البيانية للمقارنة بالرسوم البيانية القابلة للتوجيه بشكل متعدي ، والرسوم البيانية القابلة للترتيب جزئيًا ، والرسوم البيانية الاحتواء ، ^[1] والرسوم البيانية المقسوم عليها . ^[2] الرسم البياني لعدم المقارنة هو رسم بياني غير موجه يربط بين أزواج من العناصر غير القابلة للمقارنة مع بعضها البعض في ترتيب جزئي .

بالنسبة لأي مجموعة مرتبة جزئيًا صارمة ( S ،<) ، فإن الرسم البياني للمقارنة لـ ( S ،<) هو الرسم البياني ( S ،⊥) الذي تكون رؤوسه عناصر S والحواف هي تلك الأزواج { u ، v } من العناصر بحيث تكون u < v . أي أنه بالنسبة لمجموعة مرتبة جزئيًا، خذ الرسم البياني غير الدوري الموجه ، وطبق الإغلاق المتعدي ، وأزل التوجيه.

على نحو مماثل، فإن الرسم البياني للمقارنة هو رسم بياني له اتجاه متعدٍ ، ^[3] وهو تعيين اتجاهات لحواف الرسم البياني (أي اتجاه الرسم البياني) بحيث تكون علاقة التجاور للرسم البياني الموجه الناتج متعدية : كلما وجدت حواف موجهة ( x ، y ) و ( y ، z ) ، يجب أن توجد حافة ( x ، z ) .

يمكن تمثيل أي ترتيب جزئي منتهٍ كعائلة من المجموعات، بحيث يكون x < y في الترتيب الجزئي كلما كانت المجموعة المقابلة لـ x مجموعة فرعية من المجموعة المقابلة لـ y . وبهذه الطريقة، يمكن إظهار أن الرسوم البيانية للمقارنة تعادل الرسوم البيانية الاحتواءية لعائلات المجموعات؛ أي رسم بياني برأس لكل مجموعة في العائلة وحافة بين مجموعتين كلما كانت إحداهما مجموعة فرعية من الأخرى. ^[4] بدلاً من ذلك، يمكن للمرء أن يمثل الترتيب الجزئي من خلال عائلة من الأعداد الصحيحة ، بحيث يكون x < y كلما كان العدد الصحيح المقابل لـ x مقسومًا على العدد الصحيح المقابل لـ y . وبسبب هذا البناء، تم أيضًا تسمية الرسوم البيانية للمقارنة بالرسوم البيانية المقسومة. ^[2]

يمكن وصف الرسوم البيانية للمقارنة بأنها الرسوم البيانية التي يمكن من خلالها، لكل دورة معممة (انظر أدناه) بطول فردي، إيجاد حافة ( x ، y ) تربط بين رأسين على مسافة اثنين في الدورة. تسمى هذه الحافة وترًا مثلثيًا . في هذا السياق، يتم تعريف الدورة المعممة على أنها مسار مغلق يستخدم كل حافة من الرسم البياني مرة واحدة على الأكثر في كل اتجاه. ^[5] يمكن أيضًا وصف الرسوم البيانية للمقارنة بقائمة من الرسوم البيانية الفرعية المستحثة المحظورة . ^[6]

كل رسم بياني كامل هو رسم بياني للمقارنة، وهو رسم بياني للمقارنة من الدرجة الكلية . جميع التوجهات غير الدورية للرسم البياني الكامل هي متعدية. كل رسم بياني ثنائي الأجزاء هو أيضًا رسم بياني للمقارنة. يؤدي توجيه حواف الرسم البياني ثنائي الأجزاء من أحد جانبي التقسيم الثنائي إلى الجانب الآخر إلى اتجاه متعدي، يتوافق مع ترتيب جزئي للارتفاع اثنين. وكما لاحظ سيمور (2006)، فإن كل رسم بياني للمقارنة ليس كاملاً ولا ثنائي الأجزاء له قسم منحرف .

المكمل لأي رسم بياني فاصل هو رسم بياني للمقارنة. تسمى علاقة المقارنة ترتيب الفاصل . الرسوم البيانية الفاصلة هي بالضبط الرسوم البيانية التي تكون وترية ولها مكملات رسم بياني للمقارنة. ^[7]

الرسم البياني للتباديل هو رسم بياني احتواء لمجموعة من الفواصل الزمنية. ^[8] لذلك، فإن الرسوم البيانية للتباديل هي فئة فرعية أخرى من الرسوم البيانية للمقارنة.

الرسوم البيانية المثالية بشكل تافه هي الرسوم البيانية للمقارنة بين الأشجار ذات الجذور . ^[9] يمكن وصف الرسوم البيانية المشتركة بأنها رسوم بيانية للمقارنة بين الرتب الجزئية المتسلسلة المتوازية ؛ وبالتالي، فإن الرسوم البيانية المشتركة هي أيضًا رسوم بيانية للمقارنة. ^[10]

الرسوم البيانية الحدية هي نوع خاص آخر من الرسوم البيانية للمقارنة.

كل رسم بياني للمقارنة مثالي . إن كمال الرسوم البيانية للمقارنة هو نظرية ميرسكي ، وكمال مكملاتها هو نظرية ديلورث ؛ يمكن استخدام هذه الحقائق، جنبًا إلى جنب مع نظرية الرسم البياني المثالي ، لإثبات نظرية ديلورث من نظرية ميرسكي أو العكس. ^[11] وبشكل أكثر تحديدًا، فإن الرسوم البيانية للمقارنة هي رسوم بيانية قابلة للترتيب تمامًا ، وهي فئة فرعية من الرسوم البيانية المثالية: خوارزمية التلوين الجشعة للترتيب الطوبولوجي لاتجاه متعدٍ للرسم البياني ستلونها بشكل مثالي. ^[12]

المكمل لكل رسم بياني للمقارنة هو رسم بياني سلسلة . ^[13]

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

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

• الرسم البياني المحدود ، رسم بياني مختلف تم تعريفه من ترتيب جزئي