السلف المشترك الأدنى: غير الجذر وقد تتغير الإجابة

الخلاصة السريعة

عندما يكون الجذر A، مسار D نحو الجذر هو D–B–A، ومسار F هو F–E–B–A. المشتركان A و B، و B أبعد عن الجذر، فيكون الجواب B. عندما نجعل F جذرًا، يصير مسار D نحو الجذر D–B–E–F، ومسار F هو F وحده؛ فيكون الجواب F. الحواف لم تتغير، لكن علاقة السلف تتبع الجذر المختار.

• السلف المشترك الأدنى يقع على مساري الرأسين نحو الجذر، ونختار بين الرؤوس المشتركة الأبعد عن الجذر. يشمل مسار الرأس نفسه؛ وإذا كان أحد الرأسين سلفًا للآخر، فهو الجواب. [1]
• حواف المثال غير الموجهة A–B و A–C و B–D و B–E و E–F فقط. عند الجذر A أعماق A و B و C و D و E و F هي 0 و 1 و 1 و 2 و 2 و 3؛ العمق هنا عدد حواف المسار من الجذر.
• للرأسين D و F عند الجذر A، المشتركان A و B بعمقي 0 و 1؛ نختار B. للرأسين D و C يكون المشترك A وحده، فيكون A الجواب.
• للرأسين E و F يكون الجواب E، لأنه يقع على مسار F نحو الجذر A. وللزوج D,D يكون الجواب D؛ لا نشترط أن يكون السلف مختلفًا عن الرأسين.
• عند تغيير الجذر إلى F مع إبقاء الحواف، يصبح جواب D,F هو F، وجواب D,C هو B. لكن جواب D,D يبقى D؛ تغيير الجذر قد يغير الإجابة ولا يفرض تغيير كل إجابة.
• الأدنى يعني أكبر عمق بين الأسلاف المشتركة، لا الأقل على الصفحة أو صاحب أصغر اسم. حدد الجذر والرأسين في الشجرة نفسها؛ إذا أضفت G معزولًا، فلا يقع D و G في شجرة متصلة واحدة بهذا الرسم.

ثبت الشجرة والجذر وما يدخل ضمن الأسلاف

السلف المشترك الأدنى لرأسين هو الرأس المشترك على مساريهما نحو الجذر، والأبعد عن الجذر بين المشتركين. وإذا وقع أحد الرأسين على مسار الآخر نحو الجذر، كان هو الجواب. [1]

نختار الشجرة ذات الرؤوس A و B و C و D و E و F، والحواف A–B و A–C و B–D و B–E و E–F. الحواف غير موجهة، ولا توجد حافة إضافية. اخترنا A جذرًا أولًا، ثم سنختار F جذرًا للمقارنة دون تغيير الحواف.

في هذا المقال نعد الرأس نفسه ضمن مساره نحو الجذر. نسمي الرأس التالي على ذلك المسار أباه، باستثناء الجذر الذي لا أب له في الوصف. مع الجذر A، أب B وأب C هو A، وأب D وأب E هو B، وأب F هو E.

نقيس العمق بعدد الحواف من الجذر؛ عمق A هو 0، وعمق B و C هو 1، وعمق D و E هو 2، وعمق F هو 3. لا أوزان أو وحدات طول في هذا المثال. الأسهم في الصورتين تبين الأب إلى الابن وفق الجذر، ولا تغير حواف الشجرة الأصلية إلى قيود عبور.

تقاطع مساري D و F يعطي A و B، ثم نختار B

من D نحو الجذر A نسير D–B–A، ومن F نسير F–E–B–A. الرأس D ليس على المسار الثاني، ولا E أو F على المسار الأول. المشترك هو A و B فقط.

عمق A يساوي 0، وعمق B يساوي 1. نختار B لأنه أعمق بين المشتركين. وجود A على المسارين لا يجعله الجواب تلقائيًا؛ المطلوب المشترك الأدنى، لا أي سلف مشترك.

أما الزوج D,C فمسار C نحو الجذر هو C–A. يتقاطع مع D–B–A عند A وحده، لذا يكون A الجواب. وفي الزوج C,F لا يوجد مشترك سوى A أيضًا. لا نضيف B لأنه لا يقع على مسار C إلى الجذر.

