دنیاى من

امروز 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: برای خوب شدن یه دوست تا دوباره سالم و سر پا ببینمش دعا کنید :)