بوليتري

في الرياضيات ، وتحديدًا في نظرية المخططات ، تُعرف الشجرة المتعددة ^{[ 1 ]} (وتُسمى أيضًا الشجرة الموجهة ^{[ 2 ]} أو الشجرة الموجهة ^{[ 3 ]} أو الشبكة أحادية الاتصال ^{[ 4 ]} ) بأنها مخطط موجه غير دوري، يكون مخططه الأساسي غير الموجه شجرة . بعبارة أخرى، تتشكل الشجرة المتعددة من خلال تحديد اتجاه لكل حافة من حواف مخطط غير موجه متصل وغير دوري .

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

الشجرة المتعددة هي مثال على الرسم البياني الموجه .

صاغ مصطلح polytree في عام 1987 من قبل ريبان وبيرل . ^{[ 5 ]}

• الشجرة المتفرعة هي شجرة موجهة ذات جذر ، أي رسم بياني موجه غير دوري، حيث يوجد عقدة مصدر واحدة لها مسار فريد إلى كل عقدة أخرى. كل شجرة متفرعة هي شجرة متعددة، ولكن ليس كل شجرة متعددة هي شجرة متفرعة.
• الشجرة المتعددة هي رسم بياني موجه غير دوري، حيث يشكل الرسم البياني الفرعي الذي يمكن الوصول إليه من أي عقدة شجرة. كل شجرة متعددة هي شجرة متعددة .
• تشكل علاقة الوصول بين عقد الشجرة المتعددة ترتيبًا جزئيًا لا يتجاوز بُعده ثلاثة. إذا كان بُعد الترتيب ثلاثة، فلا بد من وجود مجموعة جزئية من سبعة عناصر .${\displaystyle x}$،${\displaystyle y_{i}}$، و${\displaystyle z_{i}}$(ل${\displaystyle i=0,1,2}$) بحيث يكون لكل${\displaystyle i}$، أيضاً${\displaystyle x\leq y_{i}\geq z_{i}}$أو${\displaystyle x\geq y_{i}\leq z_{i}}$، حيث تحدد هذه المتباينات الستة بنية الشجرة المتعددة على هذه العناصر السبعة. ^{[ 6 ]}
• يُعدّ السياج أو المجموعة المرتبة المتعرجة حالة خاصة من الشجرة المتعددة ، حيث تكون الشجرة الأساسية عبارة عن مسار، وتتبادل حوافها اتجاهاتها على طول هذا المسار. ويُطلق على ترتيب إمكانية الوصول في الشجرة المتعددة أيضًا اسم السياج المعمم . ^{[ 7 ]}

عدد الأشجار المتعددة المتميزة على${\displaystyle n}$العقد غير المصنفة، لـ${\displaystyle n=1,2,3,\dots }$، يكون

تنص فرضية سومنر ، التي سُميت نسبةً إلى ديفيد سومنر ، على أن البطولات هي رسوم بيانية شاملة للأشجار المتعددة، بمعنى أن كل بطولة مع${\displaystyle 2n-2}$تحتوي الرؤوس على كل شجرة متعددة الأضلاع مع${\displaystyle n}$الرؤوس كرسم بياني فرعي. على الرغم من أنها لا تزال غير محلولة، فقد تم إثباتها لجميع القيم الكبيرة بما فيه الكفاية لـ${\displaystyle n}$[ ^{8 ]​}

استُخدمت الأشجار المتعددة كنموذج بياني للاستدلال الاحتمالي . ^{[ 1 ]} إذا كانت الشبكة البايزية ذات بنية شجرة متعددة، فيمكن استخدام نشر المعتقدات لإجراء الاستدلال بكفاءة عليها. ^{[ 4 ] [ 5 ]}

شجرة الكفاف لدالة حقيقية القيمة على فضاء متجهي هي شجرة متعددة الأضلاع تصف مجموعات المستوى للدالة. تمثل عقد شجرة الكفاف مجموعات المستوى التي تمر بنقطة حرجة للدالة، بينما تمثل الحواف مجموعات متجاورة من مجموعات المستوى التي لا تمر بنقطة حرجة. ويُحدد اتجاه الحافة بمقارنة قيم الدالة على مجموعتي المستوى المتناظرتين. ^{[ 9 ]}

• مسرد مصطلحات نظرية الرسم البياني

• كار، هاميش؛ سنوينك، جاك؛ أكسن، أولريك (2000)، "حساب أشجار الكفاف في جميع الأبعاد" ، وقائع الندوة الحادية عشرة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة (SODA 2000) ، جمعية آلات الحوسبة، الصفحات 918-926 ، ISBN  978-0-89871-453-1
• داسغوبتا، سانجوي (1999)، " تعلم الأشجار المتعددة" (ملف PDF) ، وقائع المؤتمر الخامس عشر حول عدم اليقين في الذكاء الاصطناعي (UAI 1999)، ستوكهولم، السويد، يوليو-أغسطس 1999 ، الصفحات 134-141 .
• ديو، نارسنج (1974)، نظرية الرسم البياني مع تطبيقات في الهندسة وعلوم الحاسوب (ملف PDF) ، إنجلوود، نيو جيرسي: برنتيس هول، رقم ISBN 0-13-363473-6.
• هاراري، فرانك ؛ سومنر، ديفيد (1980)، "العدد ثنائي اللون لشجرة موجهة"، مجلة التوافقية والمعلومات وعلوم النظم ، 5 (3): 184-187 ، MR 0603363 .
• كيم، جين هـ.؛ بيرل، جوديا (1983)، "نموذج حسابي للاستدلال السببي والتشخيصي في محركات الاستدلال" (ملف PDF) ، وقائع المؤتمر الدولي المشترك الثامن حول الذكاء الاصطناعي (IJCAI 1983)، كارلسروه، ألمانيا، أغسطس 1983 ، الصفحات 190-193 .
• كوهن، دانييلا ؛ مايكروفت، ريتشارد؛ أوستوس، ديريك (2011)، "برهان على حدسية سومنر الشاملة للبطولات الكبيرة"، وقائع الجمعية الرياضية بلندن ، السلسلة الثالثة، 102 (4): 731-766 ، arXiv : 1010.4430 ، doi : 10.1112/plms/pdq035 ، MR 2793448 .
• ريبان، جورج؛ بيرل، جوديا (1987)، "استعادة الأشجار السببية المتعددة من البيانات الإحصائية" (ملف PDF) ، وقائع المؤتمر السنوي الثالث حول عدم اليقين في الذكاء الاصطناعي (UAI 1987)، سياتل، واشنطن، الولايات المتحدة الأمريكية، يوليو 1987 ، الصفحات 222-228 .
• روسكي، فرانك (1989)، "توليد التبديلات المتناوبة"، النظام ، 6 (3): 227-233 ، doi : 10.1007/BF00563523 ، MR 1048093 .
• سيميون، روديكا (1991)، "الأشجار ذات العوامل الأحادية والأشجار الموجهة"، الرياضيات المتقطعة ، 88 (1): 93-104 ، doi : 10.1016/0012-365X(91)90061-6 ، MR 1099270 .
• تروتر، ويليام تي. الابن ؛ مور، جون آي. الابن (1977)، "بعد المجموعات المرتبة جزئيًا المستوية"، مجلة نظرية التوافيق، السلسلة ب ، 22 (1): 54-67 ، doi : 10.1016/0095-8956(77)90048-X.