عرض الشجرة

لأي ثابت ثابت${\displaystyle k}$، الرسوم البيانية لعرض الشجرة على الأكثر${\displaystyle k}$تُسمى جزئية${\displaystyle k}$الأشجار. تشمل عائلات الرسوم البيانية الأخرى ذات عرض الشجرة المحدود رسوم الصبار البيانية ، والغابات الزائفة ، والرسوم البيانية المتسلسلة المتوازية ، والرسوم البيانية الخارجية المستوية ، ورسوم هالين البيانية ، وشبكات أبولو . ^{[ 5 ]} تتميز رسوم التحكم في التدفق، التي تنشأ في تجميع البرامج المهيكلة، أيضًا بعرض شجرة محدود، مما يسمح بتنفيذ مهام معينة بكفاءة عليها، مثل تخصيص السجلات . ^{[ 6 ]}

لا تمتلك الرسوم البيانية المستوية عرض شجرة محدود ، لأن${\displaystyle n\times n}$الرسم البياني الشبكي هو رسم بياني مستوٍ بعرض شجرة يساوي بالضبط${\displaystyle n}$لذلك، إذا${\displaystyle F}$إذا كانت عائلة الرسوم البيانية مغلقة جزئيًا وذات عرض شجري محدود، فلا يمكنها أن تشمل جميع الرسوم البيانية المستوية. وعلى العكس من ذلك، إذا لم يكن من الممكن أن يظهر رسم بياني مستوٍ ما كرسم بياني جزئي للرسوم البيانية في هذه العائلة، فلا يمكن أن يشمل جميع الرسوم البيانية المستوية.${\displaystyle F}$ثم هناك ثابت${\displaystyle k}$بحيث تكون جميع الرسوم البيانية في${\displaystyle F}$عرض الشجرة على الأكثر${\displaystyle k}$أي أن الشروط الثلاثة التالية متكافئة مع بعضها البعض: ^{[ 7 ]}

1. ${\displaystyle F}$هي عائلة مغلقة جزئياً من الرسوم البيانية ذات عرض الشجرة المحدود؛
2. أحد القاصرين المحظورين، وهو عدد محدود، والذي يميز${\displaystyle F}$مستوي؛
3. ${\displaystyle F}$هي عائلة رسوم بيانية مغلقة جزئياً لا تشمل جميع الرسوم البيانية المستوية.

