شجرة ممتدة

إضافة حافة واحدة فقط إلى شجرة ممتدة تُنشئ دورة؛ تُسمى هذه الدورة دورة أساسية بالنسبة لتلك الشجرة. توجد دورة أساسية مميزة لكل حافة غير موجودة في الشجرة الممتدة؛ وبالتالي، توجد علاقة تناظرية بين الدورات الأساسية والحواف غير الموجودة في الشجرة الممتدة. بالنسبة لرسم بياني متصل ذي V رأسًا، فإن أي شجرة ممتدة ستحتوي على V  −  1 حافة، وبالتالي، فإن رسمًا بيانيًا مكونًا من E حافة وإحدى أشجاره الممتدة سيحتوي على E  − V + 1 دورة أساسية (عدد الحواف مطروحًا منه عدد الحواف الموجودة في الشجرة الممتدة؛ مما يعطي عدد الحواف غير الموجودة في الشجرة الممتدة). بالنسبة لأي شجرة ممتدة معينة ، تُشكل مجموعة جميع الدورات الأساسية E − V + 1 أساسًا للدورات ، أي أساسًا لفضاء الدورات . ^{[ 5 ]}       

يُقابل مفهوم الدورة الأساسية مفهوم مجموعة القطع الأساسية بالنسبة لشجرة ممتدة معينة. بحذف حافة واحدة فقط من الشجرة الممتدة، تُقسّم الرؤوس إلى مجموعتين منفصلتين. تُعرَّف مجموعة القطع الأساسية بأنها مجموعة الحواف التي يجب إزالتها من الرسم البياني G لتحقيق التقسيم نفسه. بالتالي، تُحدد كل شجرة ممتدة مجموعة من V  −  1 مجموعة قطع أساسية، واحدة لكل حافة من حواف الشجرة الممتدة. ^{[ 6 ]}

تُثبت الازدواجية بين مجموعات القطع الأساسية والدورات الأساسية من خلال ملاحظة أن حواف الدورة غير الموجودة في الشجرة الممتدة لا يمكن أن تظهر إلا في مجموعات القطع الخاصة بالحواف الأخرى في الدورة؛ والعكس صحيح : لا يمكن أن تظهر الحواف في مجموعة قطع إلا في الدورات التي تحتوي على الحافة المقابلة لتلك المجموعة. ويمكن التعبير عن هذه الازدواجية أيضًا باستخدام نظرية الماترويدات ، حيث تُعتبر الشجرة الممتدة أساسًا للماترويد الرسومي ، والدورة الأساسية هي الدائرة الوحيدة ضمن المجموعة المُشكّلة بإضافة عنصر واحد إلى الأساس، وتُعرّف مجموعات القطع الأساسية بنفس الطريقة من الماترويد الثنائي . ^{[ 7 ]}

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

• تُعرّف معظم كتب ومقالات نظرية الرسوم البيانية الغابة الممتدة بأنها غابة تمتد على جميع رؤوس الرسم البياني، أي أن كل رأس من رؤوس الرسم البياني هو رأس في هذه الغابة. وقد يحتوي الرسم البياني المتصل على غابة ممتدة غير متصلة، مثل الغابة التي لا تحتوي على حواف، حيث يشكل كل رأس شجرة ذات رأس واحد. ^{[ 8 ] [ 9 ]}

• يعرّف بعض مؤلفي نظرية الرسم البياني الغابة الممتدة بأنها رسم بياني فرعي غير دوري أقصى للرسم البياني المعطى، أو بشكل مكافئ رسم بياني فرعي يتكون من شجرة ممتدة في كل مكون متصل من الرسم البياني. ^{[ 10 ]}

لتجنب الخلط بين هذين التعريفين، يقترح غروس ويلين (2005) مصطلح "الغابة الممتدة الكاملة" للغابة الممتدة التي لها نفس عدد المكونات الموجودة في الرسم البياني المعطى (أي الغابة القصوى)، بينما يطلق بوندي ومورتي (2008) على هذا النوع من الغابات اسم "الغابة الممتدة القصوى" (وهو مصطلح زائد، لأن الغابة القصوى تحتوي بالضرورة على كل رأس). ^{[ 11 ]}

في بعض الحالات، من السهل حساب t ( G ) مباشرة:

