الانقسام

في نظرية المخططات ، وهي فرع من الرياضيات، يُقاس مدى بُعد المخطط غير الموجه عن المخطط المنقسم بمصطلح " الانقسام " . المخطط المنقسم هو مخطط يمكن تقسيم رؤوسه إلى مجموعة مستقلة (لا تحتوي على أي حواف ضمن هذه المجموعة الفرعية) ومجموعة كاملة (تحتوي على جميع الحواف الممكنة ضمن هذه المجموعة الفرعية). يُعرَّف الانقسام بأنه أقل عدد من عمليات إضافة أو إزالة الحواف التي تُحوّل المخطط المُعطى إلى مخطط منقسم. ^{[ 1 ]}

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

${\displaystyle \sigma (G)={\tbinom {m}{2}}-{\frac {1}{2}}\sum _{i=1}^{m}d_{i}+{\frac {1}{2}}\sum _{i=m+1}^{n}d_{i}.}$

يكون الرسم البياني المعطى رسمًا بيانيًا منقسمًا إذا كانت σ ( G ) = 0. وإلا، فيمكن تحويله إلى رسم بياني منقسم بحساب m ، وإضافة جميع الحواف المفقودة بين أزواج الرؤوس m ذات الدرجة القصوى، وإزالة جميع الحواف بين أزواج الرؤوس المتبقية. ونتيجة لذلك، يمكن حساب الانقسام وتسلسل إضافة الحواف وإزالتها لتحقيقه في وقت خطي . ^{[ 1 ]}

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