شجرة التريماو

الموسوعة الحرة

في نظرية المخططات ، شجرة تريمو للمخطط غير الموجهجي{\displaystyle G}هي نوع من أنواع الأشجار الممتدة ، وهي تعميم لأشجار البحث العمقية . وتُعرَّف بخاصية أن كل حافة من حوافهاجي{\displaystyle G}يربط هذا النوع من الأشجار بين سلف وحفيد في الشجرة. سُميت أشجار تريمو نسبةً إلى شارل بيير تريمو، وهو كاتب فرنسي من القرن التاسع عشر استخدم شكلاً من أشكال البحث العميق أولاً كاستراتيجية لحل المتاهات . [ 1 ] [ 2 ] كما تُسمى أيضًا بالأشجار الممتدة العادية ، خاصةً في سياق الرسوم البيانية اللانهائية. [ 3 ] [ 4 ]

جميع أشجار البحث العمقي أولًا وجميع المسارات الهاميلتونية هي أشجار تريموكس. في الرسوم البيانية المحدودة، كل شجرة تريموكس هي شجرة بحث عمقي أولًا، ولكن على الرغم من أن البحث العمقي أولًا هو بطبيعته تسلسلي، إلا أنه يمكن إنشاء أشجار تريموكس بواسطة خوارزمية متوازية عشوائية في فئة التعقيد RNC . يمكن استخدامها لتحديد عمق الشجرة في الرسم البياني، وكجزء من اختبار التسطح الأيسر-الأيمن لاختبار ما إذا كان الرسم البياني مستويًا . يسمح توصيف أشجار تريموكس في منطق الرتبة الثانية الأحادي للرسوم البيانية بالتعرف بكفاءة على خصائص الرسم البياني التي تتضمن الاتجاهات للرسوم البيانية ذات عرض الشجرة المحدود باستخدام نظرية كورسيل .

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

التعريف والأمثلة

شجرة تريموكس، للرسم البياني غير الموجهجي{\displaystyle G}، هي شجرة ممتدةتي{\displaystyle T}مع الخاصية التي، لكل حافةuv{\displaystyle uv}فيجي{\displaystyle G}، إحدى نقطتي النهايةu{\displaystyle u}وv{\displaystyle v}هو سلف للآخر. لكي يكون شجرة ممتدة، يجب أن يستخدم فقط حوافجي{\displaystyle G}وتشمل كل رأس، مع وجود مسار محدود فريد بين كل زوج من الرؤوس. بالإضافة إلى ذلك، لتحديد علاقة السلف والفرع في هذه الشجرة، يجب تحديد أحد رؤوسها كجذر لها.

إذا كان للرسم البياني المحدود مسار هاميلتوني ، فإن تحديد جذر هذا المسار عند إحدى نقطتيه ينتج شجرة تريموكس. بالنسبة لهذا المسار، كل زوج من الرؤوس هو زوج سلف-حفيد.

في الرسم البياني الموضح أدناه، تكون الشجرة ذات الحواف 1-3 و2-3 و3-4 شجرة Trémaux عندما تكون متجذرة عند الرأس  1 أو الرأس  2: كل حافة من الرسم البياني تنتمي إلى الشجرة باستثناء الحافة 1-2، والتي (بالنسبة لهذه الخيارات من الجذر) تربط زوجًا من السلف والذرية.

ومع ذلك، فإن تجذير نفس الشجرة عند الرأس  3 أو الرأس  4 ينتج شجرة متجذرة ليست شجرة تريموكس، لأنه مع هذا الجذر لم يعد 1 و2 سلفًا ونسلًا لبعضهما البعض.

في الرسوم البيانية المحدودة

وجود

