شجرة ثنائية غير جذرية

في الرياضيات وعلوم الحاسوب، الشجرة الثنائية غير الجذرية هي شجرة غير جذرية يكون لكل رأس فيها جار واحد أو ثلاثة جيران.

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

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

بالإضافة إلى ذلك، يمكن التمييز بين الأشجار التي تحمل جميع رؤوسها تسميات مميزة، والأشجار التي تحمل أوراقها تسميات فقط، والأشجار التي لا تحمل عقدها أي تسميات. في شجرة ثنائية غير جذرية ذات n ورقة، سيكون هناك n − 2 عقدة داخلية، لذا يمكن اختيار التسميات من مجموعة الأعداد الصحيحة من 1 إلى 2n − 1 عند تسمية جميع العقد، أو من مجموعة الأعداد الصحيحة من 1 إلى n عند تسمية الأوراق فقط. ^{[ 1 ]}    

نظرًا لتطبيقاتها في التجميع الهرمي، فإنّ أكثر مسائل تعداد الرسوم البيانية طبيعيةً على الأشجار الثنائية غير الجذرية هي حساب عدد الأشجار التي تحتوي على n ورقة مُصنَّفة وعُقد داخلية غير مُصنَّفة. يُمكن تكوين شجرة ثنائية غير جذرية على n ورقة مُصنَّفة عن طريق توصيل الورقة رقم n بعقدة جديدة في منتصف أيٍّ من حواف شجرة ثنائية غير جذرية على n - 1 ورقة مُصنَّفة. يوجد 2 ^n - 5 حافة يُمكن توصيل العقدة رقم n بها ؛ لذلك، فإنّ عدد الأشجار على n ورقة أكبر من عدد الأشجار على n - 1 ورقة بمعامل 2 ^n - 5. وبالتالي، فإنّ عدد الأشجار على n ورقة مُصنَّفة هو مضروب العدد 2.        

