الشجرة (نظرية الرسم البياني)

الشجرة هي رسم بياني غير موجه G يحقق أيًا من الشروط المتكافئة التالية:

• G متصلة وغير دورية (لا تحتوي على دورات).
• G عبارة عن مجموعة غير دورية، وتتشكل دورة بسيطة إذا تمت إضافة أي حافة إلى G.
• G متصلة، ولكنها ستنفصل إذا تمت إزالة أي حافة واحدة من G.
• G متصلة والرسم البياني الكامل K ₃ ليس رسمًا بيانيًا صغيرًا لـ G.
• يمكن ربط أي رأسين في G بمسار بسيط فريد .

إذا كان للمخطط G عدد محدود من الرؤوس، ولنقل n منها، فإن العبارات المذكورة أعلاه تكون مكافئة أيضًا لأي من الشروط التالية:

• G متصلة ولها n − 1 حافة.
• G متصلة، وكل رسم بياني فرعي من G يحتوي على رأس واحد على الأقل ذي صفر أو ضلع واحد متصل به. (أي أن G متصلة ومتدهورة من الدرجة 1 ).
• لا تحتوي G على دورات بسيطة ولها n − 1 حافة.

كما هو الحال في مجالات أخرى من نظرية المخططات، لا يُعتبر المخطط ذو الرتبة الصفرية (المخطط الذي لا يحتوي على رؤوس) شجرةً في العادة: فبينما هو متصل اتصالاً فارغاً كمخطط (يمكن ربط أي رأسين بمسار)، إلا أنه ليس متصلاً من الرتبة الصفرية (أو حتى من الرتبة (-1)) في الطوبولوجيا الجبرية، على عكس الأشجار غير الفارغة، ويخالف علاقة "عدد الرؤوس أكثر بواحد من عدد الحواف". ومع ذلك، يمكن اعتباره غابةً تتكون من صفر من الأشجار.

الرأس الداخلي (أو الرأس الداخلي) هو رأس من الدرجة 2 على الأقل. وبالمثل، فإن الرأس الخارجي (أو الرأس الخارجي، أو الرأس الطرفي، أو الورقة) هو رأس من الدرجة 1. رأس الفرع في الشجرة هو رأس من الدرجة 3 على الأقل. ^{[ 19 ]}

الشجرة غير القابلة للاختزال (أو الشجرة المختزلة بالسلسلة) هي شجرة لا يوجد فيها رأس من الدرجة 2 (مرقم في التسلسل A000014 في OEIS ). ^{[ 20 ]}

الغابة هي رسم بياني غير موجه وغير دوري، أو ما يعادله اتحاد منفصل من الأشجار. وبطبيعة الحال، كل مكون متصل في الغابة هو شجرة. ومن الأمثلة على الغابات: الرسم البياني من الرتبة الصفرية (غابة تتكون من صفر من الأشجار)، والشجرة المفردة، والرسم البياني عديم الحواف. بما أن V − E = 1 لكل شجرة ، يمكننا بسهولة حساب عدد الأشجار داخل الغابة بطرح الفرق بين إجمالي الرؤوس وإجمالي الحواف. V − E = عدد الأشجار في الغابة.

الشجرة المتعددة ^{[ 6 ]} (أو الشجرة الموجهة ^{[ 3 ]} أو الشجرة الموجهة ^{[ 4 ] [ 5 ]} أو الشبكة أحادية الاتصال ^{[ 7 ]} ) هي رسم بياني موجه غير دوري (DAG) يكون الرسم البياني الأساسي غير الموجه الخاص بها شجرة. بعبارة أخرى، إذا استبدلنا حوافها الموجهة بحواف غير موجهة، فسنحصل على رسم بياني غير موجه متصل وغير دوري في الوقت نفسه.

يُقصر بعض المؤلفين مصطلح "الشجرة الموجهة" على الحالة التي تكون فيها جميع الحواف موجهة نحو رأس معين، أو جميعها موجهة بعيدًا عن رأس معين (انظر التفرع الشجري ). ^{[ 21 ] [ 22 ] [ 23 ]}

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

