في هذه المقالة سنتحدث عن الشجرة الممتدة والحد الأدنى من الشجرة الممتدة. ولكن قبل الانتقال مباشرة نحو الشجرة الممتدة، دعونا نرى أولاً وصفًا موجزًا للرسم البياني وأنواعه.
رسم بياني
يمكن تعريف الرسم البياني على أنه مجموعة من القمم والحواف لربط هذه القمم. يتم إعطاء أنواع الرسوم البيانية على النحو التالي -
والآن لننتقل إلى موضوع الشجرة الممتدة.
ما هي الشجرة الممتدة؟
يمكن تعريف الشجرة الممتدة على أنها رسم بياني فرعي لرسم بياني متصل غير موجه. ويشمل جميع القمم مع أقل عدد ممكن من الحواف. إذا غاب أي قمة، فهي ليست شجرة ممتدة. الشجرة الممتدة هي مجموعة فرعية من الرسم البياني لا تحتوي على دورات، ولا يمكن أيضًا فصلها.
تتكون الشجرة الممتدة من (n-1) حواف، حيث 'n' هو عدد القمم (أو العقد). قد يكون أو لا يكون لحواف الشجرة الممتدة أوزان مخصصة لها. جميع الأشجار الممتدة المحتملة التي تم إنشاؤها من الرسم البياني المعطى G سيكون لها نفس عدد القمم، لكن عدد الحواف في الشجرة الممتدة سيكون مساويًا لعدد القمم في الرسم البياني المعطى ناقص 1.
يمكن أن يكون هناك رسم بياني كامل غير موجه نن -2 عدد الأشجار الممتدة حيث ن هو عدد القمم في الرسم البياني. لنفترض، إذا ن = 5 ، سيكون الحد الأقصى لعدد الأشجار الممتدة الممكنة 55-2= 125.
تطبيقات الشجرة الممتدة
في الأساس، يتم استخدام الشجرة الممتدة للعثور على الحد الأدنى من المسار لربط جميع العقد في الرسم البياني. بعض التطبيقات الشائعة للشجرة الممتدة مدرجة على النحو التالي -
- التحليل العنقودي
- تخطيط الشبكات المدنية
- بروتوكول توجيه شبكة الكمبيوتر
الآن دعونا نفهم الشجرة الممتدة بمساعدة مثال.
مثال على الشجرة الممتدة
لنفترض أن الرسم البياني يكون -
كما نوقش أعلاه، تحتوي الشجرة الممتدة على نفس عدد القمم الموجودة في الرسم البياني، وعدد القمم في الرسم البياني أعلاه هو 5؛ وبالتالي فإن الشجرة الممتدة ستحتوي على 5 رؤوس. ستكون حواف الشجرة الممتدة مساوية لعدد القمم في الرسم البياني ناقص 1. لذا، سيكون هناك 4 حواف في الشجرة الممتدة.
فيما يلي بعض الأشجار الممتدة المحتملة التي سيتم إنشاؤها من الرسم البياني أعلاه -
خصائص الشجرة الممتدة
بعض خصائص الشجرة الممتدة مذكورة على النحو التالي -
- يمكن أن يكون هناك أكثر من شجرة ممتدة للرسم البياني المتصل G.
- لا تحتوي الشجرة الممتدة على أي دورات أو حلقة.
- الشجرة الممتدة هي متصل بالحد الأدنى, لذا فإن إزالة حافة واحدة من الشجرة سيؤدي إلى قطع الرسم البياني.
- الشجرة الممتدة هي الحد الأقصى غير الحلقي، لذا فإن إضافة حافة واحدة إلى الشجرة سيؤدي إلى إنشاء حلقة.
- يمكن أن يكون هناك الحد الأقصى نن -2 عدد الأشجار الممتدة التي يمكن إنشاؤها من رسم بياني كامل.
- هناك شجرة ممتدة ن-1 الحواف، حيث 'n' هو عدد العقد.
- إذا كان الرسم البياني عبارة عن رسم بياني كامل، فيمكن إنشاء الشجرة الممتدة عن طريق إزالة الحد الأقصى (e-n+1) من الحواف، حيث 'e' هو عدد الحواف و'n' هو عدد القمم.
لذا، فإن الشجرة الممتدة هي مجموعة فرعية من الرسم البياني المتصل G، ولا توجد شجرة ممتدة للرسم البياني المنفصل.
الحد الأدنى الشجرة الممتدة
يمكن تعريف الحد الأدنى من الشجرة الممتدة على أنها الشجرة الممتدة التي يكون فيها مجموع أوزان الحافة هو الحد الأدنى. وزن الشجرة الممتدة هو مجموع الأوزان الممنوحة لحواف الشجرة الممتدة. في العالم الحقيقي، يمكن اعتبار هذا الوزن بمثابة المسافة أو الحمل المروري أو الازدحام أو أي قيمة عشوائية.
مثال على الحد الأدنى من الشجرة الممتدة
دعونا نفهم الحد الأدنى من الشجرة الممتدة بمساعدة مثال.
مجموع حواف الرسم البياني أعلاه هو 16. الآن، بعض الأشجار الممتدة المحتملة التي تم إنشاؤها من الرسم البياني أعلاه هي -
لذا، فإن الحد الأدنى من الشجرة الممتدة التي تم تحديدها من الأشجار الممتدة أعلاه للرسم البياني الموزون المحدد هو -
تطبيقات الحد الأدنى من الشجرة الممتدة
يتم إعطاء تطبيقات الحد الأدنى من الشجرة الممتدة على النحو التالي -
- يمكن استخدام الحد الأدنى من الشجرة الممتدة لتصميم شبكات إمدادات المياه، وشبكات الاتصالات، والشبكات الكهربائية.
- ويمكن استخدامه للعثور على المسارات في الخريطة.
خوارزميات الحد الأدنى من الشجرة الممتدة
يمكن العثور على الحد الأدنى من الشجرة الممتدة من الرسم البياني الموزون باستخدام الخوارزميات الواردة أدناه -
- خوارزمية بريم
- خوارزمية كروسكال
دعونا نرى وصفًا موجزًا لكل من الخوارزميات المذكورة أعلاه.
خوارزمية بريم - إنها خوارزمية جشعة تبدأ بشجرة ممتدة فارغة. يتم استخدامه للعثور على الحد الأدنى من الشجرة الممتدة من الرسم البياني. تعثر هذه الخوارزمية على المجموعة الفرعية من الحواف التي تتضمن كل قمة في الرسم البياني بحيث يمكن تقليل مجموع أوزان الحواف إلى الحد الأدنى.
ترتيب SQL عشوائيا
لمعرفة المزيد حول خوارزمية Prim، يمكنك النقر على الرابط أدناه - https://www.javatpoint.com/prim-algorithm
خوارزمية كروسكال - تُستخدم هذه الخوارزمية أيضًا للعثور على الحد الأدنى من الشجرة الممتدة للرسم البياني الموزون المتصل. تتبع خوارزمية كروسكال أيضًا النهج الجشع، الذي يجد الحل الأمثل في كل مرحلة بدلاً من التركيز على الحل الأمثل العالمي.
لمعرفة المزيد حول خوارزمية Prim، يمكنك النقر على الرابط أدناه - https://www.javatpoint.com/kruskal-algorithm
لذلك، هذا كل ما في هذه المادة. نأمل أن تكون المقالة مفيدة وغنية بالمعلومات لك. لقد ناقشنا هنا الشجرة الممتدة والحد الأدنى من الشجرة الممتدة بالإضافة إلى خصائصها وأمثلتها وتطبيقاتها.