كل رسم بياني متصل غير موجه ومحدود يحتوي على شجرة تريموكس واحدة على الأقل. [ 4 ] يمكن إنشاء مثل هذه الشجرة عن طريق إجراء بحث في العمق أولاً وربط كل رأس (باستثناء رأس البداية للبحث) بالرأس السابق الذي تم اكتشافه منه. تُعرف الشجرة التي تم إنشاؤها بهذه الطريقة باسم شجرة البحث في العمق أولاً.uv{\displaystyle uv}يمثل ضلعًا عشوائيًا في الرسم البياني، وu{\displaystyle u}إذا كان الرأس الذي سيتم الوصول إليه من خلال البحث هو الرأس الأسبق من بين الرأسين،v{\displaystyle v}يجب أن ينتمي إلى الشجرة الفرعية المنحدرة منu{\displaystyle u}في شجرة البحث العمقية أولاً، لأن البحث سيكتشف بالضرورةv{\displaystyle v}أثناء استكشاف هذه الشجرة الفرعية، إما من أحد الرؤوس الأخرى في الشجرة الفرعية أو، في حالة فشل ذلك، منu{\displaystyle u}مباشرةً. يمكن توليد كل شجرة تريموكس محدودة كشجرة بحث في العمق أولاً: إذاتي{\displaystyle T}هي شجرة تريموكس لرسم بياني محدود، ويستكشف بحث العمق أولاً الأبناء فيتي{\displaystyle T}من كل رأس قبل استكشاف أي رؤوس أخرى، سيتم بالضرورة توليدتي{\displaystyle T}باعتبارها شجرة بحث ذات عمق أولي.

البناء المتوازي

مشكلة لم تُحل في علوم الحاسوب
هل توجد خوارزمية NC متوازية حتمية لإنشاء أشجار تريموكس؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

يُعدّ إيجاد شجرة تريموكس التي يمكن إيجادها بواسطة خوارزمية بحث متسلسل في العمق أولًا، حيث يتم البحث عن جيران كل رأس بالترتيب وفقًا لهوياتهم، مسألةً كاملةً من فئة P. [ 5 ] ومع ذلك، من الممكن إيجاد شجرة تريموكس مختلفة بواسطة خوارزمية متوازية عشوائية ، مما يُظهر أن بناء أشجار تريموكس ينتمي إلى فئة التعقيد RNC . تعتمد هذه الخوارزمية على خوارزمية متوازية عشوائية أخرى، لإيجاد المطابقات المثالية ذات الوزن الأدنى في الرسوم البيانية الموزونة بـ 0-1. [ 6 ] حتى عام 1997، ظلّ من غير المعروف ما إذا كان من الممكن بناء شجرة تريموكس بواسطة خوارزمية متوازية حتمية، في فئة التعقيد NC . [ 7 ] إذا كان من الممكن إيجاد المطابقات في NC، فإنه يمكن أيضًا إيجاد أشجار تريموكس. [ 6 ]

التعبير المنطقي

من الممكن التعبير عن الخاصية التي تتمتع بها مجموعةتي{\displaystyle T}من الحواف مع خيار رأس الجذرر{\displaystyle r}يشكل شجرة تريموكس، في منطق الرتبة الثانية الأحادي للرسوم البيانية ، وتحديدًا في شكل هذا المنطق المسمى MSO 2 ، والذي يسمح بالتكميم على مجموعات الرؤوس والحواف. يمكن التعبير عن هذه الخاصية كاقتران للخصائص التالية:

  • يتم توصيل الرسم البياني بواسطة الحواف فيتي{\displaystyle T}يمكن التعبير عن ذلك منطقيًا على النحو التالي: لكل مجموعة جزئية غير فارغة من رؤوس الرسم البياني، توجد حافة فيتي{\displaystyle T}مع وجود نقطة نهاية واحدة فقط في المجموعة الفرعية المعطاة.
  • تي{\displaystyle T}هي غير دورية. ويمكن التعبير عن ذلك منطقياً بالقول إنه لا توجد مجموعة جزئية غير فارغة.ج{\displaystyle C}لتي{\displaystyle T}والتي يكون كل رأس منها متصلاً إما بصفر أو بحافتين منج{\displaystyle C}.
  • كل حافةهـ{\displaystyle e}ليس فيتي{\displaystyle T}يربط زوجًا من الرؤوس السلفية والذرية فيتي{\displaystyle T}هذا صحيح عندما تكون كلتا نقطتي النهايةهـ{\displaystyle e}ينتمي إلى مسار فيتي{\displaystyle T}ويمكن التعبير عنها منطقياً على النحو التالي: بالنسبة لجميع الحوافهـ{\displaystyle e}، يوجد مجموعة جزئيةP{\displaystyle P}لتي{\displaystyle T}بحيث يكون هناك رأسان بالضبط، أحدهمار{\displaystyle r}، تقع على حافة واحدة منP{\displaystyle P}وبحيث تكون كلتا نقطتي النهايةهـ{\displaystyle e}تقع على حافة واحدة على الأقل منP{\displaystyle P}.

