لفهم الدرجة الداخلية والخارجية للرأس، علينا أن نتعرف أولاً على مفهوم درجة الرأس. بعد ذلك، يمكننا بسهولة فهم الدرجة الداخلية والخارجية للرأس. يجب أن نعلم أنه لا يمكن تحديد الدرجة الداخلية والخارجية إلا في الرسم البياني الموجه. يمكننا حساب درجة الرأس بمساعدة رسم بياني غير موجه. في الرسم البياني غير الموجه، لا يمكننا حساب الدرجة الداخلية والخارجية للرأس.
درجة قمة الرأس
إذا أردنا إيجاد درجة كل رأس في الرسم البياني، في هذه الحالة، علينا أن نحسب عدد العلاقات التي تنشأ بين رأس معين والرأس الآخر. بمعنى آخر، يمكننا تحديد درجة الرأس بمساعدة حساب عدد الحواف المتصلة بذلك الرأس. تتم الإشارة إلى درجة الرأس بمساعدة الدرجة (v). إذا كان هناك رسم بياني بسيط، يحتوي على عدد n من القمم، في هذه الحالة، فإن درجة أي قمة ستكون:
Deg(v) = n-1 ∀ v ∈ G
تتمتع القمة بالقدرة على تكوين حافة مع جميع القمم الأخرى في الرسم البياني باستثناء نفسها. لذلك في رسم بياني بسيط، سيتم معرفة درجة الرأس من خلال عدد القمم في الرسم البياني ناقص 1. هنا يتم استخدام 1 للرأس الذاتي لأنه لا يشكل حلقة بمفرده. إذا كان الرسم البياني يحتوي على القمم التي لها حلقة ذاتية، فلن يكون هذا النوع من الرسم البياني رسمًا بيانيًا بسيطًا.
مثال:
في هذا المثال، لدينا رسم بياني يحتوي على 6 رؤوس، أي a وb وc وd وe وf. الرأس 'أ' له الدرجة 5، وجميع القمم الأخرى لها الدرجة 1. إذا كان أي قمة لها الدرجة 1، فسيعرف هذا النوع من القمم باسم 'القمة النهائية'.
هناك حالتان من الرسوم البيانية التي يمكننا من خلالها النظر في درجة الرأس، والتي يتم وصفها على النحو التالي:
- رسم بياني غير موجه
- مخطط موجه
الآن سوف نتعرف على درجة الرأس في الرسم البياني الموجه ودرجة الرأس في الرسم البياني غير الموجه بالتفصيل.
درجة الرأس في الرسم البياني غير الموجه
إذا كان هناك رسم بياني غير موجه، فلن يكون هناك حافة موجهة في هذا النوع من الرسم البياني. يتم وصف الأمثلة لتحديد درجة قمة الرأس في الرسم البياني غير الموجه على النحو التالي:
مثال 1: في هذا المثال، سننظر في رسم بياني غير موجه. والآن سوف نوجد درجة كل رأس في هذا الرسم البياني.
حل: في الرسم البياني غير الموجه أعلاه، يوجد إجمالي 5 أرقام من القمم، أي a وb وc وd وe. يتم وصف درجة كل قمة على النحو التالي:
- يحتوي الرسم البياني أعلاه على حافتين تلتقيان عند الرأس 'a'. وبالتالي درجة (أ) = 2
- يحتوي هذا الرسم البياني على ثلاث حواف تلتقي عند الرأس 'b'. وبالتالي درجة (ب) = 3
- يحتوي الرسم البياني أعلاه على حافة واحدة تلتقي عند الرأس 'c'. وبالتالي Deg(c) = 1. يُعرف الرأس c أيضًا باسم الرأس المعلق.
- يحتوي الرسم البياني أعلاه على حافتين تلتقيان عند الرأس 'd'. وبالتالي درجة (د) = 2.
- يحتوي الرسم البياني أعلاه على 0 حواف تلتقي عند الرأس 'e'. وبالتالي Deg(a) = 0. يمكن أيضًا تسمية الرأس e بالرأس المعزول.
مثال 2: في هذا المثال، سننظر في رسم بياني غير موجه. والآن سوف نوجد درجة كل رأس في هذا الرسم البياني.
حل: في الرسم البياني غير الموجه أعلاه، يوجد إجمالي 5 أرقام من القمم، أي a وb وc وd وe. يتم وصف درجة كل قمة على النحو التالي:
درجة الرأس أ = درجة (أ) = 2
درجة الرأس ب = درجة (ب) = 2
درجة الرأس ج = درجة (ج) = 2
درجة الرأس د = درجة (د) = 2
درجة الرأس e = درجة(e) = 0
في هذا الرسم البياني، لا يوجد قمة معلقة، والقمة 'e' هي قمة معزولة.
درجة الرأس في الرسم البياني الموجه
إذا كان الرسم البياني عبارة عن رسم بياني موجه، ففي هذا الرسم البياني، يجب أن يكون لكل قمة درجة داخلية ودرجة خارجية. لنفترض أن هناك رسم بياني موجه. في هذا الرسم البياني، يمكننا استخدام الخطوات التالية لمعرفة الدرجة الداخلية والخارجية ودرجة الرأس.
في درجة قمة الرأس
يمكن وصف الدرجة الداخلية للرأس على أنها عدد من الحواف ذات الحرف v، حيث يتم استخدام v للإشارة إلى الرأس الطرفي. بمعنى آخر، يمكننا وصفه بأنه عدد من الحواف القادمة إلى الرأس. بمساعدة درجة بناء الجملة-(v)، يمكننا أن نكتب الدرجة الداخلية للرأس. إذا أردنا تحديد الدرجة الداخلية للرأس، فيجب علينا حساب عدد الحواف التي تنتهي عند الرأس.
خارج درجة قمة الرأس
يمكن وصف الدرجة الخارجية للرأس على أنها عدد من الحواف ذات الحرف v، حيث يتم استخدام v للإشارة إلى الرأس الأولي. بعبارة أخرى، يمكننا وصفه بأنه عدد من الحواف الخارجة من الرأس. بمساعدة درجة بناء الجملة+(v)، يمكننا كتابة الدرجة الخارجية للرأس. إذا أردنا تحديد الدرجة الخارجية لرأس ما، فعلينا أن نحسب عدد الحواف التي تبدأ من الرأس.
درجة قمة الرأس
تتم الإشارة إلى درجة الرأس بمساعدة الدرجة (v)، والتي تساوي إضافة درجة الرأس الداخلية ودرجة الرأس الخارجية. يتم وصف التمثيل الرمزي لدرجة الرأس على النحو التالي:
Deg(v) = deg-(v) + deg+(v)
مثال 1: في هذا المثال، لدينا رسم بياني، وعلينا تحديد درجة كل قمة.
حل: لهذا، سنوجد أولًا درجة الرأس، والدرجة الداخلية للرأس، ثم الدرجة الخارجية للرأس.
كما نرى أن الرسم البياني أعلاه يحتوي على إجمالي 6 رؤوس، أي v1 وv2 وv3 وv4 وv5 وv6.
في الدرجة:
في درجة الرأس v1 = درجة (v1) = 1
في درجة الرأس v2 = درجة (v2) = 1
في درجة الرأس v3 = درجة (v3) = 1
في درجة الرأس v4 = درجة (v4) = 5
داخل درجة الرأس v5 = درجة (v5) = 1
داخل درجة الرأس v6 = درجة (v6) = 0
خارج الدرجة:
طويلة لسلسلة جافا
الدرجة الخارجية للرأس v1 = درجة (v1) = 2
الدرجة الخارجية للرأس v2 = درجة (v2) = 3
الدرجة الخارجية للقمة v3 = الدرجة (v3) = 2
الدرجة الخارجية للقمة v4 = درجة (v4) = 0
الدرجة الخارجية للقمة v5 = درجة (v5) = 2
الدرجة الخارجية للقمة v6 = درجة (v6) = 0
درجة قمة الرأس
بمساعدة التعريف الموصوف أعلاه، نعلم أن درجة قمة الرأس Deg(v) = درجة-(ت) + أنت+(الخامس). الآن سوف نقوم بحسابها بمساعدة هذه الصيغة مثل هذا:
درجة الرأس v1 = درجة(v1) = 1+2 = 3
درجة الرأس v2 = درجة(v2) = 1+3 = 4
درجة الرأس v3 = درجة(v3) = 1+2 = 3
درجة الرأس v4 = درجة(v4) = 5+0 = 5
درجة الرأس v5 = درجة(v5) = 1+2 = 3
درجة الرأس v6 = درجة(v6) = 0+0 = 0
مثال 2:
في هذا المثال، لدينا رسم بياني موجه ذو 7 رؤوس. يحتوي الرأس 'a' على حافتين، أي 'ad' و'ab'، وهما يتجهان نحو الخارج. ومن ثم، فإن الرأس 'a' يحتوي على الدرجة الخارجية، وهي 2. وبالمثل، فإن الرأس 'a' له أيضًا حافة 'ga'، والتي تتجه نحو هذا الرأس 'a'. ومن ثم، فإن الرأس 'أ' يحتوي على الدرجة الداخلية، وهي 1.
حل: يتم وصف الدرجة الداخلية والخارجية لجميع القمم المذكورة أعلاه على النحو التالي:
في الدرجة:
في درجة الرأس أ = درجة (أ) = 1
في درجة الرأس ب = درجة (ب) = 2
في درجة الرأس ج = درجة (ج) = 2
في درجة الرأس د = درجة (د) = 1
في درجة الرأس e = درجة(e) = 1
في درجة الرأس f = درجة (f) = 1
داخل درجة الرأس g = درجة(g) = 0
خارج الدرجة:
الدرجة الخارجية للقمة a = درجة (أ) = 2
الدرجة الخارجية للرأس ب = درجة (ب) = 0
الدرجة الخارجية للقمة c = درجة (ج) = 1
الدرجة الخارجية للقمة d = درجة(d) = 1
الدرجة الخارجية للقمة e = deg(e) = 1
الدرجة الخارجية للقمة f = درجة(f) = 1
الدرجة الخارجية للقمة g = deg(g) = 2
درجة كل قمة:
نحن نعلم أن درجة قمة الرأس Deg(v) = درجة-(ت) + أنت+(الخامس). الآن سوف نقوم بحسابها بمساعدة هذه الصيغة مثل هذا:
درجة الرأس أ = درجة (أ) = 1+2 = 3
jvm في جافا
درجة الرأس ب = درجة(ب) = 2+0 = 2
درجة الرأس ج = درجة(ج) = 2+1 = 3
درجة الرأس د = درجة(د) = 1+1 = 2
درجة الرأس e = درجة(e) = 1+1 = 2
درجة الرأس f = درجة(f) = 1+1 = 2
درجة الرأس g = درجة(g) = 0+2 = 2
مثال 3: في هذا المثال، لدينا رسم بياني موجه بخمسة رؤوس. يحتوي الرأس 'a' على حافة واحدة، أي 'ae'، والتي تتجه نحو الخارج. ومن ثم، فإن الرأس 'a' يحتوي على درجة خارجية، وهي 1. وبالمثل، فإن الرأس 'a' له أيضًا حافة 'ba'، والتي تتجه نحو هذا الرأس 'a'. ومن ثم، فإن الرأس 'أ' يحتوي على الدرجة الداخلية، وهي 1.
حل: يتم وصف الدرجة الداخلية والخارجية لجميع القمم المذكورة أعلاه على النحو التالي:
في الدرجة
في درجة الرأس أ = درجة (أ) = 1
في درجة الرأس ب = درجة (ب) = 0
في درجة الرأس ج = درجة (ج) = 2
في درجة الرأس د = درجة (د) = 1
في درجة الرأس e = درجة(e) = 1
خارج الدرجة:
الدرجة الخارجية للقمة a = درجة (أ) = 1
الدرجة الخارجية للرأس ب = درجة (ب) = 2
خارج درجة قمة الرأس ج = درجة (ج) = 0
الدرجة الخارجية للقمة d = درجة(d) = 1
الدرجة الخارجية للقمة e = deg(e) = 1
درجة كل قمة:
نحن نعلم أن درجة قمة الرأس Deg(v) = درجة-(ت) + أنت+(الخامس). الآن سوف نقوم بحسابها بمساعدة هذه الصيغة مثل هذا:
درجة الرأس أ = درجة (أ) = 1+1 = 2
درجة الرأس ب = درجة(ب) = 0+2 = 2
درجة الرأس ج = درجة(ج) = 2+0 = 2
درجة الرأس د = درجة(د) = 1+1 = 2
درجة الرأس e = درجة(e) = 1+1 = 2
مثال 4: في هذا المثال، لدينا رسم بياني، وعلينا تحديد الدرجة والدرجة الداخلية والدرجة الخارجية لكل قمة.
حل: لهذا، سوف نوجد أولًا الدرجة الداخلية للرأس ثم الدرجة الخارجية للرأس.
كما نرى أن الرسم البياني أعلاه يحتوي على إجمالي 8 رؤوس، أي 0، 1، 2، 3، 4، 5، و6.
في الدرجة:
داخل درجة الرأس 0 = درجة (0) = 1
في درجة الرأس 1 = درجة (1) = 2
في درجة الرأس 2 = درجة (2) = 2
داخل درجة الرأس 3 = درجة (3) = 2
في درجة الرأس 4 = درجة (4) = 2
داخل درجة الرأس 5 = درجة (5) = 2
في درجة الرأس 6 = درجة (6) = 2
خارج الدرجة:
الدرجة الخارجية للقمة 0 = درجة (0) = 2
الدرجة الخارجية للقمة 1 = درجة (1) = 1
الدرجة الخارجية للقمة 2 = درجة (2) = 3
الدرجة الخارجية للقمة 3 = درجة (3) = 2
الدرجة الخارجية للقمة 4 = درجة (4) = 2
الدرجة الخارجية للقمة 5 = درجة (5) = 2
الدرجة الخارجية للقمة 6 = درجة (6) = 1
درجة كل قمة:
نحن نعلم أن درجة قمة الرأس Deg(v) = درجة-(ت) + أنت+(الخامس). الآن سوف نقوم بحسابها بمساعدة هذه الصيغة مثل هذا:
درجة الرأس 0 = درجة(0) = 1+2 = 3
درجة الرأس 1 = درجة(1) = 2+1 = 3
جافا فاكس البرنامج التعليمي
درجة الرأس 2 = درجة(2) = 2+3 = 5
درجة الرأس 3 = الدرجة(3) = 2+2 = 4
درجة الرأس 4 = الدرجة(4) = 2+2 = 4
درجة الرأس 5 = الدرجة(5) = 2+2 = 4
درجة الرأس 6 = درجة(5) = 2+1 = 3
تسلسل درجة الرسم البياني
لتحديد تسلسل درجات الرسم البياني، علينا أولًا تحديد درجة كل قمة في الرسم البياني. وبعد ذلك سنكتب هذه الدرجات بالترتيب التصاعدي. يمكن أن يسمى هذا الترتيب/التسلسل تسلسل درجات الرسم البياني.
على سبيل المثال: في هذا المثال، لدينا ثلاثة رسوم بيانية لها 3 و4 و5 رؤوس، وتسلسل درجات جميع الرسوم البيانية هو 3.
في الرسم البياني أعلاه، هناك 3 رؤوس. يتم وصف درجة تسلسل هذا الرسم البياني على النحو التالي:
في الرسم البياني أعلاه، هناك 4 رؤوس. يتم وصف تسلسل درجات هذا الرسم البياني على النحو التالي:
في الرسم البياني أعلاه، هناك 5 رؤوس. يتم وصف تسلسل درجات هذا الرسم البياني على النحو التالي: