الأشجار

القسم 2.2 الأشجار

الأهداف

بعد إتمام هذا القسم، ينبغي أن تكون قادرًا على ما يلي.

1. اثبت حقائقَ أساسية عن الأشجار.
2. استعمل مبرهيناتَ عن الأشجار لحل المسائل.
3. ميّز بين الأشجار الممتدة (spanning trees) وأنشئها.

معاينة القسم

استكشف!

تأمّل الرسم البياني المرسوم أدناه.

1. أوجد رسمًا فرعيًا بأصغر عدد ممكن من الحوافّ يبقى متصلًا ويحتوي على جميع الرؤوس.
2. أوجد رسمًا فرعيًا بأكبر عدد ممكن من الحوافّ لا يحتوي على أيّ دورة.
3. ما الذي تلاحظه في عدد الحوافّ في أمثلتك أعلاه؟ هل هذا مصادفة؟

إحدى أكثر طرائق دراسة نظرية الرسوم البيانية نفعًا وشيعًا هي أن تقتصر على رسومَ بيانية من نوعٍ بعينه. فمثلًا، يمكنك أن تحاول أن تفهم فهمًا حقيقيًّا الرسومَ البيانية الكاملة (complete graphs) وحدها، أو الرسومَ البيانية ثنائيةَ الطرف (bipartite graphs) وحدها، بدلًا من محاولة فهم جميع الرسوم البيانية على العموم. وهذا هو ما سنفعله الآن، إذ سننظر في الأشجار (trees). ونرجو أن يكون في وسعنا في نهاية هذا القسم أن نفهم هذه الفئة من الرسوم البيانية فهمًا أفضل، وأيضًا أن نفهم لماذا هي مهمةٌ بما يكفي لاستحقاق قسمٍ خاصٍّ بها.

تعريف 2.2.1. الأشجار والغابات.

الشجرة (tree) رسمٌ بياني متصل لا يحتوي على أيّ دورة. 4 وأحيانًا تُصاغ هذه العبارة على النحو: «الشجرة رسمٌ بياني متصل لا دوريّ (acyclic)»؛ فكلمة «لا دوريّ» ليست سوى كلمةٍ فخمة بالمعنى «لا يحتوي على دورات».

والغابة (forest) رسمٌ بياني لا يحتوي على أيّ دورة. ولاحظ أنّ هذا يعني أنّ الغابة المتصلة شجرة.

أفيوافق التعريف أعلاه حدسك فيما ينبغي أن نسمّيه شجرةً من الرسوم البيانية؟ حاول أن تفكّر في أمثلة للأشجار، وتأكّد من أنّها تحقّق التعريف. ومن الأمور التي يجدر بك تذكّرها أنّ الأشجار التي ندرسها في نظرية الرسوم البيانية ترتبط بالأشجار التي قد تراها في تخصّصاتٍ أخرى، غير أنّ هذا الارتباط ليس تامًّا. فمثلًا، في علم الأنساب (anthropology) قد تدرس أشجارَ العائلة (family trees)، مثل التي أدناه،

! ويبدو الأمر حسنًا إلى هذا الحدّ، لكن مع أنّ جدّيك (على الأرجح) ليسا من الدم نفسه، فإنّنا إذا عدنا في النسب إلى الخلف بما يكفي، فمن المرجّح أن يكون لهما سلفٌ مشترك واحدٌ على الأقلّ. وإن تتبّعتَ الشجرة منك عائدًا إلى ذلك الجدّ المشترك، ثمّ نزلتَ فيها عبر جدّك الآخر، لوجدتَ دورة، ومن ثمّ لا يكون الرسم البياني شجرة.

ولعلّك صادفت أيضًا شيئًا يُسمّى شجرة قرار (decision tree)، مثل الخوارزمية التي تقرّر ما إذا كان متتاليةٌ ما متقاربة أم متباعدة. وأحيانًا تحتوي هذه أيضًا على دورات، إذ قد يقودك القرار المتّخذ في عقدةٍ ما إلى العودة إلى خطوةٍ سابقة.

