حساب إجمالي عدد الأشجار الممتدة التي تحتوي على مجموعة معينة من الحواف

Question

لقد جربت النهج التالي:

أولاً ، أقوم بتقلص الحافة لجميع الحواف في مجموعة الحواف المحددة لتشكيل رسم بياني معدّل.

ثم أحسب العدد الإجمالي لأشجار الامتداد ، باستخدام نظرية شجرة المصفوفة ، من الرسم البياني المعدل.

أريد أن أعرف ما إذا كانت هذه الطريقة صحيحة وإذا كانت هناك طرق أخرى أفضل.

Answer 1

دع G يكون رسمًا بيانيًا ، ودع e يكون حافة ، ودع g/e هو نفس الرسم البياني مع e التعاقد. ثم،

الاقتراح: هناك تعويض بين الأشجار الممتدة لـ G التي تحتوي على E ، وأشجار تمتد لـ G/E.

هذا الاقتراح ليس من الصعب إثباته ؛ من الأفضل أن تفهم إثبات نفسك بدلاً من مجرد سؤال الآخرين عما إذا كان هذا صحيحًا. من الواضح أنه إذا كان لديك شجرة T من G التي تحتوي على E ، فإن T/E هي شجرة تمتد من G/E. الشيء الذي يجب التفكير فيه هو أنه يمكنك أيضًا العودة إلى الوراء.

وكما يشير آدم ، عليك أن تكون حريصًا على التعامل مع الرسوم البيانية بشكل صحيح مع حواف متوازية ورسوم بيانية ذات حواف من قمة الرأس إلى نفسها.

Answer 2

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