الگوریتم‌های streaming (دانشگاه هاروارد)

http://people.seas.harvard.edu/~jthaler/COSC548.html

تبدیل عکس به word-cloud

http://www.wordclouds.com/
من عکس خودم را با محتوای مقاله‌ی قبلیم دادم بهش! :))

کتاب نظریه بازی‌ها

http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/twenty-lectures-algorithmic-game-theory?format=PB

من EBook این را پیدا نکردم، اما preview آن در Google Books هست:

https://books.google.com/books?isbn=1107172667

یک سری از سوالهایش هم آنجا آمده است.

درس نظریه بازی‌های MIT

http://people.csail.mit.edu/costis/6896sp10/

15-859(J): Algorithmic Applications of Metric Embeddings

https://www.cs.cmu.edu/~anupamg/metrics/

مثال از ضرب زیگزاگی گراف

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/notes5.pdf

درس گسترگراف دانشگاه دیگر

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws10/EG/WS10.html

Ramanujan graph

https://en.wikipedia.org/wiki/Ramanujan_graph
گسترگرافی است که بیشترین اختلاف بین مقدار ویژه‌هایش هست. به خاطر همین مثال اکسترمال (ماکسیمال/مینیمال) برای خیلی از ویژگی‌ها است.
(من تا حالا فکر می‌کردم این یک گراف خاص است الآن دیدم فقط یک ویژگی است مثل مسطح بودن.)

رنگ‌آمیزی گراف با گسترگراف

http://www.cs.yale.edu/homes/spielman/561/lect03-15.pdf

قضیه ویلف

همیشه k هست که می‌شود طوری رأسها را مرتب کرد که یالهای خروجی که به سمت رأسهای با اندیس کمتر هستند حداکثر k باشد. حالا یک گراف جهت‌دار داریم که حداکثر درجه‌اش k است پس با k+1 رنگ می‌شود رنگ‌آمیزیش کرد.

قضیه ویلف می‌گوید k<=mu_1 باشد همیشه این خاصیت را دارد.

متوسط درجه‌ی گراف حداکثر mu_1 است. چون همیشه یکی هست که از امید ریاضی کمتر است، بزرگترین کسی که این خاصیت را دارد انتخاب می‌کنیم و آخر می‌گذاریم. زیرگراف روی n-1 رأس دیگر را در نظر می‌گیریم. وقتی یک سطر یا ستون از یک ماتریس متقارن را حذف می‌کنیم، بزرگترین مقدار ویژه‌ی آن کمتر مساوی مقدار فعلی می‌شود. پس می‌شود همین عمل حذف کردن رأس را به ازای ماتریس مجاورت این زیرگراف ادامه بدهیم تا همه چیده شوند.

کران هافمن

می‌گوید می‌شود طوری رأسها را اندیس‌گذاری کرد که ماتریس مجاورتش به صورت یک ماتریس بلوکی با k بلوک و قطر صفر باشد که هر بلوکی متناظر یک رنگ است. حالا با استفاده از ویژگی‌های مقدار ویژه‌های ماتریس به این شکل یک کران به دست می‌آورد.

سوالهای آخر کتاب تراویسان

سوال ۱ می‌گوید ثابت کنید کسر لایتون-رائو بعد از جایگزین کردن کوتاه‌ترین مسیر روی جواب LP به جای وزن یالها به مقدار کمتری می‌رسد و همچنان یک جواب برای LP هست.
خب برای این کار به LP مربوطه یک نگاه می‌اندازیم. قید‌های آن نصفشان مربوط به شبه‌متر هستند که تغییر نمی‌کنند و فقط یک قید است که می‌گوید جمع وزن یالهای H با یک ضریب d برابر E[H]/E[G] می‌شود.

طبیعتاً برای قیدهای شبه‌متر بودن مشکلی پیش نمی‌آید چون کوتاهترین مسیر در گراف خودش یک متر است (نامساوی مثلث برایش صادق است و نامنفی هم هست اگر یالها نامنفی باشند).

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

پس حالا فقط می‌ماند این که ثابت کنیم که این جواب کمتری می‌دهد. چون ضریب G_{u,v} تغییر نکرده است ولی ضریب d_{u,v} کم شده پس این جواب از قبلی بهتر است.

سوال ۲ می‌گوید برای حالتی که در صورت یک دور باشد و در مخرج یک گراف کامل، ثابت کنید که این کوتاهترین مسیر جواب بهینه است. خب ما می‌دانیم جواب بهینه‌ی این مثال خاص این است که دور را از وسط نصف کنیم و گراف کامل مخرج هم نصف می‌شود. کوتاهترین مسیر در گراف G که یک دور است می‌شود مینیمم فاصله‌ی دو رأس در یکی از دو جهت ممکن روی دور. کوتاهترین مسیر در H هم که ۱ است چون گراف کامل است. جمع و تقسیم کنیم باید همین به دست بیاد.