وفي مثالَي الشجرة أعلاه خاصيةٌ أخرى جديرة بالذكر: إذ إنّ لرؤوس الشجرة ترتيبًا واضحًا. فلا يتضمّن تعريف الشجرة هذه البنية المضافة، غير أنّه يمكننا فرض بنيةٍ من هذا النوع بالنظر في الأشجار الجذورية (rooted trees)، حيث نكتفي بتعيين رأسٍ واحد بوصفه الجذر (root). وسننظر في هذه الأشجار بتفصيلٍ أكثر لاحقًا في هذا القسم.

وفي هذا القسم سنستكشف بعض الخواصّ الأساسية للأشجار، وستكون مقدّمةً ممتازة لكتابة البراهين عن الرسوم البيانية. وسننظر أيضًا في نوعٍ خاصّ من الأشجار يُسمّى الشجرة الممتدة (spanning tree)، وهي شجرة تتضمّن جميع رؤوس رسمٍ بياني متصل. وأخيرًا سننظر بإيجاز في الأشجار الجذورية.

ورقة العمل: نشاط تمهيدي

1.

خُذ ورقةً وارسم 8 رؤوس في دائرة.

وسنضيف حوافّ إلى هذا الرسم البياني مستوفين بعض الشروط.

(a)

أوّلًا، أضف أصغر عدد ممكن من الحوافّ بحيث يصبح الرسم البياني الناتج متصلًا. أي أنّه يجب أن يكون هناك مسارٌ بين كلّ زوج من الرؤوس (والمسار قد يستعمل أكثر من حافة، بالطبع).

كم حافةً في الرسم البياني الذي رسمته؟

(b)

هل كان الرسم البياني الناتج الذي وجدتَه شجرةً؟

• نعم، لأنّ الرسم البياني متصل ولا يحتوي على دورات
• لا، الرسم البياني يحتوي على دورة
• لا، الرسم البياني غير متصل
• لا، الرسم البياني غير متصل ويحتوي على دورة

(c)

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

كم حافةً في الرسم البياني الذي رسمته؟

(d)

هل كان الرسم البياني الناتج الذي وجدتَه شجرةً؟

• نعم، لأنّ الرسم البياني متصل ولا يحتوي على دورات
• لا، الرسم البياني يحتوي على دورة
• لا، الرسم البياني غير متصل
• لا، الرسم البياني غير متصل ويحتوي على دورة

قسم فرعي: خواصّ الأشجار

نريد أن نفهم الأشجار فهمًا حقيقيًّا. أي ينبغي أن نكتشف خواصّ الأشجار: ما الذي يجعلها مميّزة، وما الذي يميّز خواصّها.

الشجرة رسمٌ بياني متصل لا يحتوي على دورات. فهل هناك ما يمكننا قوله أيضًا؟ سيكون من الجيّد أن تتوفّر لدينا شروطٌ أخرى مكافئة كي يكون الرسم البياني شجرة. أي نودّ أن نعرف ما إذا كانت هناك خواصّ في نظرية الرسوم البيانية تملكها جميع الأشجار، بل وحتى يقتصر عليها الأشجار وحدها.

وكي نتمكّن من تلمّس نوع ما يمكننا قوله، سننظر في ثلاث دعاوى (propositions) عن الأشجار. وهذه ستوضّح أيضًا تقنياتَ براهين مهمّة تنطبق على الرسوم البيانية على العموم، وتكون أصعب قليلًا في حالة الأشجار.

أمّا الدعوى الأولى فتقدّم تعريفًا بديلًا للشجرة. أي أنّها تعطي الشرطين اللازم والكافي كي يكون الرسم البياني شجرة.

دعوى 2.2.2.

الرسم البياني $T$ يكون شجرةً إذا وفقط إذا كان بين كلّ زوج من الرؤوس المتمايزة في $T$ مسارٌ فريد.

البرهان.

هذه عبارة «إذا وفقط إذا»، لذا علينا إثبات استلزامَين. نبدأ بإثبات أنّه إذا كان $T$ شجرةً، فإنّ بين كلّ زوج من الرؤوس المتمايزة يوجد مسارٌ فريد.