لكل قيمة محدودة من${\displaystyle k}$، الرسوم البيانية لعرض الشجرة على الأكثر${\displaystyle k}$قد تتميز بمجموعة محدودة من القواسم الصغرى المحظورة . (أي، أي رسم بياني بعرض شجرة أكبر من${\displaystyle k}$(يتضمن أحد الرسوم البيانية في المجموعة كرسم بياني فرعي.) تتضمن كل مجموعة من هذه المجموعات من الرسوم البيانية الفرعية المحظورة رسمًا بيانيًا مستويًا واحدًا على الأقل.

• ل${\displaystyle k=1}$، والمخطط الفرعي المحظور الفريد هو مخطط دورة مكون من 3 رؤوس . ^{[ 5 ]}
• ل${\displaystyle k=2}$، والمخطط الفرعي المحظور الفريد هو الرسم البياني الكامل ذو 4 رؤوس${\displaystyle K_{4}}$[ ^{5 ]​}
• ل${\displaystyle k=3}$هناك أربعة قاصرين ممنوعين:${\displaystyle K_{5}}$، ورسم بياني للمجسم الثماني الأوجه ، ورسم بياني للمنشور الخماسي ، ورسم بياني لفاغنر . ومن بين هذه الرسوم البيانية، فإن الرسمين البيانيين متعددي الأوجه مستويان. ^{[ 8 ]}

بالنسبة للقيم الأكبر من${\displaystyle k}$يزداد عدد القاصرين المحظورين على الأقل بنفس سرعة الدالة الأسية لـ${\displaystyle {\sqrt {k}}}$^{[ 9 ]} ومع ذلك ، فإن الحدود العليا المعروفة لحجم وعدد القاصرين المحظورين أعلى بكثير من هذا الحد الأدنى. ^{[ 10 ]}

إنها${\displaystyle {\mathsf {NP}}}$- أكمل لتحديد ما إذا كان الرسم البياني المعطى${\displaystyle G}$يبلغ عرض الشجرة على الأكثر متغيرًا معينًا${\displaystyle k}$[ ^{11 ] ومع ذلك ،} عندما${\displaystyle k}$أي ثابت ثابت، الرسوم البيانية ذات عرض الشجرة${\displaystyle k}$يمكن التعرف عليها، وعرضها${\displaystyle k}$تم إنشاء تحليل الشجرة لهم في وقت خطي. ^{[ 12 ]} يعتمد هذا الخوارزمية على الوقت${\displaystyle k}$هو أسّي.

نظراً للدور الذي يلعبه عرض الشجرة في عدد هائل من المجالات، فقد طُوّرت خوارزميات عملية ونظرية مختلفة لحساب عرض الشجرة في الرسم البياني. وبحسب التطبيق، يُمكن تفضيل نسبة تقريب أفضل ، أو اعتماد أفضل لوقت التشغيل على حجم المدخلات أو عرض الشجرة. يُقدّم الجدول أدناه نظرة عامة على بعض خوارزميات عرض الشجرة.${\displaystyle k}$هو عرض الشجرة و${\displaystyle n}$يمثل عدد رؤوس الرسم البياني المدخل${\displaystyle G}$كل خوارزمية من الخوارزميات تُخرج النتائج في الوقت المحدد${\displaystyle f(k)\cdot g(n)}$تحليل للعرض مُعطى في عمود التقريب. على سبيل المثال، خوارزمية بودليندر (1996) في الوقت${\displaystyle 2^{O(k^{3})}\cdot n}$إما أن يقوم بإنشاء تفكيك شجري للرسم البياني المدخل${\displaystyle G}$عرضها لا يتجاوز${\displaystyle k}$أو تقارير تفيد بأن عرض الشجرة لـ${\displaystyle G}$أكثر من${\displaystyle k}$وبالمثل، فإن خوارزمية بودليندر وآخرون (2016) في الوقت${\displaystyle 2^{O(k)}\cdot n}$إما أن يقوم بإنشاء تفكيك شجري للرسم البياني المدخل${\displaystyle G}$عرضها لا يتجاوز${\displaystyle 5k+4}$أو تقارير تفيد بأن عرض الشجرة لـ${\displaystyle G}$أكثر من${\displaystyle k}$قام كورهونين (2021) بتحسين عرض التفكيك إلى${\displaystyle 2k+1}$في نفس مدة التشغيل.

تقريب	f ( k )	g ( n )	مرجع
بالضبط	${\displaystyle 1}$	${\displaystyle O(n^{k+2})}$	أرنبورغ، كورنيل وبروسكوروفسكي (1987)
${\displaystyle 4k+3}$	${\displaystyle O(3^{3k})}$	${\displaystyle O(n^{2})}$	روبرتسون وسيمور (1995)
${\displaystyle 8k+7}$	${\displaystyle 2^{O(k\log n)}}$	${\displaystyle O(n\log ^{2}n)}$	لاغرغرين (1996)
${\displaystyle 5k+4}$(أو${\displaystyle 7k+6}$)	${\displaystyle 2^{O(k\log n)}}$	${\displaystyle O(n\log n)}$	ريد (1992)
بالضبط	${\displaystyle 2^{O(k^{3})}}$	${\displaystyle O(n)}$	بودليندر (1996)
${\displaystyle O\left(k\cdot {\sqrt {\log k}}\right)}$	${\displaystyle 1}$	${\displaystyle n^{O(1)}}$	فيجي وهاجياغاي ولي (2008)
${\displaystyle 4.5k+4}$	${\displaystyle 2^{3k}}$	${\displaystyle O(n^{2})}$	أمير (2010)
${\displaystyle {\tfrac {11}{3}}k+4}$	${\displaystyle 2^{3.6982k}}$	${\displaystyle O(n^{3}\log ^{4}n)}$	أمير (2010)
بالضبط	${\displaystyle 1}$	${\displaystyle O(1.7347^{n})}$	فومين، تودينكا وفيلانجير (2015)
${\displaystyle 3k+2}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n\log n)}$	بودليندر وآخرون (2016)
${\displaystyle 5k+4}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	بودليندر وآخرون (2016)
${\displaystyle k^{2}}$	${\displaystyle k^{7}}$	${\displaystyle O(n\log n)}$	فومين وآخرون (2018)
${\displaystyle 5k+4}$	${\displaystyle 2^{8.765k}}$	${\displaystyle O(n\log n)}$	بلباسي وفورر (2021أ)
${\displaystyle 2k+1}$	${\displaystyle 2^{O(k)}}$	${\displaystyle O(n)}$	كورهونين (2021)
${\displaystyle 5k+4}$	${\displaystyle 2^{6.755k}}$	${\displaystyle O(n\log n)}$	بلباسي وفورر (2021ب)
بالضبط	${\displaystyle 2^{O(k^{2})}}$	${\displaystyle O(n^{4})}$	كورهونين ولوكشتانوف (2023)
${\displaystyle (1+\varepsilon )k}$	${\displaystyle k^{O(k/\varepsilon )}}$	${\displaystyle O(n^{4})}$	كورهونين ولوكشتانوف (2023)

