تحقیق مقاله نظریه گراف و کاربردهای آن

نظریه های گراف و کاربرد آنها

فصل اول

مقدمه:

در دنیای اطراف ما، وضعیف های فراوانی وجود دارند که می توان توسط نموداری متشکل از یک مجموعه نقاط ، به علاوه خطوطی که برخی از این نقاط را به یکدیگر متصل می کنند، به توصیف آنها پرداخت، به عنوان مثال ، برای نشان دادن رابطه دوستی بین یک دسته از انسان ها می نوانیم هر شخص را با یک نقطه مشخص کنیم . نقاط متناظر با هر دو دوست را با یک خط به یکدیگر وصل نماییم، یا در جای دیگر ممکن است برای نشان دادن یک شبکه ارتباطی، از نموداری استفاده کنیم که در آن ، نقاط نمایانگر مراکز ارتباطی و خطوط، نشان دهنده پیوندهای ارتباطی بین مراکز باشند. توجه داشته باشید که در این گونه نمودارها، آن چه بیشتر مورد توجه است این است که آیا دو نقطه داده شده ، به وسیله یک خط به یکدیگر متصل هستند یا نه و طریقه اتصال آنها اهمیتی ندارد. تجربه ریاضی این وضعیت ها به مفهوم گراف منتهی می شود.

گراف G یک سه تایی مرتب (فرمول در فایل اصلی قرار دارد.) است که تشکیل شده از یک مجموعه ناتهیV(G) از راس ها، یک مجموعه E(G) – مجزای از V(G) – از یال ها و یک تابع وقوع (فرمول در فایل اصلی قرار دارد.) که به هر یال G ، یک زوج نا مرتب از راس های G را – که الزاماً متمایز نیستند – نسبت می دهد. اگر e یک یال وu و دو راس باشند به طوری که (فرمول در فایل اصلی قرار دارد.)، در این صورت گفته می شود که e، راس هایu و را به یکدیگر وصل کرده است و راس های u و  ، دو سر یال e نامیده می شوند.

دلیل نامگذاری گراف ها بدین نام، این است که می توان آنها را به صورت گرافیکی نمایش داد و همین نمایش گرافیکی است که ما را در درک بسیاری از خواص گراف ها یاری می کند. در این گونه نمایش داده می شود.

آشنایی با گراف

نمودار یک گراف ، فقط رابطه وقوعی را که بین راس ها و یال ها برقرار است، نشان می دهد، با این حال در غالب اوقات ، نموداری از یک گراف را رسم کرده ، به جای خود گراف ، به نمودار آن اشاره می کنیم. به همین منوال نقطه های آن را «راس» و خطوط آن را «یال» می نامیم.

اگر یک گراف ، نموداری داشته باشد که در آن یال ها تنها در راس های دو سر خود متقاطع باشند، مسطح نامیده می شود، چون می توان به سادگی این گونه گراف ها را روی یک صفحه مسطح رسم کرد. دو راس که برروی یال مشترکی واقعند ، مجاور نامیده می شوند. به همین ترتیب دو یال واقع بر روی یک راس مشترک نیز مجاورند. یک یال با دو سر یکسان ، طوقه و یک یال با دو سر متمایز ، یال پیوندی نامیده‌می‌شود.

اگر مجموعه راس ها و مجموعه یال های یک گراف، متناهی باشند، گراف مزبور را متناهی می نامند. گرافی را که یک راس داشته باشد بدیهی  و سایر گراف ها را غیر بدیهی می نامیم.

یک گراف ساده است، اگر هیچ طوقه ای نداشته باشد و بین هر دو راس آن ، بیش از یک یال نباشد . نمادهای (فرمول در فایل اصلی قرار دارد.) را به ترتیب برای نشان دادن تعداد راس ها و تعداد یال های گراف G به کار می بریم.

یکریختی گراف ها:

