پایان نامه آرايش شينه بندي مناسب شبكه ايران و رويكرد تئوري گراف به مديريت سيستم توزيع به روش بازآرايي فيدر
مقدمه:
فرض کنید Vیک مجموعه ناتهی و E زیرمجموعهای از V×Vباشد در این صورت زوج ( V, E ) G = را یک گراف می نامند. Vرا مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهتدار می گویند و یال از راسبه سمت راس را به صورتنشان میدهند. در غیر این صورت گراف را بدون جهت مینامند و یال بین راس های و با نماد نشان میدهند. تعداد راس های یک گراف را مرتبه و تعداد یال های آن را اندازه گراف می نامیم. بطور مثال در شکل زیرگرافی را با شش راس و هفت یال مشاهده می کنیم.
شکل 1-1 : گرافی با شش راس و هفت یال
1-2: گرافها
گرافها دارای انواع متعددی هستند که به برخی از آنها اشاره میکنیم:
1- گراف همبند.
2- گراف ناهمبند.
3- گراف کامل.
4- گراف اویلری.
5- گراف همیلتونی.
6- گراف درختی.
7- گراف مسطح.
8- گراف دو بخشی.
9- گراف چندبخشی.
10- گراف k–مکعب.
11-گراف چرخ.
12- گراف ستارهای.
13- گراف بازهای.
14- گراف اشتراکی.
15- گراف منظم.
16- گراف جهتدار.
نکته 1 : در نظریه گراف ، یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد.
نکته 2 : یک گراف کامل از مرتبه n، دارای n راس و یال است و آن را با نشان میدهند.
نکته 3 : یک گراف کامل یک گراف منتظم از درجه n-1 است.
1-3 : مثالهایی از گراف کامل
در شکل زیر گرافهای کامل از مرتبه یک تا مرتبه هشت نمایش داده شده است. از تعریف این نوع گراف معلوم است که گراف کامل از مرتبه اول ، هیچ یالی ندارد.
شکل1-2 : گرافهای کامل از مرتبه یک تا مرتبه هشت
1-4 : گراف دو بخشی
1-4-1 : مفهوم شهودی
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی می باشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نموده اند. حال این سوال مطرح می شود که آیا می توان به هر متقاضی شغلی متناسب او اختصاص داد؟ .
برای حل چنین مسئله ای که به مسئله ی تخصیص موسوم است، با استفاده از گراف می توان وضعیت های خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعه ای به نام X و مجموعه مشاغل بدون متصدی را در مجموعه ای به نام Y قرار می دهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یال ها وصل می نماید. به عبارت دیگر گراف بوجود آمده دارای یال های xy است که هر متقاضی x را از مجموعه X به شغل های مناسب y از مجموعه Y متصل می نماید. به عبارت دقیق تر هیچ دو راس متعلق به مجموعه X متفاضیان یا هیچ دو راس متعلق به مجموعه Yمشاغل توسط هیچ یالی به هم متصل نمی باشند. چنین گرافی را گراف دوبخشی یا دوپارچه می گویند.
1-4-2 : تعریف گراف دوبخشی
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.
یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y(ناتهی) به این صورت است که :
(1-1)
به عنوان مثال گراف زیر یک گراف دو بخشی است:
شکل1-3 : گراف دو بخشی
چرا که در این گراف مجموعه رئوس را می توان به دو مجموعه و
چنان افراز نمود که هیچ دو راسی در این دو مجموعه با هم مجاور نباشند و هر یال تنها یک انتها در مجموعه اول و یک انتها در مجموعه دوم داشته باشد.
قضیه:
اگر گراف k–منتظم، دارای دوبخش X و Y باشد، آنگاه تعداد عناصر X و Y باهم برابر است.
برهان:
فرض می کنیم X دارای m راس و Y دارای n راس از راس های گراف دو بخشی k–منتظم می باشد. نشان می دهیم که. m = n از هر راس در مجموعه X به تعداد k، یال خارج می شود(چرا؟) پس تعداد کل یال ها(q) برابر است با q = km . چون جمعا m + n راس داریم، لذا مطابق قضیه مجموع درجه های راس ها و تعریف گراف k–منتظم داریم :
(1-2)
پس:
(1-3)
و لذا حکم برقرار است.
1-4-3 : گراف دو بخشی کامل
گراف دو بخشی کامل یک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس در ان به هر راس وصل شده است. گراف دو بخشی کامل را با نماد نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.به عنوان مثال گراف زیر یک گراف دو بخشی کامل است.
شکل1-4 : گراف دو بخشی کامل
قضیه :
در گراف دو بخشی کامل همواره داریم: که در آن q اندازه گراف مذکور است.
برهان:
می دانیم گراف دارای m راس در یک مجموعه و nراس در مجموعه ای دیگر است.
تعداد کل راس ها P = m + n می باشد(مرتبه گراف). اما برای یافتن تعداد یال های گراف دو بخشی کامل ابتدا تعداد کل یال های یک گراف کامل از مرتبه P = m + n را محاسبه کرده سپس تعداد کل یال هایی که راس های دو مجموعه را در خود دو مجموعه به هم وصل می کند از آن کم می کنیم. داریم:
(1-4) قضیه:
اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه: .
برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با
که m تعداد یال بخش X و n تعداد یال بخش Y است . (بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد) . از طرفی می دانیم که: پس, داریم:
(1-5)
چون u آهنگ تغییرات تعداد یال را نشان می دهد و پس از نتیجه می شود که:
(1-6)
ضمنا می دانیم که:
(1-7)
پس بیشترین مقدار u در نقطه اتفاق می افتد، یعنی:
(1-8)
بنابراین تعداد کل یال ها نمی تواند از بیشتر باشد و لذا .
1-5 : گراف چرخ
هر گراف که دارای راس باشد که و یکی از رئوس از درجه ی و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامی
نقد و بررسیها
هنوز بررسیای ثبت نشده است.