افترض أنّ $T$ شجرة، وليكن $u$ و$v$ رأسَين متمايزَين (وإذا كان في $T$ رأسٌ واحدٌ فقط، فإنّ النتيجة محقّقة تلقائيًّا). علينا إثبات أمرَين لإثبات وجود مسارٍ فريد بين $u$ و$v\text{:}$: وجود مسار، وعدم وجود أكثر من مسار. أمّا الأمر الأول فذلك بداهة؛ ولأنّ $T$ شجرة، فإنّها متصلة، ومن ثمّ هناك مسارٌ بين كلّ زوج من الرؤوس.

ولإثبات أنّ المسار فريد، نفترض وجود مسارَين بين $u$ و$v\text{,}$ فنصل إلى تناقض. قد يبدأ المساران متطابقَين، لكن بما أنّهما مختلفان، فإنّ هناك رأسًا أوّل $u'$ تنفرج بعده المساران. غير أنّه، بما أنّ المسارَين ينتهيان معًا عند $v\text{,}$ فإنّ هناك رأسًا أوّل بعد $u'$ يشتركان فيه، ولنسمّه $v'\text{.}$ والآن تأمّل المسارَين من $u'$ إلى $v'\text{.}$ وهذان معًا يشكّلان دورة، وهذا يناقض افتراضنا بأنّ $T$ شجرة.

والآن ننظر في العكس: إذا كان بين كلّ زوج من الرؤوس المتمايزة في $T$ مسارٌ فريد، فإنّ $T$ شجرة. فافترض الفرضية: بين كلّ زوج من الرؤوس المتمايزة في $T$ يوجد مسارٌ فريد. ولإثبات أنّ $T$ شجرة، علينا إثبات أنّها متصلة ولا تحتوي على دورات.

النصف الأول من هذا سهل: $T$ متصلة، لأنّ هناك مسارًا بين كلّ زوج من الرؤوس. ولإثبات أنّ $T$ لا تحتوي على دورات، نفترض أنّها تحتوي، طلبًا للتناقض. وليكن $u$ و$v$ رأسَين متمايزَين في دورةٍ من دورات $T\text{.}$ وبما أنّه يمكننا أن ننتقل من $u$ إلى $v$ بالذهاب مع اتجاه الساعة أو عكسه حول الدورة، فإنّ هناك مسارَين من $u$ إلى $v\text{,}$ ممّا يناقض افتراضنا.

وقد أثبتنا الاتجاهَين، ومن ثمّ أكملنا البرهان.

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

وتتيح لنا هذه الملاحظة أن نُصوغ النتيجة (corollary) التالية. 5 والنتيجة (corollary) هي نوعٌ آخر من العبارات القابلة للإثبات، مثل الدعوى أو النظرية، غير أنّها تتبع مباشرةً عبارةً أخرى أُثبتت من قبل، أو برهانَها.

نتيجة 2.2.3.

الرسم البياني $F$ يكون غابةً إذا وفقط إذا كان بين كلّ زوج من الرؤوس في $F$ مسارٌ واحدٌ على الأكثر.

نحن لا نعطي برهانَ النتيجة (فهي، بعد كلّ شيء، يُفترض أن تتبع مباشرةً من الدعوى)، لكن من أجل التمرين نطلب إليك أن تقدّم برهانًا متأنّيًا في التمارين. وحين تفعل ذلك، حاول أن تستعمل البرهان بنقيض المضمون (proof by contrapositive) بدلًا من البرهان بالتناقض.

وتخبرنا الدعوى الثانية أنّ جميع الأشجار لها أوراق (leaves)، أي رؤوسًا من الدرجة الأولى.

دعوى 2.2.4.

أيّ شجرةٍ فيها رأسان على الأقلّ تملك رأسَين من الدرجة الأولى على الأقلّ.

البرهان.

نعطي برهانًا بالتناقض. وليكن $T$ شجرةً فيها رأسان على الأقلّ، ونفرض، على خلاف المطلوب، أنّه لا يوجد رأسان من الدرجة الأولى.