بمجرد تحديد شجرة تريموكس بهذه الطريقة، يمكن وصف اتجاه الرسم البياني المعطى، حتى في منطق الرتبة الثانية الأحادي، بتحديد مجموعة الحواف التي يكون اتجاهها من نقطة النهاية الأصلية إلى نقطة النهاية التابعة. يجب أن تكون الحواف المتبقية خارج هذه المجموعة موجهة في الاتجاه المعاكس. تتيح هذه التقنية تحديد خصائص الرسم البياني التي تتضمن الاتجاهات في منطق الرتبة الثانية الأحادي، مما يسمح باختبار هذه الخصائص بكفاءة على الرسوم البيانية ذات عرض الشجرة المحدود باستخدام نظرية كورسيل . [ 8 ]

إذا كان للرسم البياني مسار هاميلتوني ، فإن هذا المسار (الذي يبدأ من إحدى نهايتيه) هو أيضًا شجرة تريموكس. الرسوم البيانية غير الموجهة التي تتخذ كل شجرة تريموكس فيها هذا الشكل هي الرسوم البيانية الدورية ، والرسوم البيانية الكاملة ، والرسوم البيانية الثنائية المتوازنة الكاملة . [ 9 ]

ترتبط أشجار تريموكس ارتباطًا وثيقًا بمفهوم عمق الشجرة . عمق الشجرة في الرسم البيانيجي{\displaystyle G}يمكن تعريفها بأنها أصغر عددد{\displaystyle d}والتي يوجد لها رسم بيانيح{\displaystyle H}، مع شجرة تريموكستي{\displaystyle T}من الارتفاعد{\displaystyle d}بحيثجي{\displaystyle G}هو رسم بياني فرعي منح{\displaystyle H}يُعادل عمق الشجرة المحدود، في عائلة من الرسوم البيانية، وجود مسار لا يمكن أن يظهر كرسم بياني فرعي للرسوم البيانية في تلك العائلة. العديد من المسائل الحسابية المعقدة على الرسوم البيانية لها خوارزميات قابلة للحل بمعاملات ثابتة عند تحديدها بواسطة عمق الشجرة لمدخلاتها. [ 10 ]

تلعب أشجار تريموكس أيضًا دورًا رئيسيًا في معيار فرايسيكس-روزنستيل للتسطيح لاختبار ما إذا كان الرسم البياني المعطى مستويًا . وفقًا لهذا المعيار، فإن الرسم البيانيجي{\displaystyle G}تكون مستوية إذا، بالنسبة لشجرة تريموكس معينةتي{\displaystyle T}لجي{\displaystyle G}ويمكن وضع الحواف المتبقية بطريقة متسقة على يسار أو يمين الشجرة، مع مراعاة القيود التي تمنع الحواف ذات الموضع نفسه من تقاطع بعضها البعض. [ 11 ]

في الرسوم البيانية اللانهائية

وجود

ليس لكل رسم بياني لانهائي شجرة امتداد عادية. على سبيل المثال، لا يمتلك الرسم البياني الكامل على مجموعة غير قابلة للعد من الرؤوس شجرة امتداد عادية: إذ لا يمكن أن تكون شجرة الامتداد العادية في الرسم البياني الكامل إلا مسارًا، ولكن المسار لا يمتلك إلا عددًا قابلًا للعد من الرؤوس. مع ذلك، يمتلك كل رسم بياني متصل على مجموعة قابلة للعد من الرؤوس شجرة امتداد عادية. [ 3 ] [ 4 ]

