الرسم البياني الفرعي الممتد هورسم بياني فرعي يحتوي على جميع رؤوس الرسم البياني الأصلي. الشجرة الممتدة هي رسم بياني فرعي ممتد غالبًا ما يكون موضع اهتمام. تسمى الدورة في الرسم البياني التي تحتوي على جميع رؤوس الرسم البياني بدورة ممتدة.
كم عدد الرسوم البيانية الفرعية الممتدة هناك؟
هناك 2n الرسوم البيانية الفرعية المستحثة (جميع المجموعات الفرعية للرؤوس) و2m الرسوم البيانية الفرعية الممتدة(جميع المجموعات الفرعية من الحواف).
كيف أجد الرسم البياني الفرعي الممتد؟
وبحسب تعريف الرسم البياني الفرعي الممتد للرسم البياني G هو رسم بياني فرعيتم الحصول عليه عن طريق حذف الحافة فقط. إذا قمنا بإنشاء مجموعات فرعية من الحواف عن طريق حذف حافة واحدة وحافتين وثلاث حواف وما إلى ذلك. نظرًا لوجود حواف m ، فهناك 2 ^ m مجموعات فرعية. ومن ثم فإن G لديها 2 ^ م الرسوم الفرعية الممتدة.
ما المقصود بامتداد الشجرة؟
الشجرة الممتدة للرسم البياني (G) هيمجموعة فرعية من G تغطي جميع رؤوسها باستخدام الحد الأدنى لعدد الحواف. يمكن استنتاج بعض خصائص الشجرة الممتدة من هذا التعريف: بما أن "الشجرة الممتدة تغطي جميع الرؤوس" ، فلا يمكن فصلها.
ما هي نظرية الرسم البياني الممتد؟
الشجرة الممتدة هي مجموعة فرعية من الرسم البياني G ، الذي يحتويعلى جميع الرؤوس مغطاة بأقل عدد ممكن من الحواف. ومن ثم ، لا تحتوي الشجرة الممتدة على دورات ولا يمكن فصلها.. من خلال هذا التعريف ، يمكننا استنتاج أن كل رسم بياني G متصل وغير موجه له على الأقل شجرة ممتدة واحدة.