دو گراف Gو H همسان اند(و نوشته می شود G=H) ، اگر(فرمول در فایل اصلی قرار دارد.) . مسلماً اگر همسان باشند، می‌توان آنها را با نمودارهای یکسانی نمایش داد. به هر حال این امکان نیز وجود دارد که دو گراف نا همسان ، نمودارهای یکسانی داشته باشند. در حالت کلی ذو گراف GوH ، یکرخت نامیده می شوند (ونوشته می شود (فرمول در فایل اصلی قرار دارد.) اگر نگارشت های دو سویی (فرمول در فایل اصلی قرار دارد.) وجود داشته باشند، به طوری که داشته باشیم: (فرمول در فایل اصلی قرار دارد.) اگر تنها اگر (فرمول در فایل اصلی قرار دارد.) . این زوج  از نگارشت ها، یک یکریختی بین GوH نامیده می شود.

از طرف دیگر گراف تهی، گرافی است که هیچ یالی نداشته باشد. گراف دو بخشی ، گرافی است که می توان مجموعه راس های آن را به دو زیرمجموعه XوY چنان افراز کرد که یک سر تمام یال های آن در X و سر دیگرآنها در Y باشد. گراف دوبخشی کامل، یک گراف دوبخشی با بخش های X وY است که در آن هر راس X ،به هر راس Y وصل شده باشد. اگر (فرمول در فایل اصلی قرار دارد.) گراف دو بخشی کامل را با  نمایش می دهیم.

ماتریس وقوع و ماتریس مجاورت:

متناظر با هر گراف G ، یک ماتریس وجود دارد که ماتریس وقوع G نامیده می‌شود. اگر راس های G را با  و یال های آن را با  نمایش دهیم، آنگاه ماتریس وقوع G ، ماتریسی مانند (فرمول در فایل اصلی قرار دارد.)  است که در آن (فرمول در فایل اصلی قرار دارد.) برابر با تعداد دفعاتی است (0،1 یا2) که (فرمول در فایل اصلی قرار دارد.) بر (فرمول در فایل اصلی قرار دارد.) واقع شده است. در حقیقت ماتریس وقوع یک گراف ، طریقه دیگری یرای معین نمودن آن گراف است.

راه دیگر معین نمودن یک گراف ، استفاده از مارتیس مجاورت آن است که مارتیسی است (فرمول در فایل اصلی قرار دارد.) مانند (فرمول در فایل اصلی قرار دارد.) و در آن (فرمول در فایل اصلی قرار دارد.) برابر تعداد یال هایی است که رابه  وصل می کند.

زیر گراف :

می گوئیم گراف H، زیر گراف G است (نوشته می شود (فرمول در فایل اصلی قرار دارد.)) ، اگر (فرمول در فایل اصلی قرار دارد.) از محدود کردن (فرمول در فایل اصلی قرار دارد.) به E(H) حاصل شده باشد. اگر (فرمول در فایل اصلی قرار دارد.) ولی داشته باشیم (فرمول در فایل اصلی قرار دارد.) می نویسم (فرمول در فایل اصلی قرار دارد.) و می گوئیم H یک زیر گراف سره از G است. اگر H یک زیر گراف G باشد، درآن صورت G را یک زبرگراف H می نامیم. در صورتی که زیر گراف (یا زبرگراف) H از G در شرط V(H)=V(G) صدق کند، آن را یک زیرگراف فراگیر(یا زبرگراف فراگیر) از G خواهیم نامید.

اگر در یک گراف تمام طوقه ها را حذف کنیم و همچنین از بین هر دو راس مجاور، تمام یال های پیوندی به جز یکی را حذف نماییم ، به زیر گراف فراگیر ساده‌ای از G می رسیم که گراف ساده زمینهG نامیده می شود.

فرض کنید (فرمول در فایل اصلی قرار دارد.) ، یک زیر مجموعه ناتهی از V باشد. زیر گرافی از G که مجموعه راس های آن (فرمول در فایل اصلی قرار دارد.) و مجموعه یال هایش برابر مجموعه یال هایی از Gباشد که هر دو سر آنها در (فرمول در فایل اصلی قرار دارد.) واقع است، زیر گراف القاء شده توسط  نامیده شده، با نمایش داده می‌شود. همچنین می گوئیم  یک زیر گراف القاییG می باشد. زیر گراف القایی که با  نمایش داده می شود، زیر گرافی است که با حذف راس های و یال های واقع بر آنها، از G به دست می آید. اگر  به جای  می نویسیم .

فرض کنید کهیک مجموعه ناتهی از E باشد. زیر گرافی از G که مجموعه راس های آن ، برابر مجموعه راس های دو سریال هایباشد، زیر گراف القاء شده توسط  نامیده شده ، با  نمایش داده می شود. همچنین می گوئیم  یک زیرگراف القایی یالی G می باشد. زیر گراف فراگیری از G که مجموعه یال های آن باشد ، به طور ساده به صورت  نوشته می شود و می توان آن را با حذف یال های از   به دست آورد. به طور مشابه گرافی که با افزودن مجموعه یال های به  به دست می آید، با  نمایش داده می شود. اگر  به جای  و  می نویسیم  و.

درجه راس ها:

درجه راس در گراف ، برابر تعداد یال های واقع بر می باشد. در این تعریف ،هر طوقه به عنوان دو یال شمرده می شود.

کمترین و بیشترین درجه راس های G را به ترتیب با  نمایش می دهیم.

اثبات:

ماتریس وقوع M را در نظر بگیرند. مجموع داریه های سطر متناظر با راس دقیقاً برابر  است و بنابراین  برابر مجموع تمام داریه های M می باشد که این جمع برابر است.

مسیرها :

یک گشت از G دنباله نا صفر متناهی  است به طوری که جملات آن یک درمیان از راس ها ویال ها بوده و به ازای  دو سر  باشند. در این صورت می گوئیم w ، یک گشت از  تا  یا به عبارتی دیگر یک  گشت است. راس های  به ترتیب ابتدا و انتهای w و  راس های داخلی آن نامیده می شود. همچنین عدد صحیح k را طول w می نامیم.

اگر  دوگشت باشند ، گشت  را که از به هم پیوستن  در راس به دست می آید با نمایش می دهیم. یک قسمت از گشت ، گشتی است مانند ، که زیر دنباله ای از جملات متوالی wمی باشد و این زیر دنباله را - قسمت w می نامیم.

اگر یال های  در گذشت w متمایز  باشند، w یک گذرگاه نامیده می شود. در این حالت ، طول w برابر با می باشد. اگر علاوه بر یال ها ، راس های  نیز متمایز باشند ، wیک مسیر نامیده می شود.

می گوئیم دو راس uو از G همبند یا متصلند، اگر یک (,u (  مسیر در         G وجود داشته باشد . همبندی یک رابطه هم ارزی روی مجموعه راس های V تشکیل می‌دهد. بنابراین افرازی از V به زیر مجموعه های ناتهی (فرمول ها در فایل اصلی قرار دارد.) وجود دارد که در آن دو راس u و همبندند اگر و تنها اگر u و  هر دو متعلق به مجموعه  یکسانی باشند.

زیر گراف های (فرمول ها در فایل اصلی قرار دارد.) مولفه های G نامیده می شود. اگر گراف G دقیقاً یک مولفه داشته باشد ، همبند است و در غیر این صورت ناهمبند خواهد بود. تعداد مولفه های G را با  نمایش می دهیم.

دورها:

می گوئیم یک گشت ، بسته است ، اگر طول آن مثبت بوده ابتدا و انتهای آن یکسان باشند. یک گذرگاه بسته که ابتدا و راس های داخلی آن متمایز باشند، دور نامیده می‌شود. همانند مسیرها، گاهی اوقات لفظ «دور» را به منظور اشاره به گرافی که متناظر با یک دور است به کار می بریم ، یک دور با طول kراk- دور می نامیم.

یک k- دور بسته به اینکهk زوج یا فرد باشد ، یک دور زوج یا فرد می نامیم. غالباً به 3- دور ، مثلث گفته می شود.

یک گراف ، دو بخشی است اگر و تنها اگر هیچ دور فردی نداشته باشد.

اثبات: فرض کنید G یک گراف دوبخشی با دو بخش XوY و یک دور از G باشد. بدون اینکه از کلیت مساله کاسته شود، می توانیم فرض کنیم که.چون    دو بخشی  به همین دلیل  و در حالت کلی داریم: . از آن جایی که  پس ، در نتیجه به ازای یک مقدار i داریم  و بنابراین c زوج خواهد بود.

واضح است که اثبات عکس ، برای گراف های همبند کافی است. فرض کنید G یک گراف همبند باشد که هیچ دور فردی ندارد یک راس دلخواه مانند را انتخاب کرده، افزار (X,Y)  از V را به صورت زیر تعریف می کنیم.

(فرمول ها در فایل اصلی قرار دارد.)

نشان خواهیم داد که G یک گراف دوبخشی با دو بخش X و Y است فرض کنید دو راس X باشند.P را به عنوان کوتاهترین - مسیر و Q را به عنوان کوتاهترین - مسیر در نظر می گیریم.آخرین راس مشترک P وq را با  نشان می دهیم. چون P و Q کوتاهترین مسیر ها هستند، - قسمت های Pو Q نیز کوتاهترین - مسیر ها می باشند و بنابراین طول برابری خواهند داشت. از آن جایی که طول های P وQ هر زوج هستند، طول  - قسمت  از  و - قسمت  از  باید از نظر زوج و فرد بودن ، یکسان باشند. از اینجا نتیجه می شود که طول - مسیر زوج است. بنابراین هیچ دو راسی در X مجاور نیستند. به طور مشابه هیچ دو راسی از Y نیز مجاور نخواهند بود.

کاربردها:

مساله کوتاهترین مسیر:

فرض کنید به هر یال e از G ، یک عدد حقیقی w(e) ، که وزن آن نامیده می شود. نسبت داده ایم. دراین صورت G به همراه وزن های روی یال هایش ، یک  گراف وزندار نامیده می شود. گراف های وزندار در بسیاری از کاربردهای نظریه گراف ها پدیدار می شوند. به طور مثال در گراف دوستی ، وزن ها می توانند نمایانگر میزا علاقه و دوستی افراد باشند. در گراف ارتباطات، وزن ها می توانند نشان دهنده هزینه ساخت یا نگهداری پیوندهای ارتباطی باشند.

اگر H زیر گرافی از یک گراف وزندار باشد، وزن های روی یال های آن یعنی  است. بسیاری از مسایل بهینه سازی ، به یافتن یک زیر گراف خاص با کمترین (یا بیشترین) وزن، در یک گراف وزندار منتهی می شود. یک نمونه از این مسایل ، مساله کوتاهترین مسیر است که به این صورت تعریف می شود: یک شبکه راه‌آهن ، تعدادی شهرهای مختلف را به یکدیگر متصل می کند. کوتاهترین راه بین دو شهر مشخص را در این شبکه پیدا نمائید.