شجرة متفرعة

A spanning tree (blue heavy edges) of a grid graph

في مجال نظرية المخططات، الشجرة المتفرعة (بالإنجليزية: spanning tree)‏ هي مخطط بياني يضم مجموعة من العقد والحواف التي تسمى أغصاناً، تتصل هذه العقد مع بعضها البعض بشكل متفرع من نقطة مركزية تسمى الجذر.

تطبيقات

العديد من الخوارزميات الاستطلاعية بما فيهم خوارزمية ديكسترا وخوارزمية البحث بأولوية الأفضل(A* algorithm). تقوم ببناء شجره امتداد داخليه تعد خطوة وسيطه في حل المشكلات. من أجل تقليل تكلفة شبكات الكهرباء، وصلات الأسلاك، الأنابيب، التعرف على الكلام التلقائي....الخ. الناس غالبا ما تستخدم خوارزميات التي تبني تدريجيا الشجرة الممتدة (أو الكثير من هذه الأشجار) كخطوة وسيطة في عملية إيجاد الحد الأدنى من الشجرة الممتدة. الإنترنت والعديد من شبكات الاتصالات السلكية واللاسلكية الأخرى لديها صلات الإرسال التي تربط العقد معا في الهندسة اللا كميه شبكة تضم بعض الحلقات. من أجل «تجنب الحلقات»، والعديد من بروتوكولات التوجيه مصممة لمثل هذه الشبكات—بما في ذلك بروتوكول الشجرة الممتدة، فتح مسار أقصر أولا، بروتوكول التوجيه حاله الارتباط، المعزز التوجيه القائم على شجرة....... الخ - يتطلب كل جهاز التوجيه لتذكر الشجرة الممتدة.

تعريفات

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

حلقات اساسيه

إضافة حافه واحده الي شجرة امتداد يتسبب في تكوين حلقه؛ كل حلقه تسمي حلقه أساسية. توجد حلقات أساسية متميزة لكل حافة؛ هكذا، يوجد تطابق بين الحلقات الاساسيه والحواف التي لا تنتمي الي شجرة الامتداد. بالنسبة الي المخططات المتصلة التي بقي قمم V . أي شجرة امتداد سوف تحتوي علي عدد من الحواف يكافئV-1 . وهكذا فان المخطط الذي يحتوي على عدد E من الحواف واحدي شجرة الامتداد لهذا المخطط يحتوي على E-V+1 من الحلقات الأساسية. لأي شجرة امتداد معطاه فان المجموع ل E-V+1 من الحلقات الأساسيه يكون ما يسمي ب cycle basis (قاعدة الحلقات)

مجموعه القطع الاساسيه

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

الغابات الممتدة

في المخطوطات الغير متصله. يمكن الا يوجد أي شجره ممتده بدلا عن ذلك واحده يجب ان تعتبر غابه ممتدة. يوجده هنا تعريفين • بعض المؤلفين يعتبروا الغابة الممتدة علي انها عدد المخطوطات الفرعيه الدائريه القصوي للمخطط المعطي. أو بشكل مكافئ مخطوطة تتكون من شجره ممتدة في كل مكون متصل من المخطط. • البعض الآخر من المؤلفين. الغابة الممتدة هي غابه تمتد الي جميع القمم والتي تعني ان كل قمة في الجراف هي قمة للغابة الممتدة. في هذا التعريف حتي في المخططات المتصلة يمكن ان تحتوي علي غابات ممتدة غير متصلة لتجنب التشتت بين التعريفين اقترح Gross &Yellen (2005) الجزء المسمي "full spanning forest" للغابات الممتدة التي لها نفس التواصل بينما بدلا من ذلك أطلق Bondy&Murty (2008) علي هذا النوع من الغابات الممتده اسم "maximal spanning forest" الغابات الممتدة القصوي.

عد الأشجار الممتدة

