عنوان پایان‌نامه
پارامترهای آسیب پذیریدر گرافها تعمیم و کاربردهای آن
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 60..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 63295
- تاریخ دفاع
- ۲۷ اسفند ۱۳۹۰
- دانشجو
- بیژن جمالی
- استاد راهنما
- دارا معظمی
- چکیده
- امروزه بسیاری از سیستمهای پیشرفته به‌صورت مجموعه‌ای از شبکه‌ها طراحی می‌شوند و در طراحی، مدلسازی و ارزیابی سیستمهای اطلاعاتی اعم از مخابرات و کامپیوتر از مفهوم شبکه و خواص شبکه‌ها استفاده می شود. یکی از مهمترین موضوعاتی که در رابطه با یک شبکه به ذهن می‌رسد مؤثر بودن شبکه و میزان مقاومت آن و توانایی تحمل شبکه در برابر حوادث ناخواسته می باشد. بنابراین قابل اطمینان بودن و آسیب پذیری شبکه‌ها معیاری برای خوبی و کارایی شبکه‌ها می توانند محسوب شوند. وقتی شبکه ای شروع به از دست دادن پیوند‌‌ها یا گره‌‌‌ها می‌کند مؤثر بودن خود را به مرور از دست می دهد، به عنوان یک واکنش طبیعی گره‌‌های جدیدی یا پیوندهایی اضافه می‌شوند تا شبکه تعمیر شود. این کوششی است برای اینکه شبکه مؤثر بودن خود را به دست آورد. لذا شبکه‌‌های ارتباطی باید نه تنها نسبت به از هم پاشیدگی اولیه بلکه نسبت به احتمال تعمیر مجدد شبکه تا حد امکان به صورت پایدار ساخته شوند. برخی از پارمترهای نظریه گراف در دهه‌‌های گذشته جهت تبیین و ارزشیابی پایداری و آسیب‌پذیری شبکه‌ها مورد استفاده قرارگرفته‌اند. اولین دسته از این پارامترها همبندی رأسی وهمبندی یالی گراف بودند ولی مساله‌ای که بعدها مورد توجه قرار گرفت این بود که ممکن است با حذف یک رأس یا یال، گراف همبندی خود را از دست بدهد، لیکن گراف باقیمانده پایداری خوبی داشته باشد و در نتیجه برخی پارامترهای دیگر جهت سنجش آسیب پذیری شبکه‌ها معرفی شدند از جمله عدد بستگی، محکمی ، بی‌نقصی و در نهایت همبستگی. در این پارامترها میزان خرابی وارد شده به شبکه-تعداد م‍ؤلفه‌‌ها یا اندازه بزرگترین م‍ؤلفه- به صورت نسبی در مقابل بزرگی ضربه وارد شده به شبکه-تعداد گره‌‌‌ها یا یالهای ارتباطی حذف شده-مورد سنجش قرار می‌گیرد. در این رساله ابتدا یک دیدگاه شهودی به مفهوم آسیب پذیری شبکه‌ها ارائه شده و پس از بررسی خواص این پارامترها و مقایسه تطبیقی آنها با هم، مقدار این پارامترها برای حاصلضرب دکارتی برخی گرافها محاسبه شده است . همچنین پیشنهادهایی برای معرفی پارامترهای جدید آسیب پذیری انجام گرفته که همگی در پرتو نگاه شهودی جدید شکل گرفته اند.
- Abstract
- Networks portray a wide range of real-world systems. In a communication network, the vulnerability measures the resistance of the network to disruption of operation after the failure of certain stations or communication links. If we think of a graph as a modeling a network, the stations of network correspond to vertices of the graph and the communication links of network correspond to edges of the graph. The analysis of vulnerability in networks generally involves some questions about how the underlying graph is connected. When some vertices of a graph (the stations of network) are deleted, one wants to know whether the remaining graph is still connected. More-over if the graph is disconnected, the determination of the number of its components or their orders (the number of vertices of components) is useful. A variety of parameters, which are evolved, has been appeared and the most important of them including: Binding number, Toughness, Integrity and Tenacity are reviewed in this dissertation in a comparative manner. And finally I have computed the exact value of these parameters for the Cartesian product of a path and cycle. In this survey I have had an intuitionistic view to all graph and network related concepts and in the light of that I have tried to introduce new vulnerability parameters and their applications.
