×
Music: Yanni - Felitsa | گذاشته شده در 96/07/23 

دنیاى من

دنیای من ، دنیاییست دور از زمین

سادیسم نویسندگی :)


امروز 1234 امین روز از عمر وبلاگمه و میخواستم یه چیزی بنویسم

حس و حال نوشتن از روزانه ها و اینکه چقدر حالم میتوه داغون و خراب و له باشه رو نداشتم

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

خب !

اینقدر چیز هست که نمیدونم کدومو بگم

فک کنم گراف بد نباشه !


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

به هر راس گراف میگیم vertex و به هر یالش هم میگیم edge مثل گراف شکل زیر که شامل 8 راس و 10 یال عه

متاسفانه راس های عکس پایین شماره گذاری نشدن ولی مثلا اگه شماره یکیشون u باشه و شماره یکی دیگشون v باشه و بینشون هم یال باشه میگیم راس u هم سایه راس v هست یا اصطلاحن میگی u و v مجاورن یا میگیم بینشون یه یال هست و به صورت u <-> v نشون میدیم (البته اگه یال جهت دار نباشه) به راسی هم که هیچ همسایه ای نداشته باشه میگیم ایزوله یا تنها

خب از آشنایی اولیه که بگذریم میشه چیز های خیلی جالب و حتی سخت و جذابی راجب گراف گفت
تاریخچه به وجود اومدن علم گراف جالبه و پیشنهاد میکنم برین بخونینش و در کل علم نوینیه و مثل چیزای دیگه ریاضیات قدمت چند هزار ساله نداره ، قدمتش از جنگ جهانی (یادم نیست اول یا دوم) به بعده

برای کسایی که احتمالا علاقه مند ان یا نیاز دارن بخونن هم کتاب introduction to Graph Theory , wrote by Douglas B West رو پیشنهاد میکنم ، ترجمه فارسیش هم افتضاحه خودتونو مثل من (و دگر المپیادی ها) سرش جر وا جر نکنین برین انگلیسیشو بخونین D:

کاربرد گراف توی کامپیوتر و برنامه نویسی (ووووو المپیاد کامپیوتر و کلا علوم کامپیوتر دیگه :/ ) تقریبا خیلی زیاده

حتی توی حل مسائل ریاضی هم کاربرد داره (مسائلی که صرفا خودشون گراف نیستن ولی میشه مدلشون کرد به گراف و دید بهتری نسبت بهشون پیدا کرد)

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

مثلا فرض کنین شما با k نفر دوستین و باهشون چت میکنین و فالوشون میکنین خب اونا میان به صورت دید گراف شمارو به اون k تا وصل میکنن (یعنی بین راسی که شما و اون k نفر یه یال میذارن) و همین کارو برای اون k تا دوستتون هم میکنن و اینجوری یه شبکه از اطلاعات سامان دهی شده دارن ، حالا هر موقع خواستن یکیو پیدا کنن که فلان خصوصیت رو داشته باشه از طریق شما اقدام میکنن البته اینی گفتم یه دید ساده بود قطعا اونا یه سری اطلاعات دقیق تری رو نگه داری میکنن کنارش ، یا مثلا اگه خواستن اطلاعات رو به دولت ها بفروشن به صورتی که هویت هر فرد رو دقیقا افشا نکنن میان یه همچین گرافی رو بهشون میدن که دامنه و گستردگی ارتباط هر فرد رو نشون میده ، یا مثلا اگه یه مطلبی با موضوع x رو n نفر منتشر کردن (مثل هشتگ فلان بیسار) میان بین x و اون n نفری که این موضوع رو انتشار دادن یال میدن و هر موقع خواستن اطلاعاتی راجب مطلب x رو پیدا کنن از این طریق اقدام میکنن این اقدام میتونه فروختن این اطلاعات باشه تا استفاده برای ساختار داخلی شرکتشون

خلاصه که در این موارد کاربر های جالبی داره

