درجة عقد الرسم البياني

الخطوة 1: فهم نظرية الرسم البياني. الرسم البياني غير الموجه يتكون من رؤوس (vertices) وحواف (edges). كل حافة تربط بين رأسين. درجة الرأس هي عدد الحواف المتصلة به. في الرسم البياني غير الموجه، كل حافة تساهم بدرجة 1 لكل رأس من طرفيها، لذا مجموع درجات جميع الرؤوس يساوي ضعف عدد الحواف (2E). هذا هو مبدأ المصافحة (Handshaking Lemma).

الخطوة 2: إدخال عدد الرؤوس والحواف. أدخل عدد الرؤوس (n) وعدد الحواف (m) في الرسم البياني. تأكد من أن الرسم البياني غير موجه ولا يحتوي على حلقات ذاتية (self-loops) أو حواف مكررة للحصول على نتيجة دقيقة. إذا كان هناك حلقات ذاتية، فإنها تساهم بدرجتين في المجموع ولكنها تؤثر على الصيغة؛ في هذه الحالة، الصيغة المعدلة هي متوسط الدرجة = (2m + عدد الحلقات) / n. لكن الحاسبة تفترض رسماً بيانياً بسيطاً.

الخطوة 3: تطبيق الصيغة. متوسط درجة العقد = (2 * عدد الحواف) / عدد الرؤوس. هذه الصيغة مشتقة من مبدأ المصافحة: مجموع الدرجات = 2E. ثم نقسم على عدد الرؤوس N للحصول على المتوسط. الناتج يعطينا فكرة عن كيفية توزيع الحواف بين الرؤوس. إذا كان المتوسط مرتفعاً، فالرسم البياني كثيف؛ وإذا كان منخفضاً، فهو متناثر.