لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 8
به نام ایزد منان
گراف
(گراف همیلتنی)
استاد مربوطه :
جناب آقای غلامی
گرداورنده :
زکیه صدقی
بهار87
گراف و طبقه بندی آن
گراف شاخه‌ای جدید و بسیار جالب در ریاضیات می‌باشد. در ریاضیات تعریفهای مختلفی برای گراف ارائه می‌شود که این تعریفها با توجه به سطح مخاطب از شهودی به صوری حر کت می‌کند.
تعریفی که ما از گراف برایتان ارائه می‌دهیم، یک تعریف تقریبا شهودی می‌باشد:
یک گراف شامل نقاطی است که راس نامیده می‌شود و این راسها به وسیله خطوطی (که لازم نیست خط راست باشند) به هم وصل می‌شوند. این خطوط را یال می‌گوئیم.در بعضی از کتابها از کلمات گره و نقطه هم به جای راس استفاده می‌شود.
ریشه لغوی :
«گراف » از کلمه «Graph» از زبان انگلیسی گرفته شده است که به معنای نمودار و طرح هندسی می‌باشد.
دید کلی
گراف یکی از رشته‌های به روز ریاضیات است. امروزه مسائل زیادی وجود دارد که تا بحال حل نشده‌اند و در دانشگاههای معتبر هم در ایران و هم در خارج به عنوان رشته‌ای تخصصی نیز به گراف توجه می‌شود. به راحتی می‌توانیم بگوییم که گراف از مسائل کاربردی واقعا زیادی تشکیل شده، بطوری که مسائل روزمره مانند مسائل مربوط به دوستی (به عنوان رابطه دو طرفه) ، دست دادن ، ازدواج ، شجره‌نامه و هزاران هزار رابطه قابل تفسیر و نشان دادن به شکل گراف هستند که رابطها در این موارد متناظر با یالهای گراف می‌باشند. مسائل همبندی ، مسئله پلهای کونینگسبرگ (Koningsbrega) ، مسئله چهار رنگ ، مسئله پستچی دوره گرد ، مسئله جورسازی و ... تنها قسمتی از مسائل جالب و مشهور در تئوری گراف می‌باشند.
تاریخچه
در زمان » اویلر « ، هفت پل در رودخانه‌ای که منشعب به دو قسمت می‌گشت، مسئله جالبی را برای گردشگران و اهالی ایجاد کرده بود و آن گذر از تمامی پلها به صورتی که از هر پل فقط یک بار عبور کنند، بود. این رودخانه در شهر کونینگسبرگ قرار داشت؛ به همین دلیل این مسئله به مسئله پلهای کونینگسبرگ مشهوراست.
خیلی جالب است بدانید که مردم در این شهر دیگر بر این باور رسیده بودند که چنین مسیری وجود ندارد و این مسئله را به اویلر مطرح کرده بودند و جالب‌تر اینکه اویلر ثابت کرد چنین مسیری واقعا وجود ندارد و یافت نمی‌شود. دست نوشته‌های مربوط به این مسئله که در سال 1736 م. توسط اویلر نوشته شده بودند، به عنوان قدیمی‌ترین دست نوشته‌های مربوط به گراف تلقی می‌گردند. در این نوشته‌ها لم دست دادن نیز دیده می‌شود.
نقش و تاثیر زندگی
مسائل زیادی در زندگی مطرح می‌شود که قابل تبدیل به مسائل گراف هستند. امروزه بهینه بودن انتخابها خیلی اهمیت دارد. این بهینه بودن شامل انتخاب کوتاهترین مسیر در مسافرت از شهری به شهر دیگر ، عبور از تمامی کوچه در کمترین زمان برای پک پستچی و ... می‌باشند که در گراف مورد بحث قرار می‌گیرند. پیشرفت علوم و فناوری اطلاعات ، افزایش استفاده از کامپیوتر و وابستگی این علوم به نظریه‌های گراف اهمیت بحث گراف را در زندگی و آینده نزدیک نشان می‌دهد. به هر حال تکنولوژی و بهنیه کردن آن در عرصه صنعت لزوم استفاده را بیشتر برای ما روشن می‌کند، اما از نظر ریاضی بهترین دیدی که شاید بتوان ارائه داد، نگاه به تئوری گراف به عنوان ابزار کمک کننده حل مسائل است، نه حل آنها. جالب است بدانید که نظریه گراف در حل مسائل ریاضی سایر شاخه‌ها نیز کمک کننده می‌باشد.
طبقه بندی‌های مشهور در تئوری گراف
گراف همبند و ناهمبند
یک گراف همبند است اگر بین هر دو راس دلخواه آن مسیری وجود داشته باشد. در غیر این صورت گراف را ناهمبند گوئیم.
گراف اویلری و نااویلری
یک گراف همبند اویلری است اگر دارای گشتی بسته باشد که از همه یالهایش گذر می‌کند. در غیر این صورت نااویلری است.
گراف همیلتنی و ناهمیلتنی
یک گراف همبند همیلتنی است اگر دوری وجود داشته باشد که شامل همه رئوس آن باشد. در غیر این صورت ناهمیلتنی است.
گراف مسطح و غیرمسطح
یک گراف مسطح است اگر بتوان آن را طوری کشید که هیچ دو یالی یکدیگر را مگر در راسها قطع نکنند. بطوری که در آن راس دو یال فوق مجاور می‌باشند. گرافی را که مسطح نباشد، غیرمسطح گوئیم.
درخت :گراف فاقد دور و بدون حلقه را درخت می‌نامیم.
گرافهای دو بخشی ، کامل ، n _ منتظم
گراف دو بخشی گرافی است که راسهای آن را بتوان به دو بخش A و B چنان تقسیم کرد که هر یال در گراف یک راسش در A باشد و راس دیگرش در B. گرافی که بین هر دو راس آن یالی باشد، گراف کامل می‌گوئیم. یک گراف ،_ n منتظم است اگر درجه همه راسهایش n باشد.
مقاله در مورد گراف