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

في نظرية المخططات ، وهي فرع من فروع الرياضيات، يُعرف المخطط المنقسم بأنه مخطط يمكن فيه تقسيم الرؤوس إلى زمرة ومجموعة مستقلة . دُرست المخططات المنقسمة لأول مرة من قبل فولديس وهامر ( 1977أ ، 1977 ب ) ، وقُدمت بشكل مستقل من قبل تيشكيفيتش وتشيرنياك ( 1979 ) ، حيث أطلقوا على هذه المخططات اسم "المخططات القطبية" ( بالروسية : полярные графы ). ^{[ 1 ]}  

قد يحتوي الرسم البياني المنقسم على أكثر من قسم واحد إلى مجموعة فرعية ومجموعة مستقلة؛ على سبيل المثال، المسار a – b – c هو رسم بياني منقسم، ويمكن تقسيم رؤوسه بثلاث طرق مختلفة:

1. الزمرة { أ ، ب } والمجموعة المستقلة { ج }
2. الزمرة { b , c } والمجموعة المستقلة { a }
3. الزمرة { ب } والمجموعة المستقلة { أ ، ج }

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

من التعريف، يتضح أن الرسوم البيانية المنقسمة مغلقة تحت عملية الإكمال . ^{[ 3 ]} ومن خصائص الرسوم البيانية المنقسمة الأخرى الإكمال: فهي رسوم بيانية وترية، ومكملاتها أيضًا وترية. ^{[ 4 ]} وكما أن الرسوم البيانية الوترية هي رسوم بيانية لتقاطع الأشجار الفرعية، فإن الرسوم البيانية المنقسمة هي رسوم بيانية لتقاطع النجوم الفرعية المختلفة للرسوم البيانية النجمية . ^{[ 5 ]} جميع الرسوم البيانية الوترية تقريبًا هي رسوم بيانية منقسمة؛ أي أنه عندما يؤول n إلى اللانهاية، فإن نسبة الرسوم البيانية الوترية ذات n رأسًا المنقسمة تقترب من الواحد. ^{[ 6 ]}

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

إذا كان الرسم البياني رسمًا بيانيًا منقسمًا ورسمًا بيانيًا فاصليًا في آنٍ واحد ، فإن مكمله يكون رسمًا بيانيًا منقسمًا ورسمًا بيانيًا للمقارنة ، والعكس صحيح. يمكن وصف الرسوم البيانية المنقسمة للمقارنة، وبالتالي الرسوم البيانية المنقسمة للفواصل، من خلال مجموعة من ثلاثة رسوم بيانية فرعية مستحثة ممنوعة. ^{[ 7 ]} الرسوم البيانية المنقسمة هي بالضبط رسوم بيانية العتبة . الرسوم البيانية المنقسمة للتباديل هي بالضبط الرسوم البيانية الفاصلية التي لها مكملات رسوم بيانية فاصلية؛ ^{[ 8 ]} وهي رسوم بيانية للتباديل المدمجة المائلة . ^{[ 9 ]} الرسوم البيانية المنقسمة لها عدد لوني مشترك يساوي 2.

ليكن G مخططًا منقسمًا، مقسمًا إلى زمرة C ومجموعة مستقلة i . عندئذٍ، تكون كل زمرة عظمى في المخطط المنقسم إما C نفسها، أو جوار رأس في i . وبالتالي، يسهل تحديد الزمرة العظمى، وكذلك تحديد المجموعة المستقلة العظمى في المخطط المنقسم. في أي مخطط منقسم، يجب أن يكون أحد الاحتمالات الثلاثة التالية صحيحًا: ^{[ 10 ]}

1. يوجد رأس x في i بحيث تكون المجموعة C ∪ { x } كاملة. في هذه الحالة، تكون C ∪ { x } زمرة قصوى، وتكون i مجموعة مستقلة قصوى.
2. يوجد رأس x في المجموعة C بحيث تكون المجموعة i ∪ { x } مستقلة. في هذه الحالة، تُعتبر i ∪ { x } مجموعة مستقلة قصوى، وتُعتبر C زمرة قصوى.
3. C هي زمرة قصوى و i هي مجموعة مستقلة قصوى. في هذه الحالة، تحتوي G على تقسيم وحيد ( C ، i ) إلى زمرة ومجموعة مستقلة، حيث C هي الزمرة القصوى، و i هي المجموعة المستقلة القصوى.

بعض مسائل التحسين الأخرى التي تُصنف ضمن فئة NP-complete على عائلات رسوم بيانية أكثر عمومية، بما في ذلك تلوين الرسوم البيانية ، تُعدّ سهلة الحل بالمثل على الرسوم البيانية المنقسمة. يبقى إيجاد دورة هاميلتونية مسألة NP-complete حتى بالنسبة للرسوم البيانية المنقسمة التي تُعتبر رسومًا بيانية وترية قوية . ^{[ 11 ]} ومن المعروف أيضًا أن مسألة مجموعة الهيمنة الدنيا تبقى مسألة NP-complete بالنسبة للرسوم البيانية المنقسمة. ^{[ 12 ]}

إحدى الخصائص المميزة للرسوم البيانية المنقسمة هي إمكانية التعرف عليها فقط من خلال متواليات درجاتها . لنفترض _أن متوالية درجات الرسم البياني G هي d₁ ≥ d₂ _≥ … ≥ dₙ _، ولنفترض أن m هي أكبر قيمة لـ i بحيث يكون dᵢ ≥ i _– 1. عندئذٍ يكون G رسمًا بيانيًا منقسمًا إذا وفقط إذا

${\displaystyle \sum _{i=1}^{m}d_{i}=m(m-1)+\sum _{i=m+1}^{n}d_{i}.}$

إذا كان الأمر كذلك، فإن الرؤوس m ذات الدرجات الأكبر تشكل زمرة قصوى في G ، وتشكل الرؤوس المتبقية مجموعة مستقلة. ^{[ 13 ]}

يقيس معامل الانقسام في أي رسم بياني مدى عدم صحة هذه المتباينة. إذا لم يكن الرسم البياني منقسمًا، فيمكن الحصول على أصغر تسلسل من عمليات إضافة وإزالة الحواف التي تجعله منقسمًا عن طريق إضافة جميع الحواف المفقودة بين الرؤوس m ذات الدرجات الأكبر، وإزالة جميع الحواف بين أزواج الرؤوس المتبقية؛ ويحسب معامل الانقسام عدد العمليات في هذا التسلسل. ^{[ 14 ]}

أظهر رويل (2000) أن الرسوم البيانية المنقسمة ذات n رأس ( غير المصنفة ) تتطابق تطابقًا تامًا مع عائلات سبيرنر معينة . وباستخدام هذه الحقيقة، حدد صيغة لعدد الرسوم البيانية المنقسمة غير المتماثلة ذات n رأس. بالنسبة للقيم الصغيرة لـ n ، بدءًا من n = 1، تكون هذه الأعداد

1، 2، 4، 9، 21، 56، 164، 557، 2223، 10766، 64956، 501696، ... (التسلسل A048194 في OEIS ) .

وقد تم إثبات هذه النتيجة العددية أيضًا في وقت سابق بواسطة تيشكيفيتش وتشيرنياك (1990) .

• يظهر فصل عن الرسوم البيانية المنقسمة في كتاب مارتن تشارلز جولومبيك ، "نظرية الرسم البياني الخوارزمية والرسوم البيانية المثالية".