عنوان پایان‌نامه
پایه ی مینیمم دورها در گراف
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 5102;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 59514
- تاریخ دفاع
- ۳۰ بهمن ۱۳۹۱
- دانشجو
- سیدسعید محمودی هاشمی
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- یکی از ساختارهای مهم در گراف، دورها می‌باشند. به بیان ساده، می‌توان دور را مسیری در نظر گرفت که ابتدا و انتهای آن یکسان باشد. در گراف بدون جهت (و یا جهت‌دار) G با n رأس و m یال، بردار وقوع هر دور یک بردار از ?, 0, 1 }m-} (و یا 0, 10 } m} ) این بردارها در (GF (2 (و یا Q) تشکیل یک فضای برداری می‌دهند که به آن فضای دورهای گراف G می‌گویند. پایه‌ی دورهای گراف G، مجموعه‌ای از دورها است که بردار وقوع آن‌ها، تشکیل یک پایه برای فضای دورهای گراف بدهند. به عبارت دیگر، پایه‌ی دورهای گراف، مجموعه‌ای از دورها است که همه‌ی دورهای گراف را تولید می‌کنند. مجموع وزن دورهای یک پایه‌ی را وزن پایه‌ی دورها می‌گویند. پایه‌های دورهای یک گراف، بر اساس ساختار دورهای تشکیل دهنده‌ی آن به چند نوع مختلف دسته‌بندی می‌شوند که یافتن پایه‌ی مینیمم در هر کدام از این دسته‌ها پیچیدگی متفاوتی دارد. در کاربرد، بسیاری از الگوریتم‌ها، از پایه‌ی دورهای گراف به عنوان ورودی الگوریتم استفاده می‌کنند. در این موارد، یافتن پایه‌ی دورهای با کمترین وزن، می‌تواند به افزایش سرعت الگوریتم کمک کند. اما گراف‌هایی که در عمل مورد بررسی قرار می‌گیرند، در بسیاری از موارد ممکن است دارای تعداد بسیار زیادی رأس و یال باشند. از این رو حتی الگوریتم‌های چندجمله‌ای هم ممکن است کارایی خوبی برای این نمونه‌ها نداشته باشند. به همین دلیل، با وجود الگوریتم‌های چندجمله‌ای که در سه دهه‌ی اخیر ارائه شده است، همچنان تلاش برای یافتن الگوریتم‌های کاراتر ادامه دارد. در برخی از موارد، حتی داشتن تقریبی از پایه‌ی کمینه می‌تواند کارامد باشد. بدین منظور، علاوه بر الگوریتم‌های چندجمله‌ای قطعی، چند الگوریتم تقریبی و احتمالی نیز برای این کار ارائه شده است. در این پایان نامه، ابتدا پایه‌ی دورهای گراف و انواع آن را معرفی می‌کنیم. سپس به بررسی الگوریتم‌هایی که تا کنون برای این مسأله ارائه شده است می‌پردازیم. واژه‌های کلیدی: فضای دورهای گراف، پایه‌ی دورهای مینیمم، گراف، الگوریت
- Abstract
- Cycles are important structures in graphs. In an undirected (directed) graph G with n vertices and m edges, the incidence vector of each cycle is a vector in {0,1}^m ({-1,0,1}^m). These vectors form a vector space over GF (2) (Q) which is referred to as the cycle space of G. A cycle basis of G is the set of cycles whose incidence vectors form a basis for the cycle space of G. In other words, a cycle basis of a graph is a set of cycles that generates all cycles of the graph. The weight of the cycle basis is the sum of the weights of its cycles. The cycle bases are categorized into several classes, based on the structure of the cycles that form them. Finding the minimum cycle basis for each of these classes has a different computational complexity. In application, several algorithms use cycle bases as input. In these cases, finding the minimum cycle base can decrease the computation time of the algorithm. However, most graphs that are used in practice have a very large number of vertices and edges. Thus, even the existing polynomial-time solutions for this problem might not work efficiently for these graphs. Therefore, even though several polynomial algorithms have been presented in last three decades, efforts to find more efficient algorithms have continued. Sometimes, an approximation of the minimum cycle basis can be useful. Therefore, in addition to deterministic polynomial algorithms, some approximation and randomized algorithms have also been presented. In this thesis, we introduce the cycle bases and their classes and review the algorithms that have been presented for solving this problem. Keywords: Cycle Space, Minimum Cycle Bases, Graph, Algorit