كما هو الحال مع الأشجار الموجهة، يقصر بعض المؤلفين عبارة "الغابة الموجهة" على الحالة التي تكون فيها جميع حواف كل مكون متصل موجهة نحو رأس معين، أو جميعها موجهة بعيدًا عن رأس معين (انظر التفرع ). ^{[ 22 ]}

الشجرة الجذرية هي شجرة يُحدد فيها رأس واحد كجذر. ^{[ 24 ]} يمكن تحديد اتجاه طبيعي لحواف الشجرة الجذرية، إما بعيدًا عن الجذر أو باتجاهه، وفي هذه الحالة تصبح الشجرة جذرية موجهة. عندما يكون اتجاه الشجرة الجذرية الموجهة بعيدًا عن الجذر، تُسمى شجرة متفرعة [ ^{3 ] أو} شجرة خارجية ؛ ^{[ 11 ]} وعندما يكون اتجاهها باتجاه الجذر، تُسمى شجرة مضادة متفرعة أو شجرة داخلية . ^{[ 11 ]} ترتيب الشجرة هو الترتيب الجزئي لرؤوس الشجرة بحيث يكون u < v فقط إذا كان المسار الوحيد من الجذر إلى v يمر عبر u . الشجرة الجذرية T التي تُمثل رسمًا بيانيًا فرعيًا من رسم بياني G هي شجرة عادية إذا كانت نهايات كل مسار T في G قابلة للمقارنة وفقًا لهذا الترتيب الشجري ( Diestel 2005 ، ص 15) . تُعد الأشجار الجذرية، والتي غالبًا ما تحتوي على بنية إضافية مثل ترتيب الجيران عند كل رأس، بنية بيانات رئيسية في علوم الحاسوب؛ انظر بنية بيانات الشجرة . 

في سياق حيث يكون للأشجار عادةً جذر، تسمى الشجرة التي ليس لها جذر محدد شجرة حرة .

الشجرة المُصنَّفة هي شجرة يُعطى فيها كل رأس تصنيفًا فريدًا. عادةً ما تُعطى رؤوس الشجرة المُصنَّفة ذات n رأسًا (لأعداد صحيحة غير سالبة n ) التصنيفات من 1 إلى n . أما الشجرة التكرارية فهي شجرة جذرية مُصنَّفة حيث تحترم تصنيفات الرؤوس ترتيب الشجرة (أي، إذا كان u < v لرأسين u و v ، فإن تصنيف u يكون أصغر من تصنيف v ).

في الشجرة الجذرية، يكون رأس العقدة v هو العقدة المتصلة بـ v على المسار المؤدي إلى الجذر؛ لكل عقدة عقدة أب فريدة، باستثناء الجذر الذي ليس له عقدة أب. [24] ابن العقدة v هو العقدة التي v هي عقدتها الأب. [24] صاعد ^{العقدة v هو} أي عقدة إما أن تكون عقدة ^{أب لـ v} أو ( بشكل متكرر ) صاعدة لعقدة أب لـ v . سفلي العقدة v هو أي عقدة إما أن تكون عقدة ابن لـ v أو (بشكل متكرر) سفلية لعقدة ابن لـ v . شقيق العقدة v هو أي عقدة أخرى في الشجرة تشترك مع v في عقدة أب . ^{[ 24 ]} الورقة هي عقدة ليس لها عقد أبناء. ^{[ 24 ]} العقدة الداخلية هي عقدة ليست ورقة. ^{[ 24 ]}

ارتفاع رأس في شجرة جذرية هو طول أطول مسار هابط من ذلك الرأس إلى ورقة. ارتفاع الشجرة هو ارتفاع الجذر . عمق الرأس هو طول المسار إلى جذره ( مسار الجذر ). عمق الشجرة هو أقصى عمق لأي رأس. يُعدّ العمق ضروريًا في التعامل مع مختلف الأشجار ذاتية التوازن، وخاصة أشجار AVL . يكون عمق الجذر صفرًا، وارتفاع الأوراق صفرًا، والشجرة التي تحتوي على رأس واحد فقط (أي جذر وورقة) يكون عمقها وارتفاعها صفرًا. اصطلاحًا، تكون الشجرة الفارغة (أي الشجرة التي لا تحتوي على رؤوس، إن وُجدت) ذات عمق وارتفاع -1.