حتى في الرسوم البيانية القابلة للعد، قد لا ينجح البحث العميق أولاً في استكشاف الرسم البياني بأكمله في النهاية، [ 3 ] ولا يمكن إنشاء كل شجرة امتداد عادية عن طريق البحث العميق أولاً: لكي تكون شجرة بحث عميقة أولاً، يجب أن تحتوي شجرة الامتداد العادية القابلة للعد على مسار واحد لانهائي أو عقدة واحدة بها عدد لا نهائي من الأبناء (وليس كليهما).

القاصرون

إذا كان الرسم البياني لانهائيًاجي{\displaystyle G}يحتوي على شجرة امتداد عادية، وكذلك كل رسم بياني فرعي متصل منجي{\displaystyle G}يستنتج من ذلك أن الرسوم البيانية التي تحتوي على أشجار ممتدة عادية تتميز بوجود قاصرات محظورة . أحد نوعي القاصرات المحظورة يتكون من رسوم بيانية ثنائية الأجزاء يكون فيها أحد جانبي التقسيم الثنائي قابلاً للعد، والجانب الآخر غير قابل للعد، ولكل رأس درجة لانهائية. أما النوع الآخر من القاصرات المحظورة فيتكون من رسوم بيانية معينة مشتقة من أشجار أرونسزاجن . [ 12 ]

تعتمد تفاصيل هذا التوصيف على اختيار بديهيات نظرية المجموعات المستخدمة في صياغة الرياضيات. على وجه الخصوص، في نماذج نظرية المجموعات التي تكون فيها بديهية مارتن صحيحة وفرضية الاستمرارية خاطئة، يمكن استبدال فئة الرسوم البيانية ثنائية الأجزاء في هذا التوصيف بفئة فرعية محظورة واحدة. مع ذلك، بالنسبة للنماذج التي تكون فيها فرضية الاستمرارية صحيحة، تحتوي هذه الفئة على رسوم بيانية غير قابلة للمقارنة فيما بينها في ترتيب الفئات الفرعية. [ 13 ]

الغايات وقابلية القياس

ترتبط الأشجار الممتدة العادية ارتباطًا وثيقًا بنهايات الرسم البياني اللانهائي، وهي فئات تكافؤ للمسارات اللانهائية التي، بديهيًا، تمتد إلى اللانهاية في نفس الاتجاه. إذا كان للرسم البياني شجرة ممتدة عادية، فلا بد أن تحتوي هذه الشجرة على مسار لانهائي واحد فقط لكل نهاية من نهايات الرسم البياني. [ 14 ]

يمكن استخدام الرسم البياني اللانهائي لتكوين فضاء طوبولوجي من خلال اعتبار الرسم البياني نفسه مُركبًا تبسيطيًا وإضافة نقطة عند اللانهاية لكل طرف من أطرافه. وفقًا لهذه الطوبولوجيا، يمتلك الرسم البياني شجرة امتداد طبيعية إذا وفقط إذا أمكن تقسيم مجموعة رؤوسه إلى اتحاد قابل للعد من المجموعات المغلقة . بالإضافة إلى ذلك، يمكن تمثيل هذا الفضاء الطوبولوجي بفضاء متري إذا وفقط إذا كان للرسم البياني شجرة امتداد طبيعية. [ 14 ]

