تاریخچه نظریه گرافها

مقدمه:
اندک زمانی است که واژه گراف در ادبیات ریاضی وارد شده است، گرچه شروع آن را می توان از زمان لئناردو اویلر ریاضیدان سوئیسی (1707-1783) دانست. اما علاقه ی شدید و مداوم به نظریه ی گراف ، بعنوان شاخه ای از ریاضیات ، از سال 1930 به بعد، آشکار گردید و امروزه این نظریه یکی از پربارترین و محبوب ترین شاخه های ریاضیات و علوم کامپیوتر است و علت آن نیز به خاطر قابلیت کاربرد آن در بسیاری از مسائل گسترده ی جامعه مدرن امروزی است.هنگامی که مساله ای به زبان گراف فرمول بندی شد، درک آن بسیار آسان تر خواهد شد. امروزه نظریه ی گراف یکی از موضوعات مهم دئر ریاضیات گسسته است. گرافها، مدل های راضی برای یک مجموعه گسسته هستند، که اعضای آن به طریقی با هم مرتبط می باشند. اعضای این مجموعه می توانند انسان ها یا رابطه ی خویشاوندی ، یا دوستی و… باشد. اعضای این مجوعه می توانند، محل اتصالهای سیم های یک شبکه ی برق و رابطه ی آنها، سیم های واصل بین دو مقطه باشد و یا عناصر مجوعه می توانند اتم های یک مولکول و ارتباط آن ها، اتصالهای شیمیایی باشد. نظریه گراف ریشه در بازیها و معما ها نیز دارد، اما امروزه این نظریه نه تنها در ریاضیات بلکه در سایر علوم مانندا اقتصاد، روانشناسی،ژنتیک و باستان شناسی کاربرد فراوانی دارد.
مفهوم گراف:
واژه گراف، نه تنها در ریاضیات، بلکه در سایر علوم و حتی در زندگی روزانه به نام های گوناگون مانند طرح دیاگرام، نگاره، نقشه، ماز و… بکار می رود. مثلا ممکن است به بهانه های مختلف شکلی رسم کنیم که از نقطه هایی تشکیل شده باشد و اگر چند نقطه، رابطه هایی با هم داشته باشند این روابط را با کشیدن خط بین آن ها نشان دهیم. نیز می توانیم تیم های ورزشی را در نظر بگیریم و آن ها را با نقاط A,B,C,… روی صفحه رسم کنیم و خطوط را با این شرط وصل کنیم که آن تیم ها با هم بازی داشته باشند، در ابتدا که بازی صورت نگرفته فقط چند نقطه داریم، ولی وقتی تیم ها باهم بازی کردند، بین تمام نقاط خط هایی وصل کنیم، بدین ترتیب یک گراف ساخته ایم، که با یک نگاه، راحت متوجه رابطه بین نقاط می شویم. بدیهی است که در انتخاب مکان نقاط در صفحه و طرز رسم کردن خطوط آزاد بوده ایم. اگر هیچ تیمی بازی نکرده باشد، هیچ خطی وصل نمی شود و در این صورت گراف، گراف صفحه نخواهد بود و اگر با هم بازی کنند، گراف کامل بوجود می آید.
قابل ذکر است که اگر نقاط را رئوس گراف و خطوط را یال بنامیم داریم: G(V.E) که آن را گراف G با رئوس V. و یال های E می نامیم.
اکنون به معرفی چند نوع گراف می پردازیم:
1) گراف های یکریخت: اگر در دو گراف، تعداد راس ها برابر بوده، بطوریکه هر دو راس متناظر، با یک حرف نام گذاری شده باشد، آن گاه وقتی دو راس بوسیله ی یالی بهم مربوط باشند، راس های هم نام آن ها در گراف دوم نیز بوسیله ی یالی بهم مربوط شوند.
2) گراف همبند و ناهمبند: اگر از هر دو راس دلخواه گراف، بتوان با حرکت روی یال ها، به راس دلخواه دیگر رسید، چنین گرافی همبند و در غیر این صورت ناهمبند است، یعنی گراف همبند از یک قطعه و ناهمبند از چند قطعه تشکیل می شود.
مرتبه، اندازه و درجه گراف:
به تعداد رئوس هر گراف مرتبه و به تعداد یالهای آن، اندازه و تعداد یال های منتهی به یک راس را درجه ی آن گراف گوییم.
بدیهی است که در گراف صفر درجه، هر راس برابر صفر است و در گراف کامل با n راس درجه، هر راس برابر با n-1 خواهد بود. راس هایی که درجه زوج دارند راس های زوج و راس هایی که درجه فرد دارند راس های فرد، نامیده می شوند. مساله حایز اهمیت این است که در هر گراف، تعداد رئوس فرد، زوج هستند، یعنی نمی توان گرافی رسم کرد که مثلا: 3 تا راس فرد داشته باشد. بعنوان مثال نمی توان گرافی رسم کرد که درجه راس های آن 5،0،2،2،5،8،7،6 باشد زیرا تعداد رئوس فرد 3 تا هستند یعنی(5،7،5)! ریاضیات گسسته و نظریه گراف

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

گراف ها و درخت ها موضوعاتی ساده و در عین حال بسیار کاربردی در ریاضیات هستند. اینگونه که پیشرفت علوم نشان داده , این مباحث هنوز هم جا برای کار دارند و می توان کاربردهای جدیدی را برایشان تعریف کرد. با هم به نمونه های زیر توجه می کنیم.

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

تاریخچه نظریه گرافها

مطالب مشابه :

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

نمونه سوالات درس « نظریه گراف و کاربردهای آن »+همراه پاسخنامه

نمونه سوال نظریه گراف و کاربردهای آن پیام نور کلیه گرایش ها 91-90

نظریه گراف

نمونه سوال نظريه گراف و كاربردهاي آن

تاریخچه نظریه گرافها

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

بارم بندی جدید ریاضیات گسسته چهارم ریاضی

روش مطالعه گسسته

لیست جدید ارائه دروس مهندسی فناوری اطلاعات(طرح تجمیع)