من غير المعروف ما إذا كان تحديد عرض الشجرة للرسوم البيانية المستوية مسألة NP-كاملة، أو ما إذا كان من الممكن حساب عرض الشجرة في وقت متعدد الحدود . ^{[ 13 ]}

من الناحية العملية، يمكن لخوارزمية Shoikhet & Geiger (1997) تحديد عرض الشجرة للرسوم البيانية التي تحتوي على ما يصل إلى 100 رأس وعرض الشجرة الذي يصل إلى 11، وإيجاد إكمال وتر لهذه الرسوم البيانية بعرض الشجرة الأمثل.

بالنسبة للرسوم البيانية الأكبر حجمًا، يمكن استخدام تقنيات البحث، مثل البحث بالتفرع والتقييد، لحساب عرض الشجرة. تتميز هذه الخوارزميات بأنها تعمل في أي وقت ، فإذا توقفت مبكرًا، فإنها تُخرج حدًا أعلى لعرض الشجرة. وقد اقترح فيبهاف جوجات ورينا ديختر خوارزمية من هذا النوع عام ٢٠٠٤. ولتوفير حد أدنى لعرض الشجرة لفروع هذا البحث، يقومان بإنشاء رسم بياني فرعي عن طريق تقليص حافة بين رأس ذي درجة دنيا وأحد جيرانه بشكل متكرر، حتى يتبقى رأس واحد فقط. ويُضمن أن تكون القيمة القصوى للدرجات الدنيا في هذه الرسوم البيانية الفرعية المُنشأة حدًا أدنى لعرض الشجرة. ^{[ ١٤ ]} وقد حسّن أليكس داو وريتش كورف هذه الخوارزمية باستخدام البحث الأفضل أولًا . ^{[ ١٥ ]}

