1. ما هي الشجرة والغابة؟

شجرة

• في نظرية الرسم البياني، أ شجرة هو رسم بياني غير موجه ومتصل وغير دوري . بمعنى آخر، الرسم البياني المتصل الذي لا يحتوي على دورة واحدة يسمى شجرة.
• تمثل الشجرة البنية الهرمية في شكل رسومي.
• وتسمى عناصر الأشجار بالعقد، وتسمى حواف الشجرة بالفروع.
• الشجرة التي عدد رؤوسها n لها حواف (n-1).
• توفر الأشجار العديد من التطبيقات المفيدة البسيطة مثل شجرة العائلة والمعقدة مثل الأشجار في هياكل البيانات لعلوم الكمبيوتر.
• أ ورقة يوجد في الشجرة قمة من الدرجة الأولى أو أي قمة ليس لها أطفال تسمى ورقة.

مثال

في المثال أعلاه، جميعها عبارة عن أشجار ذات رؤوس أقل من 6.

غابة

في نظرية الرسم البياني، أ غابة يكون رسم بياني غير موجه ومنفصل وغير دوري . وبعبارة أخرى، فإن مجموعة الأشجار المنفصلة تعرف باسم الغابة. كل مكون من مكونات الغابة عبارة عن شجرة.

مثال

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

2. خصائص الأشجار

1. يجب أن تحتوي كل شجرة لها رأسان على الأقل على ورقتين على الأقل.
2. تتميز الأشجار بالعديد من الخصائص:
   افترض أن T عبارة عن رسم بياني ذو رؤوس n، فإن العبارات التالية متكافئة:
   • تي هي شجرة.
   • T لا يحتوي على دورات وله حواف n-1.
   • T متصل وله حافة (n -1).
   • T عبارة عن رسم بياني متصل، وكل حافة هي حافة مقطوعة.
   • أي رأسين من الرسم البياني T متصلان بمسار واحد بالضبط.
   • لا تحتوي T على دورات، وبالنسبة لأي حافة جديدة e، فإن الرسم البياني T+ e له دورة واحدة بالضبط.
3. كل حافة من الشجرة مقطوعة.
4. إن إضافة حافة واحدة إلى الشجرة يحدد دورة واحدة بالضبط.
5. يحتوي كل رسم بياني متصل على شجرة ممتدة.
6. تحتوي كل شجرة على رأسين على الأقل من الدرجة الثانية.

3. الشجرة الممتدة

أ تمتد شجرة في الرسم البياني المتصل G هو رسم بياني فرعي H من G يتضمن جميع رؤوس G وهو أيضًا شجرة.

مثال

خذ بعين الاعتبار الرسم البياني التالي G:

من الرسم البياني أعلاه G يمكننا تنفيذ ثلاث أشجار ممتدة H:

طرق العثور على الشجرة الممتدة

يمكننا العثور على الشجرة الممتدة بشكل منهجي باستخدام إحدى الطريقتين:

1. طريقة القطع
2. طريقة البناء

1. طريقة القطع

• ابدأ باختيار أي دورة في الرسم البياني G.
• قم بإزالة أحد حواف الدورة.
• كرر هذه العملية حتى لا تكون هناك دورات متبقية.

مثال

• النظر في الرسم البياني G،

• إذا قمنا بإزالة الحافة ac التي تدمر الدورة a-d-c-a في الرسم البياني أعلاه فإننا نحصل على الرسم البياني التالي:

• قم بإزالة الحافة cb التي تدمر الدورة a-d-c-b-a من الرسم البياني أعلاه ثم نحصل على الرسم البياني التالي:

• إذا قمنا بإزالة الحافة ec، التي تدمر الدورة d-e-c-d من الرسم البياني أعلاه، فسنحصل على الشجرة الممتدة التالية:

2. طريقة البناء

• حدد حواف الرسم البياني G واحدة تلو الأخرى. بطريقة لا توجد دورات يتم إنشاؤها.
• كرر هذه العملية حتى يتم تضمين كافة القمم.

مثال

النظر في الرسم البياني التالي G،

• اختر الحافة أب ,

• اختر الحافة ل ,

• بعد ذلك، اختر الحافة المفوضية الأوروبية ,

• بعد ذلك، اختر الحافة سي بي ثم أخيرًا نحصل على الشجرة الممتدة التالية:

رتبة الدائرة

عدد الحواف التي نحتاج إلى حذفها من G للحصول على شجرة ممتدة.

الشجرة الممتدة G = m- (n-1) ، والذي يسمى رتبة الدائرة من ز.

 Where, m = No. of edges. n = No. of vertices. 

مثال

في الرسم البياني أعلاه، الحواف m = 7 والقمم n = 5

ثم رتبة الدائرة هي ،

 G = m - (n - 1) = 7 - (5 - 1) = 3