عرض درخت
در نظریه گراف، عرض درختی یک گراف بدون جهت، عددی‌ است که مربوط به آن گراف است. این عدد می‌تواند به طرق مختلفی تعریف شود: اندازهٔ بزرگ‌ترین راس در تجریهٔ درختی آن گراف، اندازهٔ بزرگ‌ترین خوشه در تکمیل وتری و ... .مفهوم عرض درختی یک گراف، در ابتدا توسط Umberto Bertelé و Francesco Brioschi در سال ۱۹۷۲ معرفی شد. بعدها به‌صورت جدی توسط Neil Robertson و Paul Seymour در سال ۱۹۸۴ مجدداً معرفی گردید. برای تعریف عرض درختی یک گراف، ابتدا باید تجریهٔ درختی گراف را تعریف کنیم.
تجزیهٔ درختی گراف formula_1، درختی‌ است مانند formula_2 با رئوس formula_3 (به این رئوس کیف یا bag می‌گویند) که در آن هر formula_4 یک زیرمجموعه‌ای از formula_5 است که شرایط زیر را ارضا کند: تجزیهٔ درختی یک گراف، یکتا نیست. بدیهی‌ترین تجزیهٔ درختی، قراردادن تمامی رئوس گراف در یک کیف است که در این صورت هر گراف یک تجزیه با عرض formula_14 دارد؛ بنابراین برای هر گراف تجزیه‌های درختی متعددی وجود دارد. عرض درختی یک تجزیهٔ درختی، برابر است با سایز بزرگ‌ترین کیف آن منهای یک. عرض درختی یک گراف نیز که با formula_15 نمایش داده می‌شود، برابرست با کم‌ترین عرض درختی میان تمامی تجریه‌های درختی آن گراف.
مثال: در شکل زیر گراف formula_10 و یک تجزیهٔ درختی از آن را می‌بینید. عرض این تجزیهٔ درختی، ۲ می‌باشد. مثال: عرض درختی تمام درخت‌ها برابر با یک است.
تجزیهٔ درختی formula_17 با عرض k نرم می‌گوییم اگر: نکته: هر تجزیهٔ درختی را می‌توان به یک تجزیهٔ درختی نرم تبدیل کرد. فرض کنید formula_20 یک تجزیهٔ درختی برای گراف formula_21 باشد به طوری که عرض آن حداکثر formula_22 باشد. می‌خواهیم الگوریتمی از formula_23 ارائه دهیم تا بزرگ‌ترین مجموعهٔ مستقل این گراف را پیدا کنیم.
ابتدا درخت را از راس دلخواه r ریشه دار می‌کنیم. به ازای هر formula_24، formula_25 را برابر با بزرگ‌ترین مجموعهٔ مستقل که می‌توان در زیر درخت i پیدا کرد به شرط آن که اشتراک راس‌های مجموعهٔ مستقل و formula_26 دقیقا راس‌های U باشد تعریف می کنیم. حال الگوریتم جستجوی عمق اول را روی درخت اجرا می ‌کنیم. سپس به ازای هر راس i یکی از کارهای زیر را انجام می دهیم:
formula_34 جواب نیز برابر خواهد شد با: formula_35 تعداد حالاتی که مقادیر آن‌ها را پیدا می‌کنیم برابر با formula_36 است. هم‌چنین برای به دست آوردن مقدار یک خانه باید به ازای تمام زیرمجموعه از بسته‌های فرزندانش مقدار ماکسیمم حساب شود و همچنین باید بررسی شود که راس‌ها به هم یال نداشته باشند که مرتبهٔ این قسمت نیز از formula_37 است. در نتیجه زمان اجرای الگوریتم formula_38 خواهد شد.
به ازای k‌های کوچک اثبات شده‌است که گرافی که مجموعهٔ گراف‌های زیر را به عنوان ماینور شامل نمی شود ، عرض درختی کمتر مساوی k دارد.
در حالت کلی، پاسخ به این سؤال که آیا گراف formula_10 عرض درختی‌اش حداکثر formula_22 است یا نه یک مسئله formula_46 (ان‌پی کامل) است. اما برای formula_22های مشخص با اندازهٔ کوچک الگوریتمی با زمان اجرای خطی وجود دارد. زمان اجرای این الگوریتم بر اساس سایز ورودی خطی ولی بر اساس formula_22 نمایی‌ست و لذا فقط برای formula_22های ثابت و کوچک عملی‌ است. در این مثال در یک گراف تعدادی پلیس حضور دارند که در راس‌های مختلف گراف قرار دارند. یک دزد نیز در یکی از راس‌های گراف پنهان شده‌است. در هر مرحله اگر k پلیس داشته باشیم ، پلیس‌ها k راس را در نظر می‌گیرند و به آن می‌روند. سپس دزد یک راس را در نظر می‌گیرد که در آن پلیس نیست و از راسی که در آن حضور دارد به راس مقصد مسیری وجود داشته باشد که راس‌های این مسیر شامل راس‌های اشتراک مکان‌های قبلی پلیس‌ها و مکان‌های جدید پلیس‌ها نباشد. پلیس‌ها برنده می‌شوند اگر بعد از تعداد محدودی مرحله ، دزد راسی برای فرار کردن به آن نداشته باشد.
قضیه : اگر عرض درختی گراف G حداکثر k باشد ، آنگاه 1 + k پلیس می توانند دزد را دستگیر کنند.
اثبات: چون عرض درختی گراف حداکثر k است ، یک تجزیهٔ نرم برای آن وجود دارد. حال تجزیهٔ نرم آن را در نظر می گیریم. ابتدا آن را از راسی ریش‌دار می کنیم. پلیس‌ها در مرحله اول در 1 + k راس در بستهٔ ریشه قرار می‌گیرند. دزد نیز در این مرحله در راسی دیگر قرار گرفته‌است. حال راسی که دزد در آن قرار گرفته را در نظر می‌گیریم. مجموعهٔ بسته‌هایی که راس دزد در آن قرار دارد یک مجموعهٔ همبند در یکی از زیر درخت‌های فرزندان ریشه است. پلیس‌ها در این مرحله آن فرزند را انتخاب می‌کنند و به راس‌های آن منتقل می‌شوند و از آن جا که اشتراک بستهٔ جدید با بستهٔ قبل k است و یک برش در گراف را تشکیل می‌دهد ، دزد نمی‌تواند از آن خارج شود. اگر پلیس‌ها به همین روند ادامه دهند در آخر دزد را در یک بسته برگ گیر می‌اندازند.