عنوان پایان‌نامه
بررسی درخت نازک در گرافها ی عرض درخت محدود وسری موازی
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 26..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 51154
- تاریخ دفاع
- ۱۳ دی ۱۳۹۰
- دانشجو
- سعید آخوندیان امیری
- استاد راهنما
- دارا معظمی
- چکیده
- در این پایان نامه، درخت نازک در بعضی گرافها بررسی شد، که در تقریب مساله فروشنده دوره¬گرد مناسب است، در ابتدا این ذهنیت وجود داشت که درخت نازک در گرافهای عرض درخت محدود با ارایه یک الگوریتم پویای مناسب در زمان چندجمله¬ای قابل یافتن است اما با مطالعات بیشتر و مشاهده مسایل مشابه مانند دور همیلتونی به این نتیجه رسیدیم که یافتن نازکترین درخت پوشا در این گرافها کار ساده¬ای نیست. اما سخت بودن مساله نیز اثبات نشده است. قابل ذکر است که سخت بودن مساله مذکور در حالت کلی اثبات نشده، اما ما سخت بودن بدست آوردن نازکی یک درخت پوشا را در حالت کلی اثبات کردیم ، و سعی کردیم با استفاده از قضایایی که در گرافهای هامنی (مسطح) بوده، درختی با نازکی مناسب را بدست آوریم. همچنین الگوریتم دیگری برای بدست آوردن درختی با نازکی مناسب در گرافهای سری-موازی که ماکسیمم درجه پایین دارند ارایه دادیم.
- Abstract
- In this thesis we introduce thin tree, which is useful for approximating travelling salesman problem. At first glance seems thin tree in bounded tree-width graph is solvable in linear time, But by searching on similar problems, we can see it’s not as easy as other problems. Currently NP-Hardness of finding thin tree is not clear, but we showed that finding thinness of special spanning tree is NP-Hard; also we found some good thin tree in bounded genus graphs. Also we apply another algorithm to find thin tree in Series-Parallel graphs with bounded degree.