• إذا كانت G شجرة بحد ذاتها، فإن t ( G )  =  1 .
• عندما يكون G هو الرسم البياني الدوري C _n مع n رأسًا، فإن t ( G )  = n  .
• بالنسبة للرسم البياني الكامل الذي يحتوي على n رأسًا، فإن صيغة كايلي ^{[ 12 ]} تعطي عدد الأشجار الممتدة على النحو التالي: n ^{n  −  2} .
• إذا كان G هو الرسم البياني الثنائي الكامل${\displaystyle K_{p,q}}$،ثم${\displaystyle t(G)=p^{q-1}q^{p-1}}$[ ^{8 ]​}
• بالنسبة للرسم البياني المكعب الفائق ذي الأبعاد n${\displaystyle Q_{n}}$[ ^{13 ]} عدد الأشجار الممتدة ^هو${\displaystyle t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}}$.

وبشكل أكثر عمومية، بالنسبة لأي رسم بياني G ، يمكن حساب العدد t ( G ) في وقت متعدد الحدود كمحدد لمصفوفة مشتقة من الرسم البياني، باستخدام نظرية كيرشوف للمصفوفة والشجرة . ^{[ 14 ]}

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

• درجة الرأس i ، إذا كان i  = j ، 
• -1، إذا كان الرأسان i و j متجاورين، أو
• 0، إذا كانت الرؤوس i و j مختلفة عن بعضها البعض ولكنها ليست متجاورة.

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

إذا كان G رسمًا بيانيًا أو رسمًا بيانيًا متعددًا ، وكان e ضلعًا عشوائيًا في G ، فإن عدد الأشجار الممتدة لـ G ، t ( G )، يحقق العلاقة التكرارية للحذف والانكماش t ( G ) = t ( G - e ) + t ( G / e )، حيث G - e هو الرسم البياني المتعدد الناتج عن حذف e، و G / e هو انكماش G بواسطة e . ^{[ 15 ]} يحسب الحد t ( G - e ) في هذه الصيغة الأشجار الممتدة لـ G التي لا تستخدم الضلع e ، بينما يحسب الحد t ( G / e ) الأشجار الممتدة لـ G التي تستخدم e .              

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

يمكن تعريف متعددة حدود توت للرسم البياني على أنها مجموع، على الأشجار الممتدة للرسم البياني، لحدود محسوبة من "النشاط الداخلي" و"النشاط الخارجي" للشجرة. وقيمتها عند الوسيطين (1،1) هي عدد الأشجار الممتدة، أو في الرسم البياني غير المتصل، عدد الغابات الممتدة القصوى. ^{[ 16 ]}

يمكن أيضًا حساب متعددة حدود توت باستخدام علاقة تكرارية للحذف والانكماش، لكن تعقيدها الحسابي مرتفع: بالنسبة للعديد من قيم وسيطاتها، فإن حسابها بدقة يُعدّ مسألة كاملة من فئة #P ، كما يصعب تقريبها بنسبة تقريب مضمونة . تُعدّ النقطة (1,1)، التي يمكن عندها تقييمها باستخدام نظرية كيرشوف، إحدى الاستثناءات القليلة. ^{[ 17 ]}

يمكن إيجاد شجرة ممتدة واحدة لرسم بياني في زمن خطي باستخدام خوارزمية البحث العميق أولًا أو خوارزمية البحث العرضي أولًا . تستكشف كلتا الخوارزميتين الرسم البياني المُعطى، بدءًا من رأس عشوائي v ، من خلال المرور على جيران الرؤوس المكتشفة وإضافة كل جار غير مستكشف إلى بنية بيانات ليتم استكشافه لاحقًا. يكمن الاختلاف بينهما في ما إذا كانت بنية البيانات هذه عبارة عن مكدس (في حالة البحث العميق أولًا) أو طابور (في حالة البحث العرضي أولًا). في كلتا الحالتين، يمكن تكوين شجرة ممتدة عن طريق ربط كل رأس، باستثناء رأس الجذر v ، بالرأس الذي تم اكتشافه منه. تُعرف هذه الشجرة بشجرة البحث العميق أولًا أو شجرة البحث العرضي أولًا وفقًا لخوارزمية استكشاف الرسم البياني المستخدمة في بنائها. ^{[ 18 ]} تُعد أشجار البحث العميق أولًا حالة خاصة من فئة أشجار ممتدة تُسمى أشجار تريموكس ، نسبةً إلى مكتشف البحث العميق أولًا في القرن التاسع عشر. ^{[ 19 ]}