گراف خودش انواع مختلفی داره که گفتن همشون تو این یه پست کار سختیه ! :)

از نمونه سوال هایی که با الگوریتم های مختلف در مورد گراف حل کردم میتونم به :

http://codeforces.com/problemset/problem/862/B

http://codeforces.com/problemset/problem/902/B

http://codeforces.com/problemset/problem/278/C

http://codeforces.com/problemset/problem/920/E

و... اشاره کنم

توی علوم کامپیوتر گراف ها الگوریتم های زیادی دارن مثلا dfs ، bfs ، dijkstra ، SCC و غیره...

خب برای اینکه پست خالی از لطف نباشه چند تا سوال هم میذارم برای علاقه مندان :))
البته قبلش یکم راجبش مطالعه کنین بد نیست (اگه راجب گراف هیچی نمیدونین و میخواین سوالارو حل کنین :دی)

سوالا رو از 1 لول بندی مکینم عدد پایینتر یعنی سوال اسون تره نسبت به بقیه :))

1 - ثابت کنید که یک گذر بسته ، شامل یک دور میباشد (1)

2 - ثابت کنید گرافی که درجه هر راسش بیشتر مساوی 2 باشه دور داره (1)

3 - گراف 101 راسی داریم ، راسی وجود دارد که تمام دور های فرد از آن میگذرند ، حداکثر یال های این گراف چقدر است ؟ (2)

4 - اگر گراف G مثلث آزاد و n تعداد راس ها و m تعداد یال ها باشد ثابت کنید: (3) $$m \le \frac{n^2}{4}$$

پ.ن: البته به دلیل دیر عمل کردن بنده ساعت از 12 گذشت و رفتیم تو فردا و الان شد 1235 روز عمر وبلاگ :)

پ.ن2: برای خوب شدن یه دوست تا دوباره سالم و سر پا ببینمش دعا کنید :)


دیدگاه ها

آواتاز    Dark. MH میگه:
   ۲۰ آبان ۹۷ ، ۲۲:۰۵
این لامصب توی هندسه تحلیلی هم هست
توی منطق هم هست
توی خود هندسه هم هست
توی هنر هست +_+
آواتاز    پاسخ:
   ۲۱ آبان ۹۷ ، ۰۰:۰۲
:)))
آواتاز    Dark. MH میگه:
   ۲۰ آبان ۹۷ ، ۲۱:۴۵
گراف به تنهایی پتانسیل شو داشت یه شاخه جدا بشه از ریاضی
۱. جبر
۲. هندسه
۳. نظریه اعداد
۴. ترکیبیات
۵. گراف
آواتاز    پاسخ:
   ۲۰ آبان ۹۷ ، ۲۲:۰۲
البته گراف و ترکیبیات یه جوری با هم در یه تداخلی هستن ولی خب ما جدا هم حسابش میکنیم :))))
آواتاز    پر ِ بنفش میگه:
   ۲۰ آبان ۹۷ ، ۱۷:۰۸
ما اینیم دیگه! نمیشه از گراف گذشت :`)))
آواتاز    پاسخ:
   ۲۰ آبان ۹۷ ، ۲۰:۴۸
عه :))
پس در آینده پست های دیگری هم در رابطه با گراف بذارم :)))
آواتاز    پر ِ بنفش میگه:
   ۲۰ آبان ۹۷ ، ۱۵:۳۴
اه خیلی ظیبا بود!!! 

آواتاز    پاسخ:
   ۲۰ آبان ۹۷ ، ۱۶:۳۴
عه کلشو خوندی ؟
فک نمیکردم کسی کلشو بخونه D:

ارسال دیدگاه


شما هم دیدگاه خود را ارسال کنید   :)

کاربران بیان میتوانند بدون نیاز به تأیید، نظرات خود را ارسال کنند.
اگر قبلا در بیان ثبت نام کرده اید لطفا ابتدا وارد شوید، در غیر این صورت می توانید ثبت نام کنید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">