ماذا يعني 'قابل للتحقيق' لتسلسل درجات؟

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

ما هي مبرهنة المصافحة؟

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

ما هي نظرية Erdős–Gallai؟

هي شرط ضروري وكافٍ لكون تسلسل ما قابلًا للتحقيق: مرتبًا تنازليًا، يجب ألا يتجاوز مجموع أول k حدود القيمة k(k−1) زائد مجموع min(dᵢ, k) للحدود المتبقية، لكل k من 1 إلى n.

لماذا نتحقق من كل قيمة k؟

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

ماذا يحدث إذا تجاوزت أكبر درجة n − 1؟

في رسم بياني بسيط بـ n رأسًا، لا يمكن لأي رأس أن يكون له أكثر من n − 1 جارًا (لا يمكنه الاتصال بنفسه أو تكرار حافة)، لذا فإن أي درجة تتجاوز n − 1 تجعل التسلسل غير قابل للتحقيق تلقائيًا.

هل رسم التسلسل القابل للتحقيق فريد؟

لا — يمكن لعدة رسوم بيانية مختلفة أن تتشارك نفس تسلسل الدرجات. تؤكد نظرية Erdős–Gallai فقط أن رسمًا بيانيًا واحدًا على الأقل من هذا النوع موجود، وليس أيها بالتحديد.

كم يبلغ طول التسلسل الذي يمكن أن تتعامل معه هذه الآلة الحاسبة؟

تدعم هذه الآلة الحاسبة تسلسلات يصل طولها إلى 100 قيمة، وتتحقق من جميع شروط Erdős–Gallai فورًا حتى عند ذلك الحجم.

أين يُستخدم هذا في الحياة الواقعية؟

يُستخدم في تصميم الشبكات وتحليل الشبكات الاجتماعية للتحقق مما إذا كانت مجموعة مقترحة من أعداد الاتصالات قابلة للتحقيق فعليًا قبل محاولة بناء الشبكة الفعلية.

مدقق تسلسل درجات الرسم البياني — تحقق من كون تسلسل الدرجات قابلًا للتحقيق كرسم بياني

يتحقق مدقق تسلسل درجات الرسم البياني الخاص بنا مما إذا كان تسلسل معطى من الأعداد الصحيحة غير السالبة يمكن أن يكون بالفعل تسلسل درجات لرسم بياني بسيط ما، بتطبيق شروط مجموع البادئات لنظرية Erdős–Gallai مباشرة والإبلاغ بدقة عن الشرط الذي يفشل إذا لم يكن التسلسل قابلًا للتحقيق.

إجابة سريعة

أدخل تسلسل درجات أدناه للتحقق فورًا مما إذا كان قابلًا للتحقيق كرسم بياني عبر نظرية Erdős–Gallai.

تسلسل الدرجات

أدخل أعدادًا صحيحة مفصولة بفواصل أو مسافات، مثل 3,3,2,2,1,1.

كيفية استخدام مدقق تسلسل درجات الرسم البياني — نظرية Erdős–Gallai عبر الإنترنت

1
أدخل تسلسل درجات كأعداد صحيحة مفصولة بفواصل أو مسافات، مثل 3,3,2,2,1,1.
2
انقر على 'احسب' للتحقق مما إذا كان التسلسل قابلًا للتحقيق.
3
راجع التحقق خطوة بخطوة من شروط Erdős–Gallai.

لماذا تستخدم مدقق تسلسل درجات الرسم البياني — نظرية Erdős–Gallai عبر الإنترنت؟

ليست كل قائمة أرقام يمكن أن تكون تسلسل درجات رسم بياني حقيقي — تعطي نظرية Erdős–Gallai اختبارًا دقيقًا: رتّب التسلسل تنازليًا، ولكل طول بادئة k، يجب ألا يتجاوز مجموع أول k درجات القيمة k(k−1) زائد مجموع min(الدرجة, k) عبر الرؤوس المتبقية. تسلسل يجتاز كل شرط من شروط البادئات هذه (وله مجموع زوجي، وفقًا لمبرهنة المصافحة) مضمون أنه قابل للتحقيق كرسم بياني بسيط. تُجري هذه الآلة الحاسبة ذلك التحقق الدقيق وتُبلّغ بدقة عن مكان الفشل، إن حدث.

الأسئلة الشائعة

أدوات ذات صلة

آلة حاسبة مصفوفة التجاور — ابنِ مصفوفة رسم بياني عبر الإنترنت

ابنِ واعرض مصفوفة تجاور رسم بياني من إدخال بسيط لقائمة الحواف، مع تسلسل الدرجات. آلة حاسبة مجانية، موزونة أو غير موزونة.

آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت

لوّن رؤوس رسم بياني بحيث لا تشترك عقدتان متصلتان في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.

مدقق الرسم البياني المستوي — اختبار بأسلوب Kuratowski عبر الإنترنت

تحقق مما إذا كان رسم بياني مستويًا باستخدام شرط E ≤ 3V−6 الضروري بالإضافة إلى بحث صريح عن K₅/K₃,₃ للرسوم البيانية الصغيرة. آلة حاسبة مجانية، ليست اختبار استواء كاملًا.