كتب count the sprawling trees
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
عد الأشجار الممتدة (معلومة)
في الرسوم البيانية الاختيارية
المقال الرئيسي:نظرية كيرشوف بشكل أعم، لأي 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 (، التي يمكن أن تكون في تقييم استخدام بريشوف، هي واحدة من الاستثناءات القليلة.