تُعدّ الأشجار الممتدة مهمة في الحوسبة المتوازية والموزعة، كوسيلة للحفاظ على الاتصالات بين مجموعة من المعالجات؛ انظر على سبيل المثال بروتوكول الشجرة الممتدة المستخدم في أجهزة طبقة الربط في نموذج OSI، أو بروتوكول Shout للحوسبة الموزعة. مع ذلك، فإنّ طريقتي البحث في العمق أولًا والبحث في العرض أولًا لبناء الأشجار الممتدة على الحواسيب التسلسلية غير مناسبتين للحواسيب المتوازية والموزعة. ^{[ 20 ]} بدلًا من ذلك، ابتكر الباحثون العديد من الخوارزميات المتخصصة لإيجاد الأشجار الممتدة في هذه النماذج من الحوسبة. ^{[ 21 ]}

في بعض مجالات نظرية المخططات، من المفيد غالبًا إيجاد شجرة ممتدة دنيا لمخطط مُثقَّل . كما دُرست مسائل تحسين أخرى على الأشجار الممتدة، بما في ذلك الشجرة الممتدة القصوى، والشجرة الدنيا التي تمتد على الأقل k رأسًا، والشجرة الممتدة ذات أقل عدد من الحواف لكل رأس ، والشجرة الممتدة ذات أكبر عدد من الأوراق ، والشجرة الممتدة ذات أقل عدد من الأوراق (المرتبطة ارتباطًا وثيقًا بمسألة المسار الهاميلتوني )، والشجرة الممتدة ذات القطر الأدنى ، والشجرة الممتدة ذات التمدد الأدنى. ^{[ 22 ] [ 23 ]}

تمت دراسة مسائل الشجرة الممتدة المثلى أيضًا لمجموعات محدودة من النقاط في فضاء هندسي مثل المستوى الإقليدي . بالنسبة لهذا المدخل، فإن الشجرة الممتدة هي شجرة رؤوسها هي النقاط المعطاة. تُقاس جودة الشجرة بنفس طريقة قياسها في الرسم البياني، باستخدام المسافة الإقليدية بين أزواج النقاط كوزن لكل حافة. ​​وبالتالي، على سبيل المثال، فإن الشجرة الممتدة الدنيا الإقليدية هي نفسها الشجرة الممتدة الدنيا في رسم بياني كامل بأوزان حواف إقليدية. مع ذلك، ليس من الضروري إنشاء هذا الرسم البياني لحل مسألة التحسين؛ إذ يمكن حل مسألة الشجرة الممتدة الدنيا الإقليدية، على سبيل المثال، بكفاءة أكبر في زمن O ( n  log n ) عن طريق إنشاء تثليث ديلاوناي ثم تطبيق خوارزمية الشجرة الممتدة الدنيا المستوية ذات الزمن الخطي على التثليث الناتج. ^{[ 22 ]} 

تُسمى الشجرة الممتدة المختارة عشوائيًا من بين جميع الأشجار الممتدة باحتمالية متساوية شجرة ممتدة منتظمة . يمكن استخدام خوارزمية ويلسون لتوليد أشجار ممتدة منتظمة في وقت متعدد الحدود من خلال عملية إجراء مسار عشوائي على الرسم البياني المعطى ومسح الدورات الناتجة عن هذا المسار. ^{[ 24 ]}

يُعدّ نموذج الشجرة الممتدة الدنيا العشوائية نموذجًا بديلًا لتوليد الأشجار الممتدة عشوائيًا ولكن ليس بشكل منتظم . في هذا النموذج، تُسند أوزان عشوائية إلى حواف الرسم البياني، ثم تُنشأ الشجرة الممتدة الدنيا للرسم البياني الموزون. ^{[ 25 ]}

نظرًا لأن الرسم البياني قد يحتوي على عدد هائل من الأشجار الممتدة، فإنه من غير الممكن سردها جميعًا في وقت متعدد الحدود . ومع ذلك، توجد خوارزميات معروفة لسرد جميع الأشجار الممتدة في وقت متعدد الحدود لكل شجرة. ^{[ 26 ]}