درجة (نظرية الرسم البياني)

في نظرية المخططات ، تُعرف درجة (أو تكافؤ ) رأس في مخطط ما بأنها عدد الحواف المتصلة بهذا الرأس؛ في المخطط المتعدد ، تُساهم الحلقة بـ 2 في درجة الرأس، وذلك بالنسبة لطرفي الحافة. ^{​​[ 1 ]} درجة الرأس${\displaystyle v}$يُشار إليه بـ${\displaystyle \deg(v)}$أو${\displaystyle \deg v}$أعلى درجة في الرسم البياني${\displaystyle G}$يُرمز إليه بـ${\displaystyle \Delta (G)}$، وهو الحد الأقصى لـ${\displaystyle G}$درجات رؤوس الرسم البياني. يُرمز إلى أدنى درجة للرسم البياني بـ${\displaystyle \delta (G)}$، وهو الحد الأدنى من${\displaystyle G}$درجات رؤوس 's. في الرسم البياني المتعدد الموضح على اليمين، تبلغ الدرجة القصوى 5 والدرجة الدنيا 0.

في الرسم البياني المنتظم ، يكون لكل رأس نفس الدرجة، ولذلك يمكننا الحديث عن درجة الرسم البياني. الرسم البياني الكامل (يرمز له بـ${\displaystyle K_{n}}$، أين${\displaystyle n}$(عدد الرؤوس في الرسم البياني) هو نوع خاص من الرسم البياني المنتظم حيث يكون لجميع الرؤوس أعلى درجة ممكنة،${\displaystyle n-1}$.

في الرسم البياني الموقّع ، يُطلق على عدد الحواف الموجبة المتصلة برأس ما اسم درجته الموجبة ، ويُطلق على عدد الحواف السالبة المتصلة به اسم درجته السالبة . ^{[ 2 ]}

تنص صيغة مجموع الدرجات على أنه، بالنظر إلى رسم بياني${\displaystyle G=(V,E)}$،

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$.

تشير الصيغة إلى أنه في أي رسم بياني غير موجه، يكون عدد الرؤوس ذات الدرجة الفردية زوجيًا. تُعرف هذه العبارة (وكذلك صيغة مجموع الدرجات) باسم " معضلة المصافحة ". ويأتي هذا الاسم الأخير من مسألة رياضية شائعة، وهي إثبات أنه في أي مجموعة من الأشخاص، يكون عدد الأشخاص الذين صافحوا عددًا فرديًا من الأشخاص الآخرين في المجموعة زوجيًا. ^{[ 3 ]}

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

مسألة تسلسل الدرجات هي مسألة إيجاد بعض أو كل الرسوم البيانية التي يكون تسلسل درجاتها عبارة عن متتالية غير متزايدة معطاة من الأعداد الصحيحة الموجبة. (يمكن تجاهل الأصفار اللاحقة لأنها تُحقق بسهولة بإضافة عدد مناسب من الرؤوس المعزولة إلى الرسم البياني). تُسمى المتتالية التي تُمثل تسلسل درجات رسم بياني بسيط، أي التي يكون لمسألة تسلسل الدرجات حل لها، متتالية بيانية . ونتيجةً لصيغة مجموع الدرجات، لا يمكن تمثيل أي متتالية مجموعها فردي، مثل (3، 3، 1)، كتسلسل درجات لرسم بياني. وينطبق العكس أيضًا: إذا كان مجموع المتتالية زوجيًا، فإنها تُمثل تسلسل درجات لرسم بياني متعدد. بناء مثل هذا الرسم البياني بسيط: يتم توصيل الرؤوس ذات الدرجات الفردية في أزواج (لتكوين تطابق )، ثم تُملأ القيم المتبقية ذات الدرجات الزوجية بحلقات ذاتية. أما مسألة ما إذا كان من الممكن تمثيل متتالية درجات معينة برسم بياني بسيط فهي أكثر تعقيدًا. تُعرف هذه المسألة أيضًا بمسألة تمثيل الرسم البياني ، ويمكن حلها إما باستخدام نظرية إردوش-غالاي أو خوارزمية هافيل-حكيمي . وتُعدّ مسألة إيجاد أو تقدير عدد الرسوم البيانية ذات تسلسل درجات مُعطى مسألةً من مجال تعداد الرسوم البيانية .  

بشكل عام، يُعرف تسلسل درجات الرسم البياني الفائق بأنه التسلسل غير المتزايد لدرجات رؤوسه. التسلسل هو${\displaystyle k}$-رسم بياني إذا كان تسلسل درجات لبعض بسيط${\displaystyle k}$- رسم بياني فائق منتظم. على وجه الخصوص، أ${\displaystyle 2}$التسلسل الرسومي هو تسلسل رسومي. تحديد ما إذا كان تسلسل معين رسوميًا${\displaystyle k}$يمكن تنفيذ الرسم البياني في وقت متعدد الحدود لـ${\displaystyle k=2}$عبر نظرية إردوش-غالاي ، لكنها مسألة كاملة من فئة NP لجميع${\displaystyle k\geq 3}$[ ^{5 ]​}

• يُطلق على الرأس ذي الدرجة 0 اسم الرأس المعزول .
• يُطلق على الرأس ذي الدرجة 1 اسم رأس طرفي أو رأس طرفي أو رأس معلق، ويُطلق على الحافة المتصلة بهذا الرأس اسم حافة معلقة. في الرسم البياني على اليمين، {3,5} هي حافة معلقة. هذا المصطلح شائع في دراسة الأشجار في نظرية الرسوم البيانية، وخاصة الأشجار كهياكل بيانات .
• يُطلق على الرأس ذي الدرجة n − 1 في الرسم البياني المكون من n رأس اسم الرأس المسيطر .  

• إذا كان لكل رأس من رؤوس الرسم البياني نفس الدرجة k ، يُسمى الرسم البياني رسمًا بيانيًا منتظمًا من الدرجة k ، ويُقال إن الرسم البياني نفسه له درجة k . وبالمثل، يُسمى الرسم البياني ثنائي الأجزاء الذي يكون فيه لكل رأسين على نفس جانب التقسيم الثنائي نفس الدرجة رسمًا بيانيًا ثنائي الانتظام .  
• يحتوي الرسم البياني غير الموجه والمتصل على مسار أويلري إذا وفقط إذا كان يحتوي على صفر أو رأسين من الدرجة الفردية. أما إذا لم يكن يحتوي على أي رؤوس من الدرجة الفردية، فإن المسار الأويلري يكون دائرة أويلرية.
• الرسم البياني الموجه هو غابة زائفة موجهة إذا وفقط إذا كان لكل رأس درجة خروج لا تتجاوز  1. الرسم البياني الوظيفي هو حالة خاصة من الغابة الزائفة حيث يكون لكل رأس درجة خروج تساوي  1 بالضبط.
• بحسب نظرية بروكس ، فإن أي رسم بياني G بخلاف الزمرة أو الدورة الفردية له عدد لوني على الأكثر  Δ( G )، وبحسب نظرية فيزينغ، فإن أي رسم بياني له مؤشر لوني على الأكثر Δ( G )  +  1.
• الرسم البياني k -degenerate هو رسم بياني يحتوي كل رسم بياني فرعي فيه على رأس بدرجة لا تتجاوز k .

• درجة الدخول ، درجة الخروج للرسوم البيانية الموجهة
• توزيع الدرجات
• تسلسل الدرجات للرسوم البيانية ثنائية الأجزاء

• إردوس، ب . جالاي، ت. (1960). "Gráfok előírt fokszámú pontokkal" (PDF) . ماتيماتيكاي لابوك (باللغة المجرية). 11 : 264 - 274..
• هافيل، فاتسلاف (1955). "ملاحظة حول وجود الرسوم البيانية المحدودة" . Časopis Pro Pěstování Matematiky (باللغة التشيكية). 80 (4): 477-480 . دوى : 10.21136/CPM.1955.108220 .
• حكيمي، س. ل. (1962). "حول إمكانية تمثيل مجموعة من الأعداد الصحيحة كدرجات لرؤوس رسم بياني خطي. الجزء الأول". مجلة جمعية الرياضيات الصناعية والتطبيقية . 10 (3): 496-506 . doi : 10.1137/0110037 . MR 0148049 . .
• سيركسما، جيرارد؛ هوجيفين ، هان (1991). "سبعة معايير للتسلسلات الصحيحة التي تكون رسومية" . مجلة نظرية الرسم البياني . 15 (2): 223-231 . دوى : 10.1002/jgt.3190150209 . السيد 1106533 . .