يسجل الجدول أزواجًا مختلفة والأسلاف المشتركة والجواب عند الجذر A. نعرض المشتركين بترتيب أسمائهم فقط؛ هذا الترتيب ليس معيار الاختيار. الدائرة الخضراء في الصورة الرئيسية تحدد B جواب الزوج D,F، مع الجذر A بالأزرق.

قد يكون الجواب أحد الرأسين أو الرأس نفسه

للزوج E,F يكون مسار E نحو الجذر E–B–A، ومسار F هو F–E–B–A. المشترك A و B و E بأعماق 0 و 1 و 2، فيكون E الأدنى. لا نشترط أن نعود إلى B لمجرد أن E أحد الرأسين المسؤول عنهما.

وللزوج D,D نستعمل المسار D–B–A في الطرفين. المشتركون A و B و D، وأعمقهم D بعمق 2. الجواب D ينسجم مع إدراج البداية نفسها ضمن مسار الأسلاف؛ استبعادها يغير تعريف السؤال الذي نستخدمه.

وفي الزوج A,F، مسار A إلى الجذر A هو A وحده، فيكون المشترك الوحيد A. تعطي هذه الحالات طريقة لفحص اصطلاحك قبل الجدول: هل يشمل المسار الرأس نفسه، وهل يمكن أن يكون أحد طرفي السؤال هو الجواب؟ هنا الجواب نعم في الحالتين.

اجعل F جذرًا وأعد كتابة المسارين

نغير الجذر إلى F ونبقي A–B و A–C و B–D و B–E و E–F كما هي. الآن من F نسير إلى E ثم B، ومنها إلى A و D، ثم من A إلى C. الأعماق الجديدة F عند 0، و E عند 1، و B عند 2، و A و D عند 3، و C عند 4.

للزوج D,F يصير المسار الأول D–B–E–F، والثاني F وحده. المشترك F، وهو الجواب الجديد. لا حاجة إلى إضافة حافة D–F كي يكون F سلفًا لـ D؛ يقع على مساره إلى الجذر بالفعل.

للزوج D,C، المساران D–B–E–F و C–A–B–E–F. المشتركون B و E و F، وأعماقهم 2 و 1 و 0، فيكون B الجواب. عند الجذر A كان الجواب A. تغيرت علاقة الأسلاف، مع بقاء الوصلات الأصلية كلها.

الجدول يقارن ثلاثة أزواج قبل تغيير الجذر وبعده. يبقى جواب D,D مساويًا D لأن المسار نفسه يستعمل في الطرفين ويبدأ بـ D. الصورة الداخلية تحتفظ بمواضع الرؤوس والحواف، وتغير اتجاه الأب إلى الابن وتحديد الجذر والجواب؛F يظل أسفل الصورة لكنه صار الجذر.

العمق يتبع الجذر، ولا يقاس من ارتفاع النقطة

الصور ليست مسطرة لقياس العمق. في الصورة الداخلية يقع F قريبًا من أسفل الصفحة، لكن عمقه 0 لأنه الجذر. نحدد الأعماق باتباع الحواف إلى الجذر، ثم نختار أعمق رأس مشترك، بدل تخمينه من شكل التفرع أو موضع الحرف.

لا نستنتج من كلمة سلف عمرًا أو قرابة أشخاص حقيقيين. أسماء A إلى F رؤوس مجردة في شجرة معلنة. ولم نفترض أن كل رأس له ابنان، أو أن الحواف تحمل وزنًا، أو أن ترتيب الأسماء يعطي الأولوية.

إذا أضفنا G بلا أي حافة إلى الرسم، فلا يوجد مسار G إلى الجذر A. الزوج D,G ليس داخل الشجرة المتصلة نفسها، فلا نطبّق عليه الحساب السابق كأن له مسارين إلى جذر واحد. يجب تحديد الشجرة التي يجري السؤال عليها قبل المقارنة.

احتفظ في أي جواب بالجذر والرأسين وقائمة الحواف واصطلاح إدراج الرأس نفسه. تغيير الجذر قد يغير النتيجة كما حدث للزوجين D,F و D,C، لكنه لا يغير دائمًا كل النتائج. الحساب هنا يشرح المعنى بأمثلة صغيرة؛ لا يدعي زمنًا لتنفيذ خوارزمية أو طريقة معالجة استعلامات كبيرة.