مراجع

  1. ↑ إيفن، شيمون (2011)، خوارزميات الرسوم البيانية (  الطبعة الثانية)، مطبعة جامعة كامبريدج، الصفحات 46-48 ، رقم ISBN  978-0-521-73653-4.
  2. ↑ سيدجويك، روبرت (2002)، الخوارزميات في لغة C++: خوارزميات الرسوم البيانية ( الطبعة الثالثة)، بيرسون للتعليم، الصفحات 149-157 ، ISBN   978-0-201-36118-6.
  3. 1 2 3 سوكوب، لايوش (2008)، "التوافقية اللانهائية: من المحدود إلى اللانهائي"، آفاق التوافقية ، دراسات جمعية بولياي الرياضية، المجلد 17، برلين: سبرينغر، الصفحات 189-213 ، doi : 10.1007/978-3-540-77200-2_10 ، ISBN   978-3-540-77199-9MR 2432534​ انظر على وجه الخصوص النظرية 3، صفحة  193 .
  4. 1 2 3 ديستل، راينهارد (2017)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173 ( الطبعة الخامسة)، برلين: سبرينغر، الصفحات 34-36 ، 220-221 ، 247، 251-252 ، doi : 10.1007/978-3-662-53622-3 ، ISBN    978-3-662-53621-6MR 3644391​ 
  5. ↑ ريف، جون هـ. (1985)، "البحث العميق أولاً هو تسلسلي بطبيعته"، رسائل معالجة المعلومات ، 20 (5): 229-234 ، doi : 10.1016/0020-0190(85)90024-9 ، MR 0801987 .
  6. 1 2 أغاروال، أ.؛ أندرسون، ر. ج. (1988)، "خوارزمية NC عشوائية للبحث العميق أولاً"، كومبيناتوريكا ، 8 (1): 1-12 ، doi : 10.1007/BF02122548 ، MR 0951989 ، S2CID 29440871  .
  7. ↑ كارغر، ديفيد ر .؛ موتاني، راجيف (1997)، " خوارزمية NC للقطع الدنيا"، مجلة SIAM للحوسبة ، 26 (1): 255-272 ، doi : 10.1137/S0097539794273083 ، MR 1431256 .
  8. ↑ كورسيل، برونو (1996)، "حول التعبير عن خصائص الرسم البياني في بعض أجزاء منطق الرتبة الثانية الأحادي" (ملف PDF) ، في إيمرمان، نيل ؛ كولايتيس، فوكيون ج. (محرران)، وقائع وصف النماذج المعقدة والمحدودة ، DIMACS، المجلد 31، الجمعية الأمريكية للرياضيات، الصفحات 33-62 ، MR 1451381   .
  9. ↑ شارتراند، غاري ؛ كرونك، هدسون ف. (1968)، "الرسوم البيانية القابلة للتتبع عشوائيًا"، مجلة SIAM للرياضيات التطبيقية ، 16 (4): 696-700 ، doi : 10.1137/0116056 ، MR 0234852 .
  10. ↑ نيشيتريل، ياروسلاف ؛ أوسونا دي مينديز، باتريس (2012)، "الفصل 6. الأشجار ذات الارتفاع المحدود وعمق الشجرة"، التناثر: الرسوم البيانية، والهياكل، والخوارزميات ، الخوارزميات والتوافقية، المجلد 28، هايدلبرغ: سبرينغر، الصفحات 115-144 ، doi : 10.1007/978-3-642-27875-4 ، ISBN   978-3-642-27874-7MR 2920058​ .
  11. ↑ دي فرايسيكس، هوبرت؛ روزنستيل، بيير (1982)، "توصيف التسطح باستخدام البحث العميق أولاً"، نظرية الرسم البياني (كامبريدج، 1981) ، حوليات الرياضيات المتقطعة، المجلد 13، أمستردام: نورث هولاند، الصفحات 75-80 ، MR 0671906   دي فرايسيكس، هوبرت؛ أوسونا دي مينديز، باتريس ؛ روزنستيل، بيير (2006)، "أشجار تريموكس والتسطيح"، المجلة الدولية لأسس علوم الحاسوب ، 17 (5): 1017-1029 ، arXiv : math/0610935 ، doi : 10.1142/S0129054106004248 ، MR 2270949 .
  12. ↑ ديستل، راينهارد؛ ليدر، إيمري (2001)، "الأشجار الممتدة العادية، وأشجار أرونسزاين، والقواطع المستبعدة" (ملف PDF) ، مجلة جمعية لندن الرياضية ، السلسلة الثانية، 63 (1): 16-32 ، doi : 10.1112/S0024610700001708 ، MR 1801714 ، S2CID 13980974  .
  13. ↑ بولر، ناثان؛ غيشكه، ستيفان؛ بيتز، ماكس (2016)، الحد الأدنى من العوائق للأشجار الممتدة العادية ، arXiv : 1609.01042 ، Bibcode : 2016arXiv160901042B
  14. 1 2 ديستل، راينهارد (2006)، "الفضاءات الطرفية والأشجار الممتدة"، مجلة نظرية التوافيق ، السلسلة ب، 96 (6): 846-854 ، CiteSeerX 10.1.1.63.9751 ، doi : 10.1016/j.jctb.2006.02.010 ، MR 2274079  .