الشجرة الممتدة للرسم البياني هي رسم بياني فرعي يحتوي على جميع رؤوس الرسم البياني الأصلي ، ولكن بدون دورات. يعد العثور على الشجرة الممتدة للرسم البياني إحدى المهام الأساسية في نظرية الرسم البياني. من المهم أن تتذكر أنه قد يكون هناك العديد من الأشجار الممتدة ، وسيتألف كل منها من نفس العدد من الرؤوس ، ولكن متصلة بحواف مختلفة.
هناك العديد من الخوارزميات التي تسمح لك بالعثور على جميع الأشجار الممتدة للرسم البياني. واحدة من الأكثر شعبية وسهلة الفهم هي خوارزمية كروسكال. يعتمد على نهج المتعة ، عندما تتم إضافة أصغر حافة في كل خطوة إلى الشجرة الممتدة التي لا تشكل دورة ذات حواف موجودة بالفعل.
الخطوة التالية هي الخوارزمية الأولية ، والتي تعتمد أيضا على اختيار أصغر حافة ، ولكن بالفعل من الرأس المحدد. يضمن أن الشجرة ستكون متصلة ، ويسمح لك بالعثور على شجرة ممتدة واحدة فقط من الرسم البياني.
الرسم البياني تمتد الأشجار لديها مجموعة واسعة من التطبيقات. يجدون تطبيقهم ، على سبيل المثال ، في تخطيط المسار ، في تحسين شبكات الاتصالات ، في خوارزميات البحث ، وكذلك في العديد من المجالات الأخرى. يعد فهم الخوارزميات الأساسية للعثور على الأشجار الممتدة للرسم البياني جزءا مهما من البرمجة وتحليل البيانات.
- تعريف الأشجار الممتدة
- خوارزمية كراسكال للعثور على الأشجار الممتدة
- مثال على استخدام خوارزمية كراسكال
- سؤال وجواب
- ما هي طرق العثور على جميع الأشجار الممتدة للرسم البياني?
- ما هي شجرة تمتد من الرسم البياني?
- ما هي التطبيقات التي تمتد الأشجار من الرسم البياني لها?
تعريف الأشجار الممتدة
في نظرية الرسم البياني ، الشجرة الممتدة هي رسم بياني فرعي لرسم بياني متصل معين يحتوي على جميع رؤوسه وفي نفس الوقت شجرة (أي لا تحتوي على دورات). الشجرة الممتدة للرسم البياني هي مجموعة فرعية صغيرة من حوافها التي تربط جميع رؤوسها. يحتوي على الحد الأدنى لعدد الحواف اللازمة لتوصيل الرسم البياني.
يمكن أن يحتوي الرسم البياني المتصل على العديد من الأشجار الممتدة. على سبيل المثال ، في حالة رسم بياني يحتوي على 4 رؤوس ، يمكنك إنشاء 3 أشجار ممتدة تحتوي على جميع الرؤوس الـ 4 ، ولكن لها عدد مختلف من الحواف.
تستخدم الأشجار الممتدة على نطاق واسع في مختلف المجالات مثل شبكات الاتصالات وأنظمة النقل وعلم الأحياء وغيرها. يتم استخدامها لتحسين والعثور على أصغر المسارات ، وبناء الحد الأدنى من الأشجار الممتدة للطرق والمهام الأخرى المتعلقة بالحد الأدنى من الهياكل المتصلة.
توجد خوارزميات مختلفة للبحث عن الأشجار الممتدة ، مثل الخوارزمية الأولية وخوارزمية كروسكال وخوارزمية بوروفكا. كل من هذه الخوارزميات لها مزاياها وعيوبها اعتمادا على حجم الرسم البياني وهيكله.
لذلك ، من المهم معرفة الطرق المختلفة للعثور على الأشجار الممتدة والقدرة على اختيار الخوارزمية الأنسب لمهمة محددة.
خوارزمية كراسكال للعثور على الأشجار الممتدة
خوارزمية كراسكال هي خوارزمية فعالة تستخدم للعثور على الحد الأدنى من الشجرة الممتدة في الرسم البياني المرجح. لأنه يقوم على استراتيجية اختيار حافة الجشع ويمكن استخدامها للبحث عن جميع الأشجار الممتدة في الرسم البياني.
فيما يلي تسلسل خطوات خوارزمية كراسكال:
- قم بإنشاء قائمة بجميع حواف الرسم البياني وفرزها عن طريق زيادة الوزن.
- إنشاء مجموعة فارغة من مست تمتد الأشجار (الحد الأدنى تمتد الأشجار).
- لكل حافة ، بدءا من الأخف ، اتبع الخطوات التالية:
- كرر الخطوة 3 حتى يصبح مست شجرة تمتد من الرسم البياني.
- إرجاع مست نتيجة لتنفيذ الخوارزمية.
تعتمد خوارزمية كراسكال على فكرتين أساسيتين: فرز الحواف وفحص الدورة. لديها الخصائص التالية:
- تم تصميم خوارزمية كراسكال للعمل مع الرسوم البيانية المرجحة ، أي الرسوم البيانية التي يكون لكل حافة فيها وزن عددي.
- تعمل الخوارزمية مع جميع أنواع الرسوم البيانية ، بما في ذلك الرسوم البيانية غير المتصلة.
- إذا كان الرسم البياني يحتوي على عدة مجموعات من الحواف بنفس الأوزان ، فقد تعطي الخوارزمية نتائج مختلفة ، ولكن جميعها ستكون ضئيلة.
تعد خوارزمية كراسكال واحدة من أكثر الطرق شيوعا للبحث عن الأشجار الممتدة في الرسم البياني. جنبا إلى جنب مع سهولة التنفيذ والكفاءة ، بل هو خيار جيد لمعظم المهام التي تتطلب البحث عن الأشجار الممتدة.
مثال على استخدام خوارزمية كراسكال
خوارزمية كراسكال هي إحدى الطرق للعثور على الحد الأدنى من الشجرة الممتدة في الرسم البياني. يعتمد على استراتيجية جشعة وهو مصمم للرسوم البيانية المرجحة حيث يكون للحواف أوزان أو تكاليف معينة.
لنلق نظرة على مثال لاستخدام خوارزمية كراسكال في الرسم البياني التالي:
أ - - - - - ب
| \ |
| \ |
| \ |
ج - - - - - د
5
في هذا المثال ، يحتوي الرسم البياني على أربعة رؤوس (أ ، ب ، ج ، د) وثلاثة حواف (أب ، أس ، بد). كل حافة لها تكلفة محددة:
- أب — 1
- إيه سي-2
- دينار بحريني-5
لنطبق خوارزمية كراسكال لإيجاد الحد الأدنى لشجرة الامتداد في هذا الرسم البياني:
- نقوم بفرز جميع الحواف بترتيب تصاعدي للأوزان.
- نبدأ مع شجرة تمتد فارغة وإضافة حواف في ترتيب الأوزان المتزايدة.
- أضف الحافة التالية بأقل وزن (تيار متردد).
- إضافة الحافة الأخيرة (دينار بحريني).
| الحافة | الوزن |
|---|---|
| أب | 1 |
| أس | 2 |
| دينار بحريني | 5 |
| الشجرة الممتدة | الوزن |
|---|---|
| أب | 1 |
| الشجرة الممتدة | الوزن |
|---|---|
| أب | 1 |
| أس | 2 |
| الشجرة الممتدة | الوزن |
|---|---|
| أب | 1 |
| أس | 2 |
| دينار بحريني | 5 |
وهكذا ، فإن الحد الأدنى تمتد شجرة من هذا الرسم البياني يتكون من ثلاثة حواف: أب ، أس و بد. الوزن الإجمالي للشجرة الممتدة هو 8.
يوضح المثال المعطى كيف تعمل خوارزمية كراسكال على رسم بياني بسيط. ومع ذلك ، يمكن استخدام الخوارزمية لحل مشاكل أكثر تعقيدا والعثور على الحد الأدنى من الشجرة الممتدة في الرسوم البيانية الكبيرة مع عدد كبير من الرؤوس والحواف.
سؤال وجواب
ما هي طرق العثور على جميع الأشجار الممتدة للرسم البياني?
يمكن استخدام طرق مختلفة للبحث عن جميع الأشجار الممتدة للرسم البياني ، بما في ذلك البحث الكامل ، والخوارزميات القائمة على البحث عن العمق أو العرض ، والخوارزمية الأولية وخوارزمية كروسكال.
ما هي شجرة تمتد من الرسم البياني?
الشجرة الممتدة هي رسم بياني فرعي للرسم البياني الأصلي يتضمن جميع رؤوسه وهو رسم بياني غير دوري متصل بدون دورات.
ما هي التطبيقات التي يمتلكها الرسم البياني الممتد للأشجار?
تستخدم أشجار الرسم البياني الممتدة على نطاق واسع في مختلف المجالات مثل الاتصالات السلكية واللاسلكية والنقل وشبكات الكمبيوتر والمعلوماتية الحيوية وما إلى ذلك. يتم استخدامها لتحسين اتصالات الشبكة والعثور على أقصر المسارات وتحليل الكتلة والمزيد.