الشجرة من الرتبة k (لأعداد صحيحة غير سالبة k ) هي شجرة جذرية يكون لكل رأس فيها k من الأبناء على الأكثر. ^{[ 25 ]} تُسمى الأشجار من الرتبة 2 غالبًا بالأشجار الثنائية ، بينما تُسمى الأشجار من الرتبة 3 أحيانًا بالأشجار الثلاثية .

الشجرة المرتبة (أو الشجرة المستوية أو الشجرة الموضعية ^{[ 26 ]} ) هي شجرة جذرية يُحدد فيها ترتيبٌ لأبناء كل رأس. ^{[ 24 ] [ 27 ]} تُسمى هذه الشجرة "شجرة مستوية" لأن ترتيب الأبناء يُكافئ تمثيل الشجرة في المستوى، حيث يكون الجذر في الأعلى وأبناء كل رأس أسفله. عند تمثيل شجرة جذرية في المستوى، إذا ثُبِّت اتجاه الأبناء، مثلاً من اليسار إلى اليمين، فإن التمثيل يُعطي ترتيبًا للأبناء. على العكس، عند تمثيل شجرة مرتبة، ورسم الجذر في الأعلى، يُمكن رسم رؤوس الأبناء من اليسار إلى اليمين، مما يُنتج تمثيلاً مستويًا فريدًا.

تنص صيغة كايلي على وجود n ^{× n - 2} شجرة على n رأسًا مُصنَّفًا. يستخدم برهان كلاسيكي متواليات بروفر ، والتي تُظهر بطبيعة الحال نتيجة أقوى: عدد الأشجار ذات الرؤوس 1، 2، ...، n بدرجات d1 _، d2 ، ...، _{dn على التوالي ،} هو معامل متعدد الحدود .

${\displaystyle {n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.}$

تتمثل إحدى المشكلات الأكثر عمومية في حساب الأشجار الممتدة في رسم بياني غير موجه ، والتي يتم تناولها بواسطة نظرية شجرة المصفوفة . (صيغة كايلي هي حالة خاصة من الأشجار الممتدة في رسم بياني كامل ). المشكلة المماثلة المتمثلة في حساب جميع الأشجار الفرعية بغض النظر عن حجمها هي مشكلة كاملة من فئة #P في الحالة العامة ( جيروم (1994) ).

يُعدّ حساب عدد الأشجار الحرة غير المصنفة مشكلةً أكثر تعقيدًا. لا توجد صيغة مغلقة معروفة لعدد الأشجار t ( n ) التي تحتوي على n رأسًا حتى تماثل الرسم البياني . القيم القليلة الأولى لـ t ( n ) هي

1، 1، 1، 1، 2، 3، 6، 11، 23، 47، 106، 235، 551، 1301، 3159، … (التسلسل A000055 في OEIS ) .

أثبت أوتر (1948) التقدير التقاربي

${\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,}$

مع C ≈ 0.534949606... و α ≈ 2.95576528565... (التسلسل A051491 في OEIS ) . هنا، يرمز الرمز ~ إلى أن

${\displaystyle \lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.}$

هذا نتيجة لتقديره التقاربي لعدد r ( n ) من الأشجار الجذرية غير المصنفة ذات n رأس:

${\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,}$

مع D ≈ 0.43992401257... ونفس α كما هو مذكور أعلاه (انظر Knuth (1997) ، الفصل 2.3.4.4 و Flajolet & Sedgewick (2009) ، الفصل السابع.5، ص  475).

القيم القليلة الأولى لـ r ( n ) هي ^{[ 30 ]}

1، 1، 2، 4، 9، 20، 48، 115، 286، 719، 1842، 4766، 12486، 32973، ... (التسلسل A000081 في OEIS ) .