صيغة كايلي عدد الاشجار الممتدة من رسم بياني متصل t(G) هو مدروسة ثابتة. في الرسوم البيانية المحددة في بعض الحالات، من السهل حساب t(G) مباشرة: • في حالة G هي نفسها شجرة، بالتالي t(G)=1 • في حالة G هي “cyclic graph(Cn)”يحتوي علي عدد n من القمم، بالتالي t(G)=n • في الرسم البياني الكامل مع عدد رؤوس n، Cayley's formula يعطي عدد الأشجار الممتدة nn-2 • في حالة G هي "complete bipartite graph " Kp،qبالتالي t(G)=pq-1qp-1 • في حالة عدد ابعاد nhypercube graphQn عدد الاشجار الممتدة هو $2^{2-2}=1$ trees in $K_2$, $3^{3-2}=3$ trees in $K_3$, and $4^{4-2}=16$ trees in $K_4$.

في الرسوم البيانية الاختيارية

المقال الرئيسي: نظرية كيرشوف بشكل أعم، لأي G الرسم البياني، عدد (G)t ويمكن حساب في الوقت متعدد الحدود كمحدد مصفوفة المستمدة من الرسم البياني، وذلك باستخدام مصفوفة شجرة نظرية كيرشوف.

على وجه التحديد، لحساب (G)t، واحد يبني مصفوفة مربعة فيها الصفوف والأعمدة على حد سواء فهرستها من قبل القمم G. الإدخال في الصف الأول والعمود ي هي واحدة من ثلاث قيم:

• درجة قمة i، وإذا كانت i=j • -1 إذا القمم i وjمتجاورين • صفر إذا القمم i وj تختلف عن بعضها البعض ولكن غير متجاورة. • المصفوفة الناتجة تكون مفردة، بحيث المحدد لها يساوي صفر. ومع ذلك، حذف الصفوف والأعمدة لقمة مختارة عشوائيا يؤدي إلى مصفوفة الأصغر التي المحدد هو بالضبط (G)t.

حذف - تقليص

إذا G هو رسم بياني أو multigraph والبريد هي ميزة التعسفية للG، ثم ر رقم (G) لتغطي أشجار G يرضي ر الحذف انكماش تكرار (G) = ر (G - ه) + ر (G / ه)، حيث G - e هو multigraph التي تم الحصول عليها عن طريق حذف البريد وG / ه هو انكماش G عن طريق البريد [12] ور مصطلح (G - ه) في هذه الصيغة بحساب أشجار تمتد من G التي لا تستخدم حافة الإلكترونية، ور مصطلح (G / ه) بحساب أشجار تمتد من G التي تستخدم البريد.

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

Tutteمتعددة الحدود

على tutte polynomial على الرسم البياني يمكن تعريفها بأنها مبلغ أكثر من الأشجار الممتدة على الرسم البياني من حيث يحسب من "الداخلية" و"الخارجية" من الشجرة. قيمته في الحجج)1,1(في عدد من الأشجار الممتدة أو، في حالات فصل الرسم البياني، على عدد من أقصى تغطي الغابات"

tutte polynomial أيضا يمكن أن يحسب باستخدام حذف - تقلص تكرار لكن التعقيد الحسابي هو: على العديد من القيم من حجج، بالتحديد هو رقم ف كامل ومن الصعب الاقتراب مع ضمان نسبة التقريب.)1,1 (، التي يمكن أن تكون في تقييم استخدام بريشوف، هي واحدة من الاستثناءات القليلة.

الخواروميات

بناء

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

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

النمذجة

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

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

التوزيع العشوائي

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

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

التعدد

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

في الرسوم البيانية لانهائية

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

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

في الاتجاه الآخر، نظرا لأسرة مكونة من مجموعات، فمن الممكن لبناء الرسم البياني لانهائي بحيث كل شجرة تمتد من الرسم البياني يتوافق مع وظيفة الاختيار من عائلة مجموعات. لذلك، إذا كل رسم بياني متصل لانهائي لديه شجرة الممتدة، ثم مسلمة الاختيار صحيح.