تبلیغات
علم - ریاضیات گسسته

علم

شنبه 3 مهر 1389

ریاضیات گسسته

نویسنده: parsa   طبقه بندی: *ریاضی*، 

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

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




موضوعات مورد مطالعه در ریاضیات گسسته

* ترکیبیات (شاخه‌ای از ریاضیات گسسته که به شمارش و مطالعه‌ی مجموعه‌های متناهی می‌پردازد.)
* نظریه گراف
* منطق ریاضی
* نظریه مجموعه ها
* نظریه مقدماتی اعداد

نظریه گراف
نظریه گراف شاخه‌ای از ریاضیات است که دربارهٔ گراف ها بحث می‌کند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یال‌هایی‌ به هم وصل شده‌اند.





نمایش تصویری یک گراف



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

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

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

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

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

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و ... است.

روابط میان راس های یک گراف را می‌توان با کمک ماتریس بیان کرد .



انواع گراف
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.

گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.

گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است.

گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.










قضیه چهاررنگ


قَضیّهٔ چهاررَنگ یا حدس چهاررنگ از مسائل مشهور و قدیمی ریاضیات است که سال‌ها اثبات نشده مانده بود.
به بیان ساده (و نادقیق) این قضیه می‌گوید:

برای رنگ کردن هر نقشه به طوری که کشورها و نواحی همسایه در نقشه هم‌رنگ نباشند فقط چهار رنگ کافی است.

این مسئله به صورت معادله ابتدا درسال۱۸۵۲ عنوان شد و سرانجام در سال ۱۹۷۶ با کمک رایانه توسط کی اپپل و و. هیکن حل شد.
این کار در طول ۱۲۰۰ ساعت فعالیت سریعترین رایانه‌های زمان خود انجام شد که با دسته بندی بیش از چند میلیون گراف به این نتیجه رسیدند.



مثالی از یک "نقشه" چهاررنگ

نظرات() 
What causes the heels of your feet to burn?
یکشنبه 15 مرداد 1396 11:24 ب.ظ
I couldn't resist commenting. Well written!
Foot Complaints
شنبه 14 مرداد 1396 09:32 ق.ظ
Good day I am so grateful I found your site, I really found
you by accident, while I was looking on Aol for something else, Anyways I am here now and would just like to say many thanks for
a tremendous post and a all round enjoyable blog (I
also love the theme/design), I don’t have time to browse
it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I have time I will be back to read a lot more, Please do
keep up the superb jo.
Samira
شنبه 7 مرداد 1396 07:24 ب.ظ
Everything is very open with a really clear description of the issues.

It was definitely informative. Your site is very helpful.
Many thanks for sharing!
Francesca
دوشنبه 25 اردیبهشت 1396 03:27 ق.ظ
Thanks a lot for sharing this with all folks you really realize what you're talking approximately!
Bookmarked. Kindly also consult with my site =).
We will have a link alternate arrangement among us
http://kyungklauer.hatenablog.com/
پنجشنبه 21 اردیبهشت 1396 10:52 ق.ظ
It's great that you are getting thoughts from this piece of
writing as well as from our discussion made at this place.
BHW
جمعه 1 اردیبهشت 1396 01:45 ق.ظ
Hello There. I found your blog using msn. This is an extremely well written article.

I will be sure to bookmark it and return to read more of your useful information. Thanks
for the post. I will certainly comeback.
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر

آمار وبلاگ

  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :