بوليتري

في الرياضيات ، وتحديدًا في نظرية المخططات ، تُعرف الشجرة المتعددة ^{[ 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 .
• Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science(PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6.
• Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363.
• Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines"(PDF), Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983, pp. 190–193.
• Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society, Third Series, 102 (4): 731–766, arXiv:1010.4430, doi:10.1112/plms/pdq035, MR 2793448.
• Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data"(PDF), Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228.
• Ruskey, Frank (1989), "Transposition generation of alternating permutations", Order, 6 (3): 227–233, doi:10.1007/BF00563523, MR 1048093.
• Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270.
• Trotter, William T. Jr.; Moore, John I. Jr. (1977), "The dimension of planar posets", Journal of Combinatorial Theory, Series B, 22 (1): 54–67, doi:10.1016/0095-8956(77)90048-X.