رسم بياني غير منتظم للغاية

في نظرية الرسم البياني ، الرسم البياني غير المنتظم للغاية هو رسم بياني يكون فيه لكل رأس، جميع جيران ذلك الرأس لديهم درجات مميزة .

تم وصف الرسوم البيانية غير المنتظمة في البداية بواسطة يوسف علوي ، وغاري شارتراند ، وفان تشونغ ، وبول إيردوس ، ورونالد غراهام ، وأورترود أويلرمان . ^{[ 1 ]} وقد كان دافعهم هو تعريف "عكس" الرسم البياني المنتظم ، وهو مفهوم تمت دراسته بشكل شامل وفهمه جيدًا.

لم يكن تعريف "الرسم البياني غير المنتظم" واضحًا على الفور. في الرسم البياني المنتظم من الدرجة k ، تكون درجة جميع الرؤوس k . في أي رسم بياني G يحتوي على أكثر من رأس واحد، يجب أن يكون لرأسين في G نفس الدرجة، لذا لا يمكن تعريف الرسم البياني غير المنتظم بأنه رسم بياني بجميع رؤوسه ذات درجات مختلفة. قد يميل المرء إذًا إلى تعريف الرسم البياني غير المنتظم بأنه رسم بياني بجميع رؤوسه ذات درجات مختلفة باستثناء رأسين، لكن هذا النوع من الرسوم البيانية مفهوم جيدًا أيضًا، وبالتالي فهو غير مثير للاهتمام. ^{[ 2 ]} 

لذا، اتجه علماء نظرية الرسوم البيانية إلى مسألة الانتظام المحلي. يكون الرسم البياني منتظمًا محليًا عند رأس v إذا كانت جميع الرؤوس المجاورة لـ v لها درجة r . وبالتالي، يكون الرسم البياني غير منتظم محليًا إذا كان لكل رأس v في G جيران v درجات مختلفة، وتُسمى هذه الرسوم البيانية بالرسوم البيانية غير المنتظمة للغاية. ^{[ 1 ]}

بعض الحقائق حول الرسوم البيانية غير المنتظمة للغاية التي حددها علاوي وآخرون : ^{[ 3 ]}

• إذا كان v رأسًا من الدرجة القصوى d في رسم بياني غير منتظم للغاية H ، فإن v يكون مجاورًا لرأس واحد فقط من كل درجة 1،  2،  ...، d . ^{[ 3 ]} 
• أكبر درجة في رسم بياني غير منتظم للغاية لا تتجاوز نصف عدد الرؤوس. ^{[ 3 ]}
• إذا كان H عبارة عن رسم بياني غير منتظم للغاية بدرجة قصوى d ، فيمكن إنشاء رسم بياني غير منتظم للغاية بدرجة d + 1 عن طريق أخذ نسختين من H وإضافة حافة بين الرأسين بدرجة d . ^{[ 3 ]} 
• تؤول النسبة H ( n )/ G ( n ) إلى الصفر عندما تؤول n إلى اللانهاية بسرعة أسية، حيث H ( n ) هو عدد الرسوم البيانية غير المنتظمة للغاية (غير المتماثلة) ذات n رأس، و G ( n ) هو العدد الإجمالي للرسوم البيانية ذات n رأس. ^{[ 3 ]}
• لكل رسم بياني G ، يوجد رسم بياني H غير منتظم للغاية يحتوي على G كرسم بياني فرعي مستحث . ^{[ 3 ]}

هذه الملاحظة الأخيرة مماثلة لنتيجة دينيس كونيغ ، التي تنص على أنه إذا كان H رسمًا بيانيًا ذو درجة قصوى r ، فإنه يوجد رسم بياني G منتظم من الدرجة r ويحتوي على H كرسم بياني فرعي مستحث. ^{[ 3 ]} 

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

• رسم بياني غير منتظم متدرج
• فرضية عدم التوازن