رقم الميل

في رسم المخططات ونظرية المخططات الهندسية ، فإن رقم ميل المخطط هو الحد الأدنى الممكن لعدد الميول المتميزة للحواف في رسم المخطط الذي يتم فيه تمثيل الرؤوس كنقاط في المستوى الإقليدي وتمثيل الحواف كقطع مستقيمة لا تمر عبر أي رأس غير متطابق.

على الرغم من دراسة مسائل وثيقة الصلة في الهندسة المتقطعة سابقًا، على سبيل المثال من قِبل سكوت (1970) وجاميسون (1984) ، فقد طُرحت مسألة تحديد عدد ميل الرسم البياني بواسطة ويد وتشو (1994) ، اللذين أثبتا أن عدد ميل الرسم البياني الكامل ذي n رأس Kn هو _n بالضبط . ويمكن إنشاء رسم بياني بهذا العدد من الميل عن طريق وضع رؤوس الرسم البياني على مضلع منتظم . 

من الواضح أن رقم ميل الرسم البياني ذي الدرجة القصوى d هو على الأقل${\displaystyle \lceil d/2\rceil }$لأن اثنين على الأكثر من الحواف المتصلة برأس من الدرجة d يمكن أن تشترك في ميل واحد. وبشكل أدق، فإن عدد الميل يساوي على الأقل عدد التشعبات الخطية للرسم البياني، لأن حواف الميل الواحد يجب أن تشكل غابة خطية ، وعدد التشعبات الخطية بدوره يساوي على الأقل${\displaystyle \lceil d/2\rceil }$.

توجد رسوم بيانية ذات درجة قصوى خمسة ذات عدد ميول كبير كيفيًا. ^{[ 1 ]} _{مع ذلك، فإن} كل رسم بياني ذي درجة قصوى ثلاثة له عدد ميول لا يتجاوز أربعة؛ ^{[ 2 ]} تُظهر نتيجة ويد وتشو (1994) للرسم البياني الكامل K4 أن هذا دقيق. لا تصلح كل مجموعة من أربعة ميول لرسم جميع الرسوم البيانية من الدرجة 3: فمجموعة الميول تصلح لهذا الغرض إذا وفقط إذا كانت تُشكل ميول أضلاع وأقطار متوازي الأضلاع . على وجه الخصوص، يمكن رسم أي رسم بياني من الدرجة 3 بحيث تكون حوافه إما موازية للمحاور أو موازية للأقطار الرئيسية للشبكة الصحيحة . ^{[ 3 ]} من غير المعروف ما إذا كانت الرسوم البيانية ذات الدرجة القصوى أربعة لها عدد ميول محدود أم غير محدود. ^{[ 4 ]}

كما أوضح كيسيز، باتش، وبالفولجي (2011) ، فإن لكل رسم بياني مستوٍ تمثيلًا خطيًا مستويًا يكون فيه عدد المنحدرات المختلفة دالةً لدرجة الرسم البياني. ويستند برهانهم إلى بناء ماليتز وباباكستاس (1994) لتقييد الدقة الزاوية للرسوم البيانية المستوية كدالة للدرجة، وذلك بإكمال الرسم البياني إلى رسم بياني مستوٍ أقصى دون زيادة درجته بأكثر من عامل ثابت، وتطبيق نظرية تعبئة الدوائر لتمثيل هذا الرسم البياني المُوسَّع كمجموعة من الدوائر المتماسّة. إذا كانت درجة الرسم البياني الأولي محدودة، فإن النسبة بين أنصاف أقطار الدوائر المتجاورة في التعبئة ستكون محدودة أيضًا بواسطة مبرهنة الحلقة ^{[ 5 ]} ، مما يعني بدوره أن استخدام شجرة رباعية لوضع كل رأس من رؤوس الرسم البياني على نقطة داخل دائرته سينتج عنه منحدرات هي نسب أعداد صحيحة صغيرة. عدد المنحدرات المتميزة الناتجة عن هذا البناء يتناسب طرديًا مع درجة الرسم البياني.

يُعد تحديد ما إذا كان للرسم البياني ميل رقم اثنين مسألةً كاملةً من نوع NP . ^{[ 6 ]} ومن هذا، يترتب على ذلك أن تحديد رقم ميل أي رسم بياني، أو تقريبه بنسبة تقريب أفضل من 3/2، يُعد مسألةً صعبةً من نوع NP.

كما أن تحديد ما إذا كان للرسم البياني المستوي رسم مستوٍ ذو ميل رقم اثنين يُعد مسألة NP-كاملة، ^{[ 7 ]} ومن الصعب على النظرية الوجودية للأعداد الحقيقية تحديد الحد الأدنى لعدد ميل الرسم المستوي. ^{[ 8 ]}