عرض درخت
در نظریه گراف، عرض درختی یک گراف بدون جهت، عددی است که مربوط به آن گراف است. این عدد میتواند به طرق مختلفی تعریف شود: اندازهٔ بزرگترین راس در تجریهٔ درختی آن گراف، اندازهٔ بزرگترین خوشه در تکمیل وتری و ... .مفهوم عرض درختی یک گراف، در ابتدا توسط Umberto Bertelé و Francesco Brioschi در سال ۱۹۷۲ معرفی شد. بعدها بهصورت جدی توسط Neil Robertson و Paul Seymour در سال ۱۹۸۴ مجدداً معرفی گردید. برای تعریف عرض درختی یک گراف، ابتدا باید تجریهٔ درختی گراف را تعریف کنیم.
تجزیهی درختی
تجزیهٔ درختی گراف
- اجتماع تمامی ها، مجموعهٔباشد.
- تمامی رئوس (کیفهای) درخت که شامل راس هستند، تشکیل یک زیردرخت همبند بدهند.
- برای هر یال مانند در گراف، حداقل یک راس (کیف) ماننددر درخت باشد که شامل هر دو راسواست.
تجزیهٔ درختی یک گراف، یکتا نیست. بدیهیترین تجزیهٔ درختی، قراردادن تمامی رئوس گراف در یک کیف است که در این صورت هر گراف یک تجزیه با عرض
مثال:
در شکل زیر گراف
مثال: عرض درختی تمام درختها برابر با یک است.
تجزیهی درختی نرم
تجزیهٔ درختی
نکته: هر تجزیهٔ درختی را میتوان به یک تجزیهٔ درختی نرم تبدیل کرد.
مجموعهی مستقل بر روی تجزیهی درختی
فرض کنید
ابتدا درخت را از راس دلخواه r ریشه دار میکنیم. به ازای هر
- اگر راس یک برگ بود، به ازای هراگر U یک مجموعهٔ مستقل در گراف بوددر نظر می گیریم در غیر این صورت
- اگر راس برگ نبود وفرزندان راسباشند آنگاه:
جواب نیز برابر خواهد شد با:
به ازای kهای کوچک اثبات شدهاست که گرافی که مجموعهٔ گرافهای زیر را به عنوان ماینور شامل نمی شود ، عرض درختی کمتر مساوی k دارد.
- بیش از ۷۵ نوع گراف
الگوریتمهای محاسبهٔ عرض درختی یک گراف
در حالت کلی، پاسخ به این سؤال که آیا گراف
به بیان دقیقتر محسابهی عرض درختی یک مساله FPT است که مخفف Fixed-Parameter Tractable میباشد. به مسالهای FPT گفته میشود که زمان اجرای آن به صورت
ضریب تخمین | وابستگی زمان اجرا به k | وابستگی زمان اجرا به n | مرجع |
---|---|---|---|
دقیق (۱) | آرنبرگ و سایرین (۱۹۸۷) | ||
۴ | رابرتسون و سیمور (۱۹۹۵) | ||
۸ | رید (۱۹۹۲) | ||
۵ | لاگرگرن (۱۹۹۶) | ||
دقیق (۱) | بُدلَندِر (۱۹۹۶) | ||
فیگه و سایرین (۲۰۰۸) | |||
۴.۵ | امیر (۲۰۱۰) | ||
۴.۶۶ | امیر (۲۰۱۰) | ||
دقیق (۱) | فومین و سایرین (۲۰۱۵) | ||
۳ | بُدلَندِر (۲۰۱۶) | ||
۵ | بُدلَندِر (۲۰۱۶) | ||
فومین و سایرین (۲۰۱۸) | |||
۵ | بلباسی و فورِر (۲۰۲۱-آ) | ||
۲ | کُرهُنِن (۲۰۲۱) | ||
۵ | بلباسی و فورِر (۲۰۲۱-ب) |
مسئلهی دزد و پلیسها
در این مثال در یک گراف تعدادی پلیس حضور دارند که در راسهای مختلف گراف قرار دارند. یک دزد نیز در یکی از راسهای گراف پنهان شدهاست. در هر مرحله اگر k پلیس داشته باشیم ، پلیسها k راس را در نظر میگیرند و به آن میروند. سپس دزد یک راس را در نظر میگیرد که در آن پلیس نیست و از راسی که در آن حضور دارد به راس مقصد مسیری وجود داشته باشد که راسهای این مسیر شامل راسهای اشتراک مکانهای قبلی پلیسها و مکانهای جدید پلیسها نباشد. پلیسها برنده میشوند اگر بعد از تعداد محدودی مرحله ، دزد راسی برای فرار کردن به آن نداشته باشد.
قضیه : اگر عرض درختی گراف G حداکثر k باشد ، آنگاه 1 + k پلیس می توانند دزد را دستگیر کنند.
اثبات: چون عرض درختی گراف حداکثر k است ، یک تجزیهٔ نرم برای آن وجود دارد. حال تجزیهٔ نرم آن را در نظر می گیریم. ابتدا آن را از راسی ریشدار می کنیم. پلیسها در مرحله اول در 1 + k راس در بستهٔ ریشه قرار میگیرند. دزد نیز در این مرحله در راسی دیگر قرار گرفتهاست. حال راسی که دزد در آن قرار گرفته را در نظر میگیریم. مجموعهٔ بستههایی که راس دزد در آن قرار دارد یک مجموعهٔ همبند در یکی از زیر درختهای فرزندان ریشه است. پلیسها در این مرحله آن فرزند را انتخاب میکنند و به راسهای آن منتقل میشوند و از آن جا که اشتراک بستهٔ جدید با بستهٔ قبل k است و یک برش در گراف را تشکیل میدهد ، دزد نمیتواند از آن خارج شود. اگر پلیسها به همین روند ادامه دهند در آخر دزد را در یک بسته برگ گیر میاندازند.
منابع
- ↑ https://www.ti.inf.ethz.ch/ew/lehre/GA07/lec-treewidth.pdf
- ↑ Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317
- ↑ A $c^k n$ 5-Approximation Algorithm for Treewidth Read More: https://epubs.siam.org/doi/abs/10.1137/130947374
- ↑ https://arxiv.org/abs/2104.07463
- ↑ «نسخه آرشیو شده» (PDF). بایگانیشده از اصلی (PDF) در ۲۷ سپتامبر ۲۰۱۶. دریافتشده در ۲۰ مه ۲۰۱۷.
- ↑ https://epubs.siam.org/doi/abs/10.1137/130947374