وليكن $P$ مسارًا في $T$ من أطول طولٍ ممكن. وليكن $u$ و$v$ طرفَي هذا المسار. وبما أنّ $T$ لا تملك رأسَين من الدرجة الأولى، فلا بدّ أن يكون أحدهما على الأقلّ من الدرجة الثانية أو أعلى. لنقل إنّ ذلك هو $u\text{.}$ ونحن نعرف أنّ $u$ مجاورٌ لرأسٍ ما في المسار $P\text{,}$ لكنّه يجب أن يكون الآن مجاورًا لرأسٍ آخر، لنسمّه $u'\text{.}$

وأين $u'\text{?}$ لا يمكن أن يكون رأسًا من رؤوس $P\text{,}$ لأنّه لو كان كذلك لكان بين $u$ و$u'\text{:}$ مساران متمايزان: الحافة بينهما، والجزء الأول من $P$ (حتى $u'$). لكنّ $u'$ لا يمكن أيضًا أن يكون خارج $P\text{,}$ فإنّه لو كان كذلك لكان هناك مسارٌ من $u'$ إلى $v$ أطول من $P\text{,}$ وهو أطول طولٍ ممكن.

وهذا التناقض يثبت أنّه لا بدّ من وجود رأسَين على الأقلّ من الدرجة الأولى. وفي الحقيقة يمكننا القول بأكثر قليلًا من ذلك: لا بدّ أن يكون لكلٍّ من $u$ و$v$ درجةٌ واحدة.

والدعوى مفيدةٌ جدًّا عند إثبات عباراتٍ عن الأشجار، لأنّنا نُثبت عباراتٍ عن الأشجار كثيرًا ما بالتعريض (induction). وهذه تقنيةُ برهانٍ نستعرضها بالتفصيل في القسم 4.5، أمّا الآن فنحن لا نحتاج إلّا أن نفهم أنّها مفيدةٌ لمقارنة شجرةٍ معطاةٍ بأشجار أصغر منها. فإلإثبات أنّ أمرًا ما صحيحٌ لشجرةٍ فيها $v$ رأسًا، سنفترض أنّ الأمر صحيح لجميع الأشجار التي فيها $v-1$ رأسًا. وبحذف رأسٍ من الدرجة الأولى نحصل على هذه الشجرة الأصغر، ثمّ لا يلزمنا إلّا أن نبيّن أنّ إعادة الرأس إلى مكانه لا تُفسد أمورَنا.

هل توجد شجرةٌ فيها بالضبط 7 رؤوس و7 حوافّ؟ حاول أن ترسم واحدة. وهل يمكن لشجرةٍ فيها 7 رؤوس أن تملك 5 حوافّ فقط؟ وهناك سببٌ جيّد يجعل هذين يبدو مستحيلَي الرسم.

دعوى 2.2.5.

ليكن $T$ شجرةً فيها $v$ رأسًا و$e$ حافة. عندئذٍ $e = v-1\text{.}$

سنثبت أنّ هذه الدعوى صحيحةٌ لكلّ القيم المحتملة لـ $v \ge 1\text{.}$ ولاحظ أنّه إذا كان $v = 1\text{,}$ فلا بدّ أن تكون في الشجرة $0$ حوافّ، إذن نعم، $e = v-1\text{.}$ ثمّ يمكننا أن ننظر في الأشجار التي فيها $v=2$ رأسًا (هناك واحدةٌ فقط، وفيها $e = 1 = v-1$ حافة) ثمّ في جميع الأشجار التي فيها $v=3$ رؤوس، ثمّ $v=4\text{,}$ وهكذا، لكنّ ذلك يستغرق إلى الأبد. حرفيًّا!

وبدلًا من ذلك، سنُجري صيغةً من البرهان بالتناقض تُسمّى المجرمَ الأدنى (minimal criminal). سنفترض أنّ الدعوى غير صحيحة (كما تفعل في أيّ برهان بالتناقض). ويجني هذا أنّ هناك شجرةً أصغر لا تصدّق عليها الدعوى. فإذا كان هذا المثالُ المضادّ الأصغر (أي المجرم الأدنى) فيه $v$ رؤوس، فإنّنا نُضمن أنّ جميع الأشجار التي فيها $v-1$ رؤوس ليست أمثلةَ مضادّة. ولنرَ كيف يجري هذا.

البرهان.

افترض، طلبًا للتناقض، أنّ الدعوى ليست صحيحةً لكلّ الأشجار. وليكن $T$ شجرةً الدعوى فيها غير صحيحة، وهي التي لها أصغر عددٍ من الرؤوس بين جميع الأمثلة المضادّة. وليكن $v$ عددَ رؤوس $T\text{.}$

وبما أنّ الشجرة الوحيدة ذات الرأس الواحد ليس فيها حوافّ، فلا يمكن أن تكون شجرتُنا $T\text{,}$ ومن ثمّ يمكننا أن نفترض $v \ge 2\text{.}$ وعلى وجه الخصوص، نعرف من دعوى 2.2.4 أنّ $T$ يجب أن تحتوي على رأسٍ واحدٍ على الأقلّ من الدرجة الأولى، لنسمّه $v_0\text{.}$

وليكن $T'$ الشجرةَ الناتجة عن حذف $v_0$ من $T$ (مع حافّتها الملاصقة). وبما أنّنا حذفنا ورقة، فإنّ $T'$ ما زالت شجرة (المساراتُ الفريدة بين أزواج الرؤوس في $T'$ هي نفسها المساراتُ الفريدة بينها في $T$).

والآن في $T'$ عددٌ من الرؤوس يساوي $v-1$. وبما أنّ $T$ كانت أصغر شجرةٍ الدعوى فيها غير صحيحة، فنحن نعلم أنّ الدعوى صحيحةٌ لـ $T'\text{.}$ إذن لا بدّ أن يكون في $T'$ حافةٌ واحدةٌ أقلّ من عدد الرؤوس؛ أي أنّ في $T'$ عددًا من الحوافّ يساوي $v-2$. لكنّ في $T$ حافةً واحدةً أكثر من $T'\text{,}$ إذن فيها $v-1$ حافة. وهذا يناقض افتراضنا بأنّ $T$ لا تحقّق الدعوى، وبذلك يكتمل برهانُنا.

قسم فرعي: الأشجار الممتدة

ومن مزايا الأشجار أنّها تمتحنا طرائقَ بسيطةً قليلة للتنقّل بين الرؤوس. فإذا لم يكن رسمٌ بياني متصل شجرة، فلا يزال بإمكاننا استعمال خوارزميات اجتياز (traversal) هذه إن حدّدنا رسمًا فرعيًا هو شجرة.

وقبل ذلك يجدر بنا أن نتأمّل ما إذا كان هذا منطقيًّا أصلًا. فبمعطى أيّ رسمٍ بياني متصل $G\text{,}$ هل يوجد دائمًا رسمٌ فرعي هو شجرة؟ والحقيقة أنّ ذلك سهلٌ فضلًا: يمكنك أن تكتفي بأخذ رأسٍ واحدٍ من $G\text{.}$ أمّا إن أردنا أن تخبرنا هذه الرسم الفرعي بكيفية زيارة جميع الرؤوس، فنريده أن يتضمّن جميع الرؤوس. ونسمّي شجرةً من هذا النوع شجرةً ممتدة (spanning tree).

تعريف 2.2.6.

بمعطى رسمٍ بياني متصل $G\text{,}$ تكون الشجرةُ الممتدة لـ $G$ رسمًا فرعيًا من $G$ يكون شجرةً ويتضمّن جميع رؤوس $G\text{.}$

ويتبين أنّ كلّ رسمٍ بياني متصل يملك واحدة (وكثيرًا ما يملك).

نظرية 2.2.7.

كلّ رسمٍ بياني متصل يملك شجرةً ممتدة.

وكيف نعرف ذلك؟ يمكننا أن نعطي خوارزميةً لـالعثور على شجرةٍ ممتدة! ابدأ برسمٍ بياني متصل $G\text{.}$ فإذا لم تكن هناك دورات، فإنّ $G$ شجرةً أصلًا وقد انتهينا. وإن كانت هناك دورة، فلتكن $e$ أيّ حافةٍ في تلك الدورة، ولنتأمّل الرسمَ البياني الجديد $G_1 = G - e$ (أي الرسم البياني الذي تحصل عليه بحذف $e$). فهذه الشجرة ما زالت متصلة: ولأنّ $e$ كانت تنتمي إلى دورة، فكان بين طرفيها مساران على الأقلّ. والآن كرّر: إذا لم تكن في $G_1$ دورات، فقد انتهينا؛ وإلّا فعرّف $G_2$ لتكون $G_1 - e_1\text{,}$ حيث $e_1$ حافةٌ في دورةٍ ما في $G_1\text{.}$ وواصل المضيّ قدمًا. ولابدّ أن تتوقّف هذه العمليّة في وقتٍ ما، لأنّ عدد الحوافّ القابلة للحذف محدود. وسيكون الناتجُ شجرةً، وبما أنّنا لم نحذف أيّ رأس، ستكون شجرةً ممتدّة.

وليست هذه بأيّ حال الخوارزميةَ الوحيدة للعثور على شجرةٍ ممتدة. فكان بإمكانك أن تبدأ بالرسم البياني الفارغ وتضيف حوافَّ تنتمي إلى $G\text{,}$ ما دام إضافتُها لا تنشئ دورة. ولك بعض الخيارات في تحديد الحوافّ التي تضيفها أوّلًا: يمكنك دائمًا أن تضيف حافةً مجاورَةً للحوافّ التي أضفتها من قبل (بعد الأولى بالطبع)، أو تضيفها بترتيبٍ آخر. وأيّ شجرةٍ ممتدة تنتهي إليها يعتمد على هذه الاختيارات.

مثال 2.2.8.

أوجد شجرتين ممتدتين مختلفتين للرسم البياني،

الحلّ. إليك شجرتين ممتدتين.

ورغم أنّنا لن نتناول هذا بالتفصيل، فإنّ هذه الخوارزميات تُطبَّق عادةً على الرسوم البيانية المُوزونة (weighted). فهنا لكلّ حافةٍ وزنٌ أو تكاليفُ تُسند إليها. والهدف هو العثور على شجرةٍ ممتدة يكون مجموعُ أوزانها أصغر ما يمكن. وتُسمّى شجرةٌ من هذا النوع شجرةَ الحدّ الأدنى (minimum spanning tree). والعثورُ على شجرة الحدّ الأدنى يستعمل الخوارزميات نفسها التي وصفناها أعلاه في جوهرها، لكن حين تختار حافةً لإضافتها فإنّك تختار دائمًا الأصغر (أو حين تحذف حافةً فإنّك تحذف دائمًا الأكبر). 6 فإذا أضفت أصغر حافةٍ مجاورَةٍ للحوافّ التي أضفتها من قبل، فأنت تستعمل خوارزمية بريم (Prim's algorithm). وإذا أضفت أصغر حافةٍ في الرسم البياني كلّه، فأنت تتبع خوارزمية كروسكال (Kruskal's algorithm).

قسم فرعي: الأشجار الجذورية

حتى الآن كنا ننظر إلى الأشجار بوصفها نوعًا بعينه من الرسوم البيانية فحسب. غير أنّه من المفيد غالبًا أن نضيف إلى الأشجار بنيةً إضافية تساعدنا في حل المسائل. فالبيانات مُنظَّمة في الغالب على صورة شجرة. فكتابنا هذا، مثلًا، له بنيةٌ شجرية: ارسم رأسًا للكتاب نفسه. ثمّ ارسم رأسًا لكلّ فصل، مربوطًا برأس الكتاب. وتحت كلّ فصل، ارسم رأسًا لكلّ قسم، مربوطًا بالفصل الذي ينتمي إليه. ولن يكون في الرسم البياني أيّ دورات؛ بل سيكون شجرةً، لكنّها شجرةٌ ذات تسلسلٍ هرميٍّ واضحٍ لا يظهر إن لم نُعيّن «رأس الكتاب» بوصفه «القمة».

وبمجرد أن يُعيَّن رأسٌ واحدٌ من رؤوس الشجرة بوصفه الجذر (root)، أمكن أن نُميّز كلّ رأسٍ آخر فيها بموقعه نسبةً إلى الجذر. والأمر بهذا يعمل لأنّ بين أيّ رأسَين في الشجرة مسارًا فريدًا. ومن ثمّ نستطيع من أيّ رأس أن نعود إلى الجذر بطريقةٍ واحدةٍ بالضبط. وهذا يتيح لنا أيضًا أن نصف كيف ترتبط الرؤوسُ المتمايزة في شجرةٍ جذورية ببعضها.

فإذا كان رأسان متجاورَين، قلنا إنّ أحدهما الأصل (parent) للآخر، والآخر ابنُ الأصل (child). ومن بين الرأسَين، يكون الأصل هو الرأس الأقرب إلى الجذر. ومن ثمّ يكون جذرُ الشجرة أصلًا، لكنّه ليس ابنَ أيّ رأس (وهو فريدٌ في هذا المعنى: فجميع الرؤوس غير الجذر لها أصلٌ واحدٌ بالضبط).

ومن غير المستغرب أن يُسمّى ابنُ الابن حفيدًا (grandchild) للرأس (وهو الجدّ له). والأعمّ من ذلك نقول إنّ الرأس $v$ يكون من نسل (descendent) الرأس $u$ بشرط أن يكون $u$ رأسًا على المسار من $v$ إلى الجذر. وعندئذٍ نسمي $u$ سلفًا (ancestor) لـ $v\text{.}$

وفي معظم الأشجار (وفي الحقيقة إلّا المسارات التي يكون أحدُ طرفيَها هو الجذر) توجد أزواجٌ من الرؤوس لا يكون أيٌّ منها من نسل الآخر. ويمكننا تسمية هذين قرينَين (cousins) أو شقيقَين (siblings). وفي الحقيقة تُسمّى الرؤوسُ $u$ و$v$ شقيقَين بشرط أن يكون لهما الأصلُ نفسه. ولاحظ أنّ الشقيقَين لا يكونان متجاورَين أبدًا (هل ترى لماذا؟).

مثال 2.2.9.

تأمّل الشجرةَ أدناه.

فإذا عيّنّا الرأسَ $f$ بوصفه الجذر، فإنّ $e\text{,}$ $h\text{,}$ و$i$ تكون أبناءَ $f\text{,}$ وهي شقيقةً بعضها بعض. ومن الأشياء الأخرى التي يمكننا قولها إنّ $a$ ابنُ $c\text{,}$ ومن نسلِ $f\text{.}$ أمّا الرأسُ $g$ فمن نسلِ $f\text{,}$ بل هو في الواقع حفيدُ $f\text{.}$ والرؤوسُ $g$ و$d$ شقيقة، لأنّ لهما الأصلَ المشترك $e\text{.}$

ولاحظ كيف يتغيّر هذا إن اخترنا رأسًا مختلفًا ليكون الجذر. فإذا كان $a$ هو الجذر، فإنّ ابنَه الوحيدَ هو $c\text{,}$ ولَه بدوره ابنٌ واحدٌ فقط، هو $e\text{.}$ عندئذٍ يكون $f$ ابنَ $e$ (لا العكس)، ويكون $f$ من نسلِ $a\text{,}$ لا سلفًا له. أمّا $f$ و$g$ فأخوان الآن.

كلُّ هذه اللغة المزخرفة تساعدنا على وصف كيفية التنقّل في شجرة. فاجتيازُ شجرة، أي زيارةُ كلّ رأسٍ بترتيبٍ ما، خطوةٌ أساسيةٌ في خوارزمياتَ كثيرة. وحتى إن لم تكن الشجرةُ جذورية، يمكننا دائمًا تشكيل شجرةٍ جذورية باختيار أيّ رأسٍ ليكون الجذر. وإليك مثالًا على كيف قد يكون ذلك مفيدًا.

مثال 2.2.10.

اشرح لماذا كلُّ شجرةٍ رسمٌ بياني ثنائي الطرف (bipartite graph).

الحلّ. لإثبات أنّ رسمًا بيانيًا ثنائي الطرف، علينا أن نقسم الرؤوس إلى مجموعتَين، $A$ و$B\text{,}$ بحيث لا يكون رأسان في المجموعة نفسها متجاورَين. وإليك خوارزميةً تفعل ذلك بالضبط.

عيّن أيّ رأسٍ ليكون الجذر. ضع هذا الرأس في المجموعة $A\text{.}$ والآن ضع جميع أبناء الجذر في المجموعة $B\text{.}$ ولا شيءٌ من هذه الأبناء متجاور (فهم شُقَقاء)، إذن نحن على ما يرام حتى الآن. والآن ضع في $A$ كلَّ ابنٍ لكلّ رأسٍ في $B$ (أي كلَّ حفيدٍ للجذر). وواصل المضيّ حتى تُسنَد جميعُ الرؤوس إلى إحدى المجموعتَين، مبدّلًا بين $A$ و$B$ في كلّ «جيل». أي أنّ الرأس يكون في المجموعة $B$ إذا وفقط إذا كان ابنَ رأسٍ في المجموعة $A\text{.}$

والمفتاحُ في الطريقة التي قسّمنا بها الشجرةَ في المثال هو معرفةُ أيّ رأسٍ نسنِد إلى مجموعةٍ تالية. فقد اخترنا زيارةَ جميع رؤوس الجيل نفسه قبل أيّ رأسٍ من الجيل التالي. واسمُ هذا عادةً البحثَ في العرض (breadth-first search) (ونقول «بحث» لأنّك كثيرًا ما تجتاز شجرةً بعينابِ رؤوسٍ ذات خواصّ معيّنة).

وفي المقابل، كان بإمكاننا أيضًا أن نقسم الشجرةَ بترتيبٍ مختلف. ابدأ بالجذر؛ ضعه في $A\text{.}$ ثمّ ابحث عن ابنٍ واحدٍ للجذر تضعه في $B\text{.}$ ثمّ ابحث عن ابنٍ لذلك الرأس، وضعه في $A\text{,}$ ثمّ ابحث عن ابنه، وضعه في $B\text{,}$ وهكذا. وحين تصل إلى رأسٍ ليس له أبناء، ارجع إلى أصله، وانظر إلى ما إذا كان لهذا الأصل أبناءٌ آخرون. فنحن نبتعد عن الجذر بأقصى سرعة، ثمّ نتراجع إلى الوراء حتى نستطيع المضيّ قدمًا من جديد. واسمُ هذا البحثَ في العمق (depth-first search).

ويمكن لهذه الشروح الخوارزمية أن تصلح برهانًا على أنّ كلّ شجرةٍ ثنائية الطرف، وإن كان يلزم العنايةُ لإثبات أنّ الخوارزميّتين صحيحتان. ويُطلب في التمارين منهجٌ آخر لإثبات أنّ جميع الأشجار ثنائية الطرف، بالاعتماد على التعريض.

أسئلة القراءة

1.

لنفترض أنّ $T$ شجرةٌ فيها 10 رؤوس. أيُّ العبارات التالية لا بدّ أن تكون صحيحةً عن $T\text{?}$ اختر كلّ ما ينطبق.

• في $T$ مسارٌ فريد بين كلّ زوج من الرؤوس.
• لو حذفتَ أيّ حافةٍ من $T\text{,}$ لكان الرسمُ البياني الناتج غير متصل.
• لو أضفتَ أيّ حافةٍ بين رأسَين في $T$ (لم يكونا متجاورَين من قبل)، لكان في الرسم البياني الناتج دورة.
• في $T$ رأسان بالضبط من الدرجة الأولى.

2.

إذا كانت شجرةٌ فيها 20 رأسًا، فكم حافةً فيها؟

عدد الحوافّ:

3.

ما الأسئلة التي خطرت ببالك بعد قراءة هذا القسم؟ اكتب سؤالًا واحدًا على الأقلّ عن محتوى هذا القسم يثير فضولك.