موضوع مقاله: عرض درخت | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # عرض درخت | مقدمه: این عدد می‌تواند به طرق مختلفی تعریف شود: اندازهٔ بزرگ‌ترین راس در تجریهٔ درختی آن گراف، اندازهٔ بزرگ‌ترین خوشه در تکمیل وتری و ... | ## بخش 1: عرض درخت | تجزیه‌ی درختی تجزیهٔ درختی گراف ، درختی‌ است مانند با رئوس (به این رئوس کیف یا bag می‌گویند) که در آن هر یک زیرمجموعه‌ای از است که شرایط زیر را ارضا کند: اجتماع تمامی ها، مجموعهٔ باشد. برای هر یال مانند در گراف ، حداقل یک راس (کیف) مانند در درخت باشد که شامل هر دو راس و است. بدیهی‌ترین تجزیهٔ درختی، قراردادن تمامی رئوس گراف در یک کیف است که در این صورت هر گراف یک تجزیه با عرض دارد؛ بنابراین برای هر گراف تجزیه‌های درختی متعددی وجود دارد. عرض درختی یک گراف نیز که با نمایش داده می‌شود، برابرست با کم‌ترین عرض درختی میان تمامی تجریه‌های درختی آن گراف. هر یال (متشکل از دو راس) از گراف اصلی حداقل در یکی از سبدهای تجزیه‌ی درختی دیده می‌شود (به طور مثال دو راس a و b در گراف اصلی به هم وصل‌اند و بنابراین در تجزیه درختی در حداقل یکی از سبدها (سبد بالا چپ) دیده می‌شوند).از طرفی دیگر تمامی رئوس گراف (۸ راس) در حداقل یکی از سبدهای تجزیه درختی آمده‌اند. بدین معنی که سبدهای حاویِ یک راس، تشکیل یک زیردرخت در تجزیه درختی می‌دهند (به طور مثال به راس G که با رنگ بنفش مشخص شده‌است، دقت کنید که در سه سبد موجود است و این سه سبد تشکیل یک مولفه هم‌بندی می‌دهند). برقراری این سه شرط نشان می‌دهد که تجزیه درختی ارائه‌شده، یک تجزیه درختی معتبر است. تجزیه‌ی درختی نرم تجزیهٔ درختی با عرض k نرم می‌گوییم اگر: نکته: هر تجزیهٔ درختی را می‌توان به یک تجزیهٔ درختی نرم تبدیل کرد. | ## بخش 2: عرض درخت | مجموعه‌ی مستقل بر روی تجزیه‌ی درختی فرض کنید یک تجزیهٔ درختی برای گراف باشد به طوری که عرض آن حداکثر باشد. می‌خواهیم الگوریتمی از ارائه دهیم تا بزرگ‌ترین مجموعهٔ مستقل این گراف را پیدا کنیم. به ازای هر ، را برابر با بزرگ‌ترین مجموعهٔ مستقل که می‌توان در زیر درخت i پیدا کرد به شرط آن که اشتراک راس‌های مجموعهٔ مستقل و دقیقا راس‌های U باشد تعریف می کنیم. سپس به ازای هر راس i یکی از کارهای زیر را انجام می دهیم: اگر راس یک برگ بود، به ازای هر اگر U یک مجموعهٔ مستقل در گراف بود در نظر می گیریم در غیر این صورت اگر راس برگ نبود و فرزندان راس باشند آنگاه: جواب نیز برابر خواهد شد با: تعداد حالاتی که مقادیر آن‌ها را پیدا می‌کنیم برابر با است. هم‌چنین برای به دست آوردن مقدار یک خانه باید به ازای تمام زیرمجموعه از بسته‌های فرزندانش مقدار ماکسیمم حساب شود و همچنین باید بررسی شود که راس‌ها به هم یال نداشته باشند که مرتبهٔ این قسمت نیز از است. به ازای k‌های کوچک اثبات شده‌است که گرافی که مجموعهٔ گراف‌های زیر را به عنوان ماینور شامل نمی شود ، عرض درختی کمتر مساوی k دارد. بیش از ۷۵ نوع گراف الگوریتم‌های محاسبهٔ عرض درختی یک گراف در حالت کلی، پاسخ به این سؤال که آیا گراف عرض درختی‌اش حداکثر است یا نه یک مسئله (ان‌پی کامل) است. به مساله‌ای FPT گفته می‌شود که زمان اجرای آن به صورت باشد که در آن سایز وروردی (در این مساله ː اندازه گراف)، یک پارامتر (در این‌ مساله ː عرض درختی) و یک تابع محاسبه‌پذیر است (هر تابعی که حداقل یک ماشین تورینگ در زمان متناهی بتواند آن را محاسبه کند). | ## بخش 3: عرض درخت | به جز موارد ردیف اول و ردیف نهم، باقی الگورتیم‌ها همگی FPT می‌باشند که در آن‌ها ضریب تخمین، وابستگی به در پیچیدگی زمانی یا همان و وابستگی به در پیچیدگی زمانی در ستون‌های متفاوت ذکر شده‌اند. +ضریب تخمینوابستگی زمان اجرا به kوابستگی زمان اجرا به nمرجعدقیق (۱)آرنبرگ و سایرین (۱۹۸۷)۴رابرتسون و سیمور (۱۹۹۵)۸رید (۱۹۹۲)۵لاگرگرن (۱۹۹۶)دقیق (۱)بُدلَندِر (۱۹۹۶)فیگه و سایرین (۲۰۰۸)۴.۵امیر (۲۰۱۰)۴.۶۶امیر (۲۰۱۰)دقیق (۱)فومین و سایرین (۲۰۱۵)۳بُدلَندِر (۲۰۱۶)۵بُدلَندِر (۲۰۱۶)فومین و سایرین (۲۰۱۸)۵بلباسی و فورِر (۲۰۲۱-آ)۲کُرهُنِن (۲۰۲۱)۵بلباسی و فورِر (۲۰۲۱-ب) مسئله‌ی دزد و پلیس‌ها در این مثال در یک گراف تعدادی پلیس حضور دارند که در راس‌های مختلف گراف قرار دارند. در هر مرحله اگر k پلیس داشته باشیم ، پلیس‌ها k راس را در نظر می‌گیرند و به آن می‌روند. سپس دزد یک راس را در نظر می‌گیرد که در آن پلیس نیست و از راسی که در آن حضور دارد به راس مقصد مسیری وجود داشته باشد که راس‌های این مسیر شامل راس‌های اشتراک مکان‌های قبلی پلیس‌ها و مکان‌های جدید پلیس‌ها نباشد. پلیس‌ها برنده می‌شوند اگر بعد از تعداد محدودی مرحله ، دزد راسی برای فرار کردن به آن نداشته باشد. قضیه : اگر عرض درختی گراف G حداکثر k باشد ، آنگاه 1 + k پلیس می توانند دزد را دستگیر کنند. مجموعهٔ بسته‌هایی که راس دزد در آن قرار دارد یک مجموعهٔ همبند در یکی از زیر درخت‌های فرزندان ریشه است. پلیس‌ها در این مرحله آن فرزند را انتخاب می‌کنند و به راس‌های آن منتقل می‌شوند و از آن جا که اشتراک بستهٔ جدید با بستهٔ قبل k است و یک برش در گراف را تشکیل می‌دهد ، دزد نمی‌تواند از آن خارج شود. | ## جمع‌بندی | اگر پلیس‌ها به همین روند ادامه دهند در آخر دزد را در یک بسته برگ گیر می‌اندازند.