في مطلع سبعينيات القرن العشرين، لوحظ أن فئة واسعة من مسائل التحسين التوافقي المعرفة على الرسوم البيانية يمكن حلها بكفاءة باستخدام البرمجة الديناميكية غير التسلسلية ، شريطة أن يكون للرسم البياني بُعد محدود ^{[ 16 ]} ، وهو مُعامل أثبت بودليندر (1998) أنه يُكافئ عرض الشجرة . لاحقًا، لاحظ العديد من الباحثين بشكل مستقل في أواخر ثمانينيات القرن العشرين ^{[ 17 ]} أن العديد من المسائل الخوارزمية التي تُصنف ضمن مسائل NP-complete للرسوم البيانية العشوائية يمكن حلها بكفاءة باستخدام البرمجة الديناميكية للرسوم البيانية ذات عرض الشجرة المحدود، وذلك باستخدام تحليلات الشجرة لهذه الرسوم البيانية.

على سبيل المثال، مشكلة تلوين رسم بياني بعرض شجرة${\displaystyle k}$يمكن حل هذه المشكلة باستخدام خوارزمية البرمجة الديناميكية على تحليل شجري للرسم البياني. لكل حقيبة${\displaystyle X_{i}}$من تجزئة الشجرة، وكل قسم من رؤوس${\displaystyle X_{i}}$يُقسّم البرنامج البيانات إلى فئات لونية، ويحدد ما إذا كان هذا التلوين صالحًا ويمكن تعميمه على جميع العقد الفرعية في تحليل الشجرة، وذلك من خلال دمج معلومات من نوع مماثل محسوبة ومخزنة في تلك العقد. ويجد البرنامج الناتج تلوينًا أمثلًا لـ${\displaystyle n}$رسم بياني ذو رؤوس متعددة في الزمن${\displaystyle O(k^{k+O(1)}n)}$، وهو حد زمني يجعل هذه المشكلة قابلة للحل باستخدام معلمات ثابتة .

بالنسبة لفئة واسعة من المسائل، توجد خوارزمية خطية لحل مسألة من هذه الفئة إذا تم توفير تحليل شجري ذي عرض شجري ثابت ومحدود. وبالتحديد، تنص نظرية كورسيل ^{[ 18 ]} على أنه إذا أمكن التعبير عن مسألة بيانية بمنطق الرسوم البيانية باستخدام منطق الرتبة الثانية الأحادي ، فإنه يمكن حلها في زمن خطي على الرسوم البيانية ذات العرض الشجري المحدود. منطق الرتبة الثانية الأحادي هو لغة لوصف خصائص الرسوم البيانية، ويستخدم البنى التالية:

