منبع فایل کامل این پایان نامه این سایت pipaf.ir است

 

 

 

 

 

 

 

 

۱-۱- ۳ تاریخچه نظریه گراف.
برخلاف شاخه‌های دیگر ریاضیات، سیر نظریه گراف آغاز معینی در زمان و مکان دارد وآن مسئله هفت پل کونیگسبرگ است که در سال ۱۷۳۶ توسط لئونارد اویلر حل شد. در سال۱۷۵۲ قضیه اویلر برای گراف‌های مسطح ارائه می‌شود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.
در سال ۱۸۴۷،گوستاو کرشهف[۷] نوع خاصی از گراف‌ها به نام درخت را مورد بررسی قرار داد. کرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی درکاربردهایی که حاوی شبکه‌های الکتریکی بودند به‌کار گرفت. ده سال بعد،آرتورکیلی۲ همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربنهای اشباع شده به ‌کار برد.
درهمین دوران شاهد حضور دوایده مهم دیگردرصحنه هستیم. ایده اول حدس چهار رنگ بودکه نخستین بار توسط فرانسیس گوثری[۸] در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط کنث ایپل[۹] و ولفگانگ هیکن[۱۰] و با استفاده از یک تحلیل رایانه‌ای پیچیده حل شد.
ایده مهم دوم، دور همیلتونی بود. این دور به افتخار سرویلیام روآن همیلتون[۱۱] نامگذاری شده است. او این ایده را در سال۱۸۵۹ برای حل معمای جالبی حاوی یال‌های یک دوازده وجهی منتظم به‌کار گرفت. یافتن جوابی برای این معما چندان دشوار نیست، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که گراف‌های بیسوی حاوی مسیر یا دورهای همیلتونی را مشخص کنند.
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئله مشخص کردن گراف‌های مسطح را کازیمیر کوراتوفسکی۵، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب درباره نظریه گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان مجار، دنش کونیگ۶، که خود محقق برجسته‌ای در این زمینه بود، نوشت. از آن پس فعالیت‌های بسیاری در این زمینه صورت گرفته و رایانه نیز در چهار دهه اخیر به یاری این فعالیت‌ها آمده است.
۱-۱-۴ اندازه گراف.
اندازه گراف تعداد یال‌های یک گراف است و به صورت E(G)بیان می‌شود.
۱-۱-۵ درجه راس‌ها.
در نظریه گراف‌ها، درجه یک راس به تعداد یال‌های متصل به آن راس گفته می‌شود. بعبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)‌های مستقیم یک راس را بیان می‌کند. از آنجا که هر یال در گراف دو راس را به هم وصل می‌کند، مجموع درجه راس‌های یک گراف با دو برابر تعداد یال‌های آن گراف برابر است.
۱-۱-۶ تعریف مسیر.
مسیر بین دو راس متمایز و غیرصفرx , xn G ، از گراف غیرجهت دار G را به صورت یک دنباله ناصفر و متناهی− x1 − − xi – xi + 1 − − xn x از رأس های متمایز G نشان می دهند
به طوری که به ازای هر عدد صحیح ≤ I ≤ n ، رأسهای xi +1 , xi مجاورند.
…
…
۱-۱-۷ تعریف دور.
یک دور در گراف G عبارت است از مسیر بین دو رأس ناصفر و متمایز x , x n G ، بطوریکه این مسیر حداقل از سه رأس متمایز و ناصفر تشکیل شده باشد و x وxn نیز مجاور باشند.
۱-۱-۸ گراف همبند.
گرافی است که حداقل یک مسیر بین هر دو راس آن وجود داشته باشد.
۱-۱-۹ گراف ساده.
هر گرافG زوج مرتبی مانند (V , E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G می‌نامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقه‌ای (یعنی یالی که رأس را به خودش وصل می‌کند) نیز وجود نداشته باشد.
۱-۱-۱۰ گراف همیلتونی.
گراف ساده ی G از مرتبه V هرگاه دوری به طول V در آن یافت شود.
۱-۱-۱۱ گراف اویلری و همیلتونی.
گاهی اوقات که دریک گراف حرکت می کنیم و از راسی به راسی دیگرمی رویم. در این صورت ممکن است مهم باشد که ازروی یال یا راس تکراری حرکت نکنیم(مشابه مساله فروشنده دوره گرد).این مساله درصرفه جویی زمان وهزینه هم مهم است.(یعنی مبحث بهینه سازی) دراینجا دو موضوع گرافهای اویلری(دور زدن درگراف بدون یال تکراری)وهمیلتونی(دور زدن بدون راس تکراری)را در برمی گیرد. به راحتی می‌توان بررسی کرد که راسهای گراف اویلری باید درجه زوج داشته باشند. اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده مانده ‌است.
۱-۱-۱۲ گراف دوری.
در نظریه گراف، گراف دوری به گرافی که متشکل از یک دور باشد گفته می‌شود، یا به عبارت دیگر تعدادی رأس که بصورت زنجیری به یکدیگر متصل شده‌اند. گراف دوری با n رأس با نماد Gn نشان داده می‌شود. گراف دوری گرافی همبند بوده که درجه هر رأس آن دو می‌باشد. تعداد رأس‌ها و یال‌های این گراف نیز برابر می‌باشد.