شجرة متفرعة: الفرق بين النسختين

في مجال [[نظرية المخططات]]، '''الشجرة المتفرعة''' {{إنج|spanning tree}} هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر.<ref>{{مرجعاستشهاد ويب| مسار = https://babelnet.org/synset?word=bn:03217203n | عنوان = معلومات عن شجرة متفرعة على موقع babelnet.org | ناشر = babelnet.org|مسار أرشيف= https://web.archive.org/web/20191209141038/https://babelnet.org/synset?word=bn:03217203n|تاريخ أرشيف=2019-12-09}}</ref><ref>{{مرجعاستشهاد ويب| مسار = https://id.loc.gov/authorities/sh2005003951 | عنوان = معلومات عن شجرة متفرعة على موقع id.loc.gov | ناشر = id.loc.gov|مسار أرشيف= https://web.archive.org/web/20191209141040/https://id.loc.gov/authorities/sh2005003951|تاريخ أرشيف=2019-12-09}}</ref>

الإنترنت والعديد من شبكات الاتصالات السلكية واللاسلكية الأخرى لديها صلات الإرسال التي تربط العقد معا في الهندسهالهندسة اللا كميه شبكة تضم بعض الحلقات. من أجل "تجنب الحلقات"، والعديد من بروتوكولات التوجيه مصممة لمثل هذه الشبكات—بما في ذلك [[بروتوكول الشجرة الممتدة]]، فتح مسار أقصر أولا، بروتوكول التوجيه حاله الارتباط، المعزز التوجيه القائم على شجرة....... الخ - يتطلب كل جهاز التوجيه لتذكر الشجرة الممتدة.

الشجرهالشجرة هي عباره عن مخطط متصل غير مباشر لا يوجد به اي حلقات. تسمي شجره الامتداد للمخطط G . إذا كان يمتد G (أي أنه يشمل كل قمة من G)، وهو مخطط ثانوي من G (كل حافة في شجرة تنتمي إلى G). شجره امتداد للمخطط G يمكن ان تعرف ايضا بانها المجموعة القصوى من حواف G التي لا تحتوي على دورة، أو مجموعة صغيرة من الحواف التي تربط بين جميع القمم.

الفكرهالفكرة المزدوجة لفكره الحلقات الأساسية هي فكرة مجموعة القطع الأساسية فبحذف حافه واحده من شجرة الامتداد يتم تقسيم القمم إلى مجموعتين متصلتين . مجموعة القطع الأساسية تعرف علي انها مجنوعة الحواف التي يلزم حذفها من ال مخطط G لانجاز نفس القسم . وهكذا فان كل جرة امتداد تعرف بمجموعه من القطع الاساسيه V-1 . واحده لكل حافة في شجرة الامتداد .

الحواف في ال cutset يمكنها الظهور فقط في الحلقات التي تحتوي الحواف المقابلهالمقابلة لل cutset. ويمكن أيضا أن تتجلى هذه الازدواجية باستخدام نظرية matroid. التي تنص علي ان الشجرهالشجرة هي قاعدد matroid . الحلقة الأساسية هي دائرة فريدة من نوعها ضمن مجموعة شكلت من خلال إضافة عنصر واحد إلى قاعدة. وتعرف مجموهة القطع الأساسية بنفس الطريقة من matroid.

• البعض الاخر من المؤلفين . الغابهالغابة الممتدة هي غابه تمتد الي جميع القمم والتي تعني ان كل قمة في الجراف هي قمة للغابة الممتدة. في هذا التعريف حتي في المخططات المتصلة يمكن ان تحتوي علي غابات ممتدة غير متصلة

• في حالة G هي نفسها شجرة ،شجرة، بالتالي t(G)=1

شجرة واحدة ممتدة يمكن العثور عليها في الزمن الخطي من الرسم البياني عن طريق احدي التقنيات depth-first search اوأو breadth-first search. كل من هذه الخوارزميات حلل رسم البياني معين، بدءا من قمة رأس الرسم ،الرسم، من خلال المرور في حلقات عبر النقط المجاورة من القمم يكتشفون وإضافة كل الجيران غير مستكشفة إلى بنية بيانات من يكتشفها في وقت لاحق. وهي تختلف في ما إذا كانت هذه البنية البيانات كومة (في حالة من البحث المتعمق الأول) أو طابور (في حالة بحث-اتساع الأول). في كلتا الحالتين، يمكن للمرء أن تشكيل شجرة تمتد من خلال ربط كل قمة، وغيرها من قمة الجذر الخامس، إلى قمة الرأس الذي تم اكتشافه. هذه الشجرة المعروفة باسم شجرة البحث المتعمق الأول أو شجرة البحث-اتساع الأول وفقا لخوارزمية التنقيب الرسم البياني تستخدم لبناء عليه. أشجار البحث المتعمق الأولى هي حالة خاصة من فئة الأشجار الممتدة يسمى شجرة تريماو ،تريماو، الذي سمي على اسم مكتشف القرن 19 للبحث المتعمق الأول.

في مجالات معينة من نظرية الرسم البياني غالبا ما يكون من المفيد ايجاد اقل شجرة ممتدة من شكل ذو اوزان مختلفه . كما تم دراسة مشاكل نمذجه أخرى على الأشجار الممتدة، بما في ذلك مشاكل ايجاد الحد الأقصى من الشجرة الممتدة، والحد الأدنى الشجرة التي تمتد على القمم ك ،ك، والشجرة الممتدة مع أقل عدد من حواف لكل قمه ،قمه، والشجرة الممتدة مع أكبر عدد من الأوراق، والشجرة الممتدة مع أقل عدد من الأوراق (ترتبط ارتباطا وثيقا مشكلة مسار هاميلتون)، مشكله اقل قطر للشجرة الممتدة ،الممتدة، والحد الأدنى من اتساع الشجرة الممتدة. [19] [20]

كما تم دراسة المشاكل التي تختص بدراسه مشاكل الشجرة الممتدة المثلي لمجموعات محدودة من النقاط في هندسه الفضاء مثل نضريه اقليدس. لمثل هذا الإدخال، شجرة تمتد مرة اخرى الشجرة التي لديها كما رؤوسه على نقاط معينة. يتم قياس جودة الشجرة بنفس الطريقة كما في الرسم البياني، وذلك باستخدام المسافة الإقليدية بين أزواج من نقطة لوزن لكل حافة. وهكذا، على سبيل المثال، اقل شجرة ممتدة علي الطريقهالطريقة الاقليديه هي نفسها اقل شجرة ممتدة في رسم بياني كامل مع اوزان الحافهالحافة الاقليديه ومع ذلك، فإنه ليس من الضروري لبناء هذا الرسم البياني من أجل حل مشكله النمذجهالنمذجة. مشكله اقل امتداد اقليدي للشجرة، على سبيل المثال، لا يمكن حل أكثر كفاءة في O (ن تسجيل ن) الوقت من خلال إنشاء التثليث ديلوناي ثم تطبيق الزمن الخطي الرسم البياني مستو أدنى تمتد خوارزمية الشجرة إلى التثليث الناتجة عن ذلك.

لأن الرسم البياني قد يحتوي علي أضعافا مضاعفة من الاشجار الممتدة ،الممتدة، فإنه ليس من الممكن ذكرها جميعا في الوقت متعدد الحدود. ومع ذلك،يتمذلك، يتم استخدام خوارزميات لإدراج جميع الأشجار التي تغطي في الوقت متعدد الحدود لكل شجرة.