• العمليات المنطقية، مثل${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• اختبارات العضوية، مثل${\displaystyle e\in E}$،${\displaystyle v\in V}$
• التكميمات على الرؤوس، والحواف، ومجموعات الرؤوس، و/أو مجموعات الحواف، مثل${\displaystyle \forall v\in V}$،${\displaystyle \exists e\in E}$،${\displaystyle \exists I\subset V}$،${\displaystyle \forall F\subset E}$
• اختبارات وقوع النقاط عند الرؤوس والحواف (${\displaystyle u}$هي نقطة نهاية لـ${\displaystyle e}$)، وبعض الإضافات التي تسمح بأمور مثل التحسين.

لنأخذ على سبيل المثال مسألة تلوين الرسوم البيانية بثلاثة ألوان . بالنسبة للرسم البياني${\displaystyle G=(V,E)}$تطرح هذه المسألة سؤالاً حول إمكانية تعيين كل رأس${\displaystyle v\in V}$أحد ثلاثة ألوان بحيث لا يتم تخصيص نفس اللون لرأسين متجاورين. يمكن التعبير عن هذه المشكلة في منطق الرتبة الثانية الأحادي كما يلي: $${\displaystyle \exists W_{1}\subseteq V\ \exists W_{2}\subseteq V\ \exists W_{3}\subseteq V\ \left({\begin{aligned}&\forall v\in V\ (v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge {}\\&\operatorname {independent} (W_{1})\wedge {}\\&\operatorname {independent} (W_{2})\wedge {}\\&\operatorname {independent} (W_{3})\\\end{aligned}}\right),}$$ أين${\displaystyle W_{1}}$،${\displaystyle W_{2}}$،${\displaystyle W_{3}}$تمثل المجموعات الفرعية من الرؤوس التي تحتوي على كل لون من الألوان الثلاثة، حيث تمثل التعبيرات الفرعية${\displaystyle \operatorname {independent} (W_{i})}$تُعرَّف بأنها تعني $${\displaystyle \operatorname {independent} (W_{i})\equiv \forall e\in E\ \exists v\in V\ (\operatorname {endpoint} (v,e)\wedge \neg v\in W_{i}).}$$ (ليس من الضروري تضمين شرط أن المجموعات في هذه الصيغة)${\displaystyle W_{i}}$(يكون منفصلاً.) لذلك، وفقًا لنتائج كورسيل، يمكن حل مشكلة التلوين الثلاثي في ​​وقت خطي للرسم البياني المعطى بتقسيم الشجرة ذي عرض الشجرة الثابت المحدود.

يُعرَّف عرض المسار في الرسم البياني تعريفًا مشابهًا جدًا لعرض الشجرة عند تحليلها إلى أجزاء، ولكنه يقتصر على تحليلات الأشجار التي تكون فيها الشجرة الأساسية للتحليل عبارة عن رسم بياني للمسارات . ويمكن تعريف عرض المسار من الرسوم البيانية الفاصلية بشكل مشابه لتعريف عرض الشجرة من الرسوم البيانية الوترية. ونتيجة لذلك، يكون عرض المسار في الرسم البياني دائمًا أكبر من أو يساوي عرض الشجرة، ولكنه لا يمكن أن يزيد عنه إلا بمعامل لوغاريتمي. ^{[ 5 ]} وهناك معيار آخر، وهو عرض نطاق الرسم البياني ، له تعريف مشابه من الرسوم البيانية الفاصلية الصحيحة ، وهو أكبر من أو يساوي عرض المسار. وتشمل المعايير الأخرى ذات الصلة عمق الشجرة ، وهو عدد محدود لعائلة رسوم بيانية مغلقة جزئيًا إذا وفقط إذا كانت العائلة تستبعد مسارًا، والانحلال ، وهو مقياس لتباعد الرسم البياني يساوي على الأكثر عرض الشجرة.

لأن عرض الشجرة لـ${\displaystyle n\times n}$الرسم البياني الشبكي هو${\displaystyle n}$، عرض الشجرة للرسم البياني${\displaystyle G}$يكون دائمًا أكبر من أو يساوي حجم أكبر مربع فرعي في الشبكة${\displaystyle G}$في الاتجاه الآخر، تُظهر نظرية الشبكة الصغرى لروبرتسون وسيمور وجود دالة غير محدودة${\displaystyle f}$بحيث يكون أكبر مخطط شبكي مربع لرسم بياني بعرض شجرة${\displaystyle k}$له حجم على الأقل${\displaystyle f(k)}$[ ^{19 ]} أفضل الحدود المعروفة ^في${\displaystyle f}$هل هذا${\displaystyle f}$يجب أن يكون على الأقل${\displaystyle \Omega (k^{d})}$لبعض الثوابت الثابتة${\displaystyle d>0}$، وعلى الأكثر ^{[ 20 ]}$${\displaystyle O\left({\sqrt {r/\log r}}\right).}$$

(لـ)${\displaystyle \Omega }$(انظر ترميز Big O في الحد الأدنى ). توجد حدود أدق معروفة لعائلات الرسوم البيانية المقيدة، مما يؤدي إلى خوارزميات فعالة للعديد من مسائل تحسين الرسوم البيانية على تلك العائلات من خلال نظرية ثنائية الأبعاد . ^{[ 21 ]} توفر نظرية شبكة هالين نظيرًا للعلاقة بين عرض الشجرة وحجم الشبكة الصغرى للرسوم البيانية اللانهائية. ^{[ 22 ]}

عائلة${\displaystyle F}$يُقال إن مجموعة من الرسوم البيانية المغلقة تحت أخذ الرسوم البيانية الفرعية لها عرض شجري محلي محدود ، أو خاصية القطر-العرض الشجري ، إذا كان عرض الشجرة للرسوم البيانية في المجموعة محدودًا من الأعلى بدالة لقطرها . وإذا افترضنا أيضًا أن المجموعة مغلقة تحت أخذ الرسوم البيانية الفرعية ، فإن${\displaystyle F}$يكون عرض الشجرة المحلي محدودًا إذا وفقط إذا كان أحد القاصرين المحظورين لـ${\displaystyle F}$هو رسم بياني للقمة . ^{[ 23 ]} أظهرت البراهين الأصلية لهذه النتيجة أن عرض الشجرة في عائلة رسوم بيانية خالية من الرؤوس الصغرى ينمو على الأكثر ضعفًا أُسّيًا كدالة للقطر؛ ^{[ 24 ]} ثم اختُزل هذا إلى أُسّي مفرد ^{[ 21 ]} وأخيرًا إلى حد خطي. ^{[ 25 ]} يرتبط عرض الشجرة المحلي المحدود ارتباطًا وثيقًا بنظرية الخوارزميات ثنائية الأبعاد ، ^{[ 26 ]} ويمكن تحديد كل خاصية من خصائص الرسم البياني القابلة للتعريف في منطق الرتبة الأولى لعائلة رسوم بيانية خالية من الرؤوس الصغرى في وقت يزيد قليلاً عن الخطي. ^{[ 27 ]}

من الممكن أيضًا أن تمتلك فئة من الرسوم البيانية غير المغلقة تحت تأثير المحددات الصغرى عرضًا شجريًا محليًا محدودًا. وينطبق هذا بشكل بديهي على فئة الرسوم البيانية ذات الدرجة المحدودة، حيث أن الرسوم البيانية الفرعية ذات القطر المحدود لها حجم محدود. ومن الأمثلة الأخرى الرسوم البيانية المستوية أحادية البعد ، وهي الرسوم البيانية التي يمكن رسمها في المستوى بتقاطع واحد لكل حافة، وبشكل أعم، الرسوم البيانية التي يمكن رسمها على سطح ذي جنس محدود بعدد محدود من التقاطعات لكل حافة. ​​وكما هو الحال مع عائلات الرسوم البيانية المغلقة تحت تأثير المحددات الصغرى ذات العرض الشجري المحلي المحدود، فقد مهدت هذه الخاصية الطريق لخوارزميات تقريب فعالة لهذه الرسوم البيانية. ^{[ 28 ]}

عرّف هالين (1976) فئة من معلمات الرسم البياني أطلق عليها اسم دوال S ، والتي تشمل عرض الشجرة. يجب أن تكون هذه الدوال، التي تربط الرسوم البيانية بالأعداد الصحيحة، صفرًا على الرسوم البيانية التي لا تحتوي على حواف ، وأن تكون رتيبة بشكل طفيف (دالة).${\displaystyle f}$يُشار إليه باسم "النغمة الرتيبة الصغرى" إذا، كلما${\displaystyle H}$هو قاصر من${\displaystyle G}$، لدى المرء${\displaystyle f(H)\leq f(G)}$تزداد قيمة الدالة بمقدار واحد عند إضافة رأس جديد مجاور لجميع الرؤوس السابقة ، وتختار القيمة الأكبر من بين الرسمين الفرعيين على جانبي فاصل الزمر . تشكل مجموعة جميع هذه الدوال شبكة كاملة تحت عمليتي التصغير والتكبير العنصري. العنصر العلوي في هذه الشبكة هو عرض الشجرة، والعنصر السفلي هو عدد هادويغر ، وهو حجم أكبر قاصر كامل في الرسم البياني المعطى.