درجة الرأس في الرسم البياني هي عدد الوصلات ، أي عدد الحواف القادمة من رأس معين. يمكن أن يكون تحديد درجات الرؤوس مفيدا في تحليل الشبكات الاجتماعية المختلفة أو شبكات النقل أو أي أنظمة أخرى ممثلة كرسم بياني.
يمكن استخدام خوارزميات وطرق مختلفة لإيجاد درجات الرؤوس في الرسم البياني. واحدة من أسهل الطرق هي المرور عبر جميع الحواف وحساب عدد المرات التي يحدث فيها كل رأس كبداية أو نهاية للحافة. ستكون الأرقام الناتجة هي درجات القمم المقابلة.
على سبيل المثال ، ضع في اعتبارك الرسم البياني التالي:
القمم: أ ، ب ، ج
الحواف: أب ، أس ، قبل الميلاد ، با
ستكون درجات الرؤوس في هذا الرسم البياني كما يلي:
وبالتالي ، باستخدام عمليات حسابية بسيطة ، من الممكن العثور بسهولة وبسرعة على درجات الرؤوس في أي رسم بياني. يمكن أن تساعد معرفة هذه القيم في حل المهام المختلفة المتعلقة بتحليل الرسم البياني.
- كيفية تحديد درجات القمم بشكل موثوق: دليل مفصل مع أمثلة
- الطريقة 1: عد الحواف
- الطريقة 2: استخدام قائمة الجوار
- الطريقة 3: استخدام مصفوفة الجوار
- المفاهيم الأولية والتعاريف الأساسية
- طرق لتحديد درجات القمم
- خوارزميات لتحديد درجات القمم
- 1. خوارزمية بسيطة لحساب درجات القمم
- 2. مصفوفة الجوار
- 3. قائمة الجوار
- أمثلة على تحديد درجات الرؤوس في الرسوم البيانية
- مثال 1:
- المثال 2:
- توصيات عملية ونصائح مفيدة
- سؤال وجواب
- كيف يمكنني العثور على درجة من قمة الرأس في الرسم البياني?
- كيف يمكنني العثور على درجة من قمة الرأس في الرسم البياني الموجه?
- كيفية العثور على درجة قمة الرأس إذا كانت مصفوفة الجوار معروفة?
- كيف يمكنني العثور على درجات القمم من الرسم البياني المرجح?
- كيف يمكنني العثور على درجة من القمم في الرسم البياني قطع?
- كيف يمكنني العثور على درجة من القمم في الرسم البياني الموجه المرجحة?
كيفية تحديد درجات القمم بشكل موثوق: دليل مفصل مع أمثلة
يعد تحديد درجات الرؤوس إحدى المهام المهمة في نظرية الرسم البياني. يتم تحديد درجة رأس الرسم البياني من خلال عدد الحواف المتصلة برأس معين. في هذه المقالة ، سننظر في عدة طرق لتحديد درجات القمم باستخدام الأمثلة.
الطريقة 1: عد الحواف
إن أبسط طريقة لتحديد درجة الرأس هي حساب الحواف المرتبطة برأس معين. للقيام بذلك ، انتقل من خلال جميع حواف الرسم البياني وحساب عدد الحواف لها قمة الرأس باعتبارها واحدة من نهاياتها. على سبيل المثال ، ضع في اعتبارك الرسم البياني التالي:
| فيرتكس | الدرجة العلمية |
| A | 3 |
| B | 2 |
| C | 2 |
| D | 1 |
في هذا المثال ، فيرتكس أ لديه درجة 3 ، منذ 3 حواف (أب ، أس ، أد) متصلة به. فيرتكس ب لديه درجة 2 ، منذ 2 حواف (أب ، قبل الميلاد) ترتبط به ، وهلم جرا.
الطريقة 2: استخدام قائمة الجوار
هناك طريقة أخرى لتحديد درجات الرؤوس وهي استخدام قائمة الجوار. قائمة الجوار هي جدول حيث يتوافق كل صف مع رأس الرسم البياني ، وتشير الأعمدة إلى الرؤوس المجاورة. لكل قمة ، تحتاج إلى حساب عدد القمم المجاورة. على سبيل المثال ، ضع في اعتبارك المثال التالي:
| قمة الرأس | القمم المجاورة | الدرجة العلمية |
| A | باء ، جيم ، دال | 3 |
| B | أ ، ج | 2 |
| C | ألف ، باء | 2 |
| D | A | 1 |
في هذا المثال ، الرأس أ لديه درجة 3 ، لأنه متصل بالرؤوس ب, ج و د. الرأس ب لديه درجة 2 ، لأنه متصل بالرؤوس أ و ج ، وما إلى ذلك وهلم جرا.
الطريقة 3: استخدام مصفوفة الجوار
الطريقة الثالثة لتحديد درجات الرؤوس هي استخدام مصفوفة الجوار. المصفوفة المجاورة هي جدول نكسن ، حيث تشير كل قيمة في الخلية إلى وجود حافة بين الرؤوس المقابلة. لكل قمة ، من الضروري حساب عدد الحواف التي تقع على هذا الرأس. على سبيل المثال ، ضع في اعتبارك المثال التالي:
| قمة الرأس | الدرجة العلمية |
| A | 3 |
| B | 2 |
| C | 2 |
| D | 1 |
في هذا المثال ، يحتوي الرأس أ على الدرجة 3 ، نظرا لوجود 3 قيم غير صفرية في الصف أ (رؤوس أخرى مجاورة لـ أ). فيرتكس ب لديه درجة 2 ، لأن هناك 2 قيم غير صفرية في الصف ب ، وهلم جرا.
في الختام ، تجدر الإشارة إلى أن اختيار طريقة تحديد درجة الرؤوس يعتمد على نوع الرسم البياني وتعقيده. إذا كان الرسم البياني يحتوي على عدد صغير من الرؤوس والحواف ، فيمكن استخدام طرق عد بسيطة. ومع ذلك ، في حالة الرسوم البيانية الكبيرة ، قد يكون استخدام قائمة الجوار أو مصفوفة الجوار أكثر كفاءة.
المفاهيم الأولية والتعاريف الأساسية
قبل البدء في دراسة درجات رؤوس الرسم البياني ، من الضروري التعرف على المفاهيم والتعريفات الأساسية التي سيتم استخدامها في المستقبل.
الرسم البياني هو تجريد رياضي يستخدم لتمثيل الروابط أو العلاقات بين الكائنات. يتكون الرسم البياني من رؤوس وحواف تربط هذه الرؤوس.
الرأس هو أحد عناصر الرسم البياني. يمكن توصيل كل قمة برؤوس أخرى بالحواف.
الحافة هي اتصال بين رأسين من الرسم البياني. يمكن توجيه الحافة (موجهة) أو غير موجهة (غير موجهة).
درجة الرأس هي عدد الحواف التي يتصل بها رأس معين. في حالة الرسم البياني غير الموجه ، تكون درجة الرأس مساوية لعدد الحواف التي تقع عليه. في حالة الرسم البياني الموجه ، تكون درجة الرأس مساوية لمجموع عدد الحواف الواردة والصادرة.
الدرجة الصادرة للرأس هي عدد الحواف الصادرة المتصلة برأس معين في رسم بياني موجه.
الدرجة الواردة للرأس هي عدد الحواف الواردة المتصلة برأس معين في رسم بياني موجه.
الرأس المعزول هو رأس رسم بياني لا يحتوي على أي حواف متصلة به.
الحلقة هي حافة تربط قمة الرأس بنفسها.
للحصول على دراسة أكثر قابلية للفهم لدرجات رؤوس الرسم البياني ، دعنا نلقي نظرة على بعض الأمثلة ونعمل معها.
طرق لتحديد درجات القمم
يتم تعريف درجة الرأس في الرسم البياني على أنها عدد الحواف المتصلة برأس معين. يمكن أن يكون تحديد درجات الرؤوس مفيدا عند تحليل خصائص الرسم البياني والبحث عن رؤوس مهمة في الشبكات أو الرسوم البيانية الاجتماعية.
هناك طرق مختلفة لتحديد درجات الرؤوس في الرسم البياني:
- طريقة العد: إن أبسط طريقة لتحديد درجات الرؤوس هي حساب عدد الحواف المتصلة بكل رأس في الرسم البياني. لكل قمة ، يتم حساب عدد حواف الحادث ، والتي تعتبر حواف واردة وصادرة.
- طريقة المصفوفة: هناك طريقة أخرى لتحديد درجات الرؤوس وهي استخدام مصفوفة الجوار في الرسم البياني. درجة الرأس تساوي عدد "1" في الصف أو العمود المقابل لمصفوفة الجوار.
- طريقة القائمة: يمكنك أيضا استخدام قائمة تجاور الرسم البياني. لكل رأس ، يتم حساب عدد العناصر في قائمة الجوار التي تمثل الرؤوس المجاورة لهذا الرأس.
يعتمد اختيار طريقة محددة لتحديد درجات الرؤوس على نوع الرسم البياني والمعلومات المتاحة حول هيكله. طريقة العد هي الأبسط ، ولكنها قد تكون غير فعالة للرسوم البيانية الكبيرة. يمكن أن تكون طريقة المصفوفة وطريقة القائمة أكثر فعالية لتحليل الرسوم البيانية الكبيرة.
تتيح لك معرفة درجات الرؤوس تقييم أهمية أو مركزية الرؤوس في الرسم البياني. يمكن للرؤوس ذات الدرجة العالية أن تلعب دورا رئيسيا في نقل المعلومات أو تؤثر على بنية الرسم البياني.
خوارزميات لتحديد درجات القمم
تحدد درجة الرأس في الرسم البياني عدد الحواف المجاورة لذلك الرأس. يعد تحديد درجات الرؤوس مهمة مهمة في تحليل الشبكات والرسوم البيانية. في هذا القسم ، سنلقي نظرة على العديد من الخوارزميات التي يمكن استخدامها لتحديد درجات الرؤوس في الرسم البياني.
1. خوارزمية بسيطة لحساب درجات القمم
أسهل طريقة لتحديد درجات الرؤوس هي التكرار على جميع الحواف في الرسم البياني وحساب عدد الحواف المرتبطة بكل رأس. هذه الخوارزمية لها تعقيد زمني لـ ا (ه) ، أين ه هو عدد الحواف في الرسم البياني.
مثال على كود بايثون:
عدد مواطن_درجات (رسم بياني):
درجة = [0] * لين (الرسم البياني)
للحافة في الرسم البياني:
درجة [حافة [0]] + = 1
درجة [حافة [1]] + = 1
درجات العودة
في هذا الرمز ، نقوم بإنشاء قائمة درجات تمت تهيئتها بالأصفار. ثم نقوم بتشغيل جميع الحواف في الرسم البياني وزيادة عدادات الدرجة للرؤوس المقابلة. وأخيرا ، نعود قائمة من الدرجات مع درجات القمم عد.
2. مصفوفة الجوار
هناك طريقة أخرى لتحديد درجات الرؤوس وهي استخدام مصفوفة الجوار في الرسم البياني. مصفوفة الجوار هي مصفوفة مربعة عند تقاطع الصف الأول والعمود ي هناك 1 إذا كانت القمم أنا و ي متصلة بحافة ، و 0 خلاف ذلك. يعطي مجموع العناصر في كل صف (أو عمود) من مصفوفة الجوار درجة الرأس المقابل.
مثال على الكود لتحديد درجات الرؤوس بناء على مصفوفة الجوار:
درجة_عد_درجة_درجة_درجة_درجة_درجة_درجة_درجة:
الدرجات = [مجموع (صف) للصف في مصفوفة الصف]
درجات العودة
في هذا الرمز ، نقوم بإنشاء قائمة درجات باستخدام مولد قائمة. لكل صف من المصفوفة المجاورة ، نلخص عناصرها ونحصل على درجة الرأس المقابل. وأخيرا ، نعود قائمة من الدرجات مع درجات القمم عد.
3. قائمة الجوار
الطريقة الثالثة لتحديد درجات الرؤوس هي استخدام قائمة تجاور الرسم البياني. ال قائمة الجوار هي قائمة فيها كل عنصر أنا يتوافق مع قائمة الرؤوس المجاورة ل قمة الرأس أنا. يعطي عدد العناصر في كل قائمة فرعية درجة الرأس المقابل.
مثال على الكود لتحديد درجات الرؤوس بناء على قائمة الجوار:
عدد الدرجات:
درجات = [لين (أدجليست [عقدة]) للعقدة في نطاق (لين(أدجليست))]
درجات العودة
في هذا الرمز ، نقوم بإنشاء قائمة درجات باستخدام مولد قائمة. لكل قمة أنا ، نحصل على طول القائمة الفرعية المقابلة ونحصل على درجة قمة الرأس أولا. أخيرا ، نعيد قائمة بالدرجات مع حساب درجات الرؤوس.
اعتمادا على المهمة وبنية البيانات المتاحة لتمثيل الرسم البياني ، يمكنك اختيار الخوارزمية المثلى لتحديد درجات الرؤوس. في بعض الحالات ، قد تكون خوارزمية واحدة أكثر كفاءة من غيرها.
أمثلة على تحديد درجات الرؤوس في الرسوم البيانية
درجة الرأس في الرسم البياني هي أحد المفاهيم الأساسية المستخدمة في تحليل ودراسة الرسوم البيانية. وهو يمثل عدد الحواف المتصلة برأس معين. من أجل الوضوح ، دعنا نفكر في عدد من الأمثلة لتحديد درجات الرؤوس في الرسوم البيانية:
مثال 1:
الرسم البياني:
|
|
مقرر:
لتحديد درجة كل رأس في رسم بياني معين ، تحتاج إلى حساب عدد الحواف المتصلة بكل رأس:
- درجة الرأس 1: 2 (الحواف 1-2 و 1-3)
- درجة الرأس 2: 3 (الحواف 1-2 و 2-4 و 2-5)
- درجة الرأس 3: 3 (الحواف 1-3 و 3-4 و 3-5)
- درجة الرأس 4: 2 (الحواف 2-4 و 3-4)
- درجة الرأس 5: 2 (الحواف 2-5 و 3-5)
المثال 2:
الرسم البياني:
|
|
مقرر:
Степень каждой вершины в данном графе можно определить следующим образом:
- Степень вершины A: 2 (ребра A-B и A-C)
- Степень вершины B: 3 (ребра A-B, B-C и B-D)
- Степень вершины C: 4 (ребра A-C, B-C, C-D и C-E)
- Степень вершины D: 3 (ребра B-D, C-D и D-E)
- Степень вершины E: 2 (ребра C-E и D-E)
هذه ليست سوى بعض الأمثلة التي ستساعدك على فهم أفضل لكيفية تحديد درجات الرؤوس في الرسوم البيانية. تعتبر درجات قمة الرأس سمة مهمة للرسوم البيانية ودراستها لها أهمية عملية كبيرة.
توصيات عملية ونصائح مفيدة
في هذا القسم ، نقدم لك بعض التوصيات العملية والنصائح المفيدة لإيجاد درجات الرؤوس في الرسم البياني. بعد هذه التوصيات ، يمكنك بسهولة وبسرعة العثور على درجات القمم واستخدام هذه المعلومات في مزيد من العمل.
- دراسة هيكل الرسم البياني: قبل البدء في العثور على درجات القمم ، من المهم فهم بنية الرسم البياني. اكتشف الرؤوس المتصلة ببعضها البعض ، والحواف التي تربط هذه الرؤوس.
- استخدام خوارزميات البحث درجة قمة الرأس: هناك خوارزميات مختلفة لإيجاد درجة قمة الرأس في الرسم البياني. يعتمد بعضها على عبور الرسم البياني في العرض أو العمق. دراسة هذه الخوارزميات واختيار واحد الذي هو الأنسب لمهمة محددة.
- استخدم مصفوفات الجوار أو قوائم الجوار: للبحث بكفاءة عن درجات الرؤوس في الرسم البياني ، يوصى باستخدام مصفوفات الجوار أو قوائم الجوار. إنها تسمح لك بتمثيل الرسم البياني كهيكل بيانات يسهل معالجته.
- تطبيق تحليل النتائج: بعد العثور على درجات القمم ، قم بتحليل البيانات التي تم الحصول عليها. إيلاء الاهتمام لأكبر وأصغر درجة من القمم ، وجود القمم مع نفس الدرجات ، وغيرها من الميزات. يمكن أن تكون هذه معلومات مفيدة عند حل مشكلة متعلقة بالرسم البياني.
- استخدم التصور الرسومي: للحصول على تمثيل مرئي للرسم البياني وهيكله ، استخدم التصور الرسومي. سيساعدك هذا على فهم الروابط بين القمم ودرجاتها بشكل أفضل.
باتباع هذه التوصيات العملية والنصائح المفيدة ، ستتمكن من العثور بنجاح على درجات الرؤوس في الرسم البياني. تذكر أن الممارسة تلعب دورا مهما في تعلم مهارات جديدة ، لذلك لا تخف من التجربة وتجربة طرق مختلفة.
سؤال وجواب
كيف يمكنني العثور على درجة من قمة الرأس في الرسم البياني?
درجة الرأس في الرسم البياني تساوي عدد الحواف المتصلة برأس معين. للعثور على درجة قمة الرأس ، من الضروري حساب عدد الحواف التي تقع عليها.
كيف يمكنني العثور على درجة من قمة الرأس في الرسم البياني الموجه?
في الرسم البياني الموجه ، تكون درجة الرأس مساوية لمجموع الحواف الواردة والصادرة المتصلة برأس معين.
كيفية العثور على درجة قمة الرأس إذا كانت مصفوفة الجوار معروفة?
للعثور على درجة الرأس بواسطة مصفوفة الجوار ، من الضروري تلخيص عناصر الصف أو العمود المقابل لهذا الرأس.
كيف يمكنني العثور على درجات القمم من الرسم البياني المرجح?
لا يؤثر وزن حافة الرسم البياني المرجح على درجة الرأس. للعثور على درجة رأس الرسم البياني المرجح ، من الضروري حساب عدد الحواف المتصلة بهذا الرأس.
كيف يمكنني العثور على درجة من القمم في الرسم البياني قطع?
للعثور على درجة الرؤوس في رسم بياني غير متصل ، من الضروري تطبيق خوارزمية لكل مكون من مكونات الاتصال. مكون الاتصال هو الحد الأقصى للرسم البياني الفرعي المتصل للرسم البياني الأصلي.
كيف يمكنني العثور على درجة من القمم في الرسم البياني الموجه المرجحة?
في الرسم البياني الموجه المرجح ، تكون درجة الرأس مساوية لمجموع أوزان الحواف الواردة والصادرة المرتبطة برأس معين.