${\displaystyle (2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.}$^{[ 6 ]}

أرقام الأشجار على الأوراق المرقّمة 2، 3، 4، 5، ... هي

1، 1، 3، 15، 105، 945، 10395، 135135، 2027025، 34459425، ... (التسلسل A001147 في OEIS ) .

يرمز طول المسار بين الأوراق في شجرة ثنائية غير جذرية ثابتة (UBT) T إلى عدد الحواف التي تنتمي إلى المسار الفريد في T الذي يربط ورقة معينة بورقة أخرى. على سبيل المثال، بالرجوع إلى الشجرة الثنائية غير الجذرية الموضحة في الصورة على اليمين، فإن طول المسار${\displaystyle p_{1,2}}$المسافة بين الورقتين 1 و 2 تساوي 2، بينما طول المسار${\displaystyle p_{1,3}}$المسافة بين الورقتين 1 و3 تساوي 3. يُشفّر تسلسل أطوال المسارات من ورقة معينة على جدول UBT ثابت T أطوال المسارات من تلك الورقة إلى جميع الأوراق المتبقية. على سبيل المثال، بالرجوع إلى جدول UBT الموضح في الصورة على اليمين، يكون تسلسل أطوال المسارات من الورقة 1 هو${\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}$. عادة ما يشار إلى مجموعة تسلسلات طول المسار المرتبطة بأوراق T باسم مجموعة تسلسلات طول المسار لـ T ^{[ 7 ]} .

أظهر دانييلي كاتانزارو ورافاييل بيسينتي ولورانس وولسي ^{[ 7 ]} أن مجموعة تسلسل طول المسار التي تشفر UBT معينًا مع n ورقة يجب أن تستوفي معادلات محددة، وهي:

• ${\displaystyle p_{i,i}=0}$للجميع${\displaystyle i\in [1,n]}$
• ${\displaystyle p_{i,j}=p_{j,i}}$للجميع${\displaystyle i,j\in [1,n]:i\neq j}$
• ${\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}$للجميع${\displaystyle i,j,k\in [1,n]:i\neq j\neq k}$
• ${\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}$للجميع${\displaystyle i\in [1,n]}$(وهو تعديل لمتباينة كرافت-ماكميلان )
• ${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3}$، ويشار إليه أيضًا باسم التشعب التطوري . ^{[ 7 ]}

ثبت أن هذه المتساويات ضرورية ومستقلة لكي تقوم مجموعة أطوال المسارات بترميز UBT ذي n ورقة. ^{[ 7 ]} من غير المعروف حاليًا ما إذا كانت كافية أيضًا.

تُعرف الأشجار الثنائية غير الجذرية أيضًا بالأشجار الثنائية الحرة ، ^{[ 8 ]} والأشجار المكعبة ، ^{[ 9 ]} والأشجار الثلاثية ^{، [ 5 ]} والأشجار الثلاثية غير الجذرية . ^{[ 10 ]} ومع ذلك، فقد تم تطبيق اسم "الشجرة الثنائية الحرة" أيضًا على الأشجار غير الجذرية التي قد تحتوي على عقد من الدرجة الثانية، ^{[ 11 ]} وعلى الأشجار الثنائية الجذرية ذات الأبناء غير المرتبين، ^{[ 12 ]} ويُستخدم اسم "الشجرة الثلاثية" بشكل أكثر شيوعًا للدلالة على شجرة جذرية تحتوي على ثلاثة أبناء لكل عقدة .

• بالدينغ، دي جيه؛ بيشوب، مارتن جيه؛ كانينغز، كريستوفر (2007)، دليل علم الوراثة الإحصائي ، المجلد  1 (  الطبعة الثالثة)، وايلي-إنترساينس، ص  502، ISBN 978-0-470-05830-5.
• سيليبراسي، رودي؛ فيتاني، بول إم بي (2006). "طريقة استدلالية جديدة لشجرة رباعية للتجميع الهرمي". arXiv : cs/0606048 ..
• تشوماج، آرثر؛ جيبونز، آلان (1996)، "مشكلة غوثري: مكافئات جديدة واختزالات سريعة"، علوم الحاسوب النظرية ، 154 (1): 3-22 ، doi : 10.1016/0304-3975(95)00126-3.
• إبستين، ديفيد (2009)، "سراويل مربعة في شجرة: مجموع تجميع الأشجار الفرعية وتحليل السراويل الزائدية"، معاملات ACM في الخوارزميات ، 5 (3): 1-24 ، arXiv : cs.CG/0604034 ، doi : 10.1145/1541885.1541890 ، S2CID 2434 .
• إكسو، جيفري (1996)، "طريقة بسيطة لإنشاء رسوم بيانية مكعبة صغيرة ذات محيطات 14 و15 و16" (ملف PDF) ، المجلة الإلكترونية للتوافقية ، 3 (1) R30، doi : 10.37236/1254.
• فورناس، جورج و. (1984)، "توليد الأشجار العشوائية الثنائية غير المرتبة"، مجلة التصنيف ، 1 (1): 187-233 ، doi : 10.1007/BF01890123 ، S2CID 121121529 .
• هاراري، فرانك ؛ بالمر، إي إم؛ روبنسون، آر دبليو ( 1992)، "حساب الأشجار الثنائية الحرة التي تقبل ارتفاعًا معينًا" (ملف PDF) ، مجلة التوافقية والمعلومات وعلوم الأنظمة ، 17 : 175-181.
• هيندي، مايكل د.؛ بيني، ديفيد (1989)، "إطار للدراسة الكمية للأشجار التطورية"، علم الأحياء المنهجي ، 38 (4): 297-309 ، doi : 10.2307/2992396 ، JSTOR 2992396 
• برزيتيكا، تيريزا م .؛ لارمور، لورانس ل. (1994)، "إعادة النظر في مسألة الشجرة الأبجدية المثلى"، وقائع الندوة الدولية الحادية والعشرين حول الأتمتة واللغات والبرمجة (ICALP '94) ، سلسلة محاضرات في علوم الحاسوب، المجلد  820، سبرينغر-فيرلاغ، الصفحات 251-262 ، doi : 10.1007/3-540-58201-0_73 ، ISBN  978-3-540-58201-4.
• روبرتسون، نيل ؛ سيمور، بول د. (1991)، "الرسوم البيانية الصغرى. العاشر. عوائق تفكيك الشجرة"، مجلة نظرية التوافيق ، 52 (2): 153-190 ، doi : 10.1016/0095-8956(91)90061-N.
• سانت جون، كاثرين؛ وارنو، تاندي ؛ موريت، برنارد إم إي ؛ فاوترد، ليزا (2003)، "دراسة أداء الطرق التطورية: طرق الرباعيات (غير الموزونة) وربط الجوار" (ملف PDF) ، مجلة الخوارزميات ، 48 (1): 173-193 ، doi : 10.1016/S0196-6774(03)00049-X ، S2CID 5550338 .