الگوریتم های گراف

[monajem]

یه گراف داریم.می تونیم یه راسو برداریم.وقتی یه راسو برمیداریم تمام راس های متصل به اون حذف میشن.

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

 

[parsa_spy]

پاسخ : الگوریتم های گراف

1- این بیشتر به المپیاد کامپیوتر ربط نداره؟

2- راس هایی که در انتها ور داشتیم، نسبت به همدیگه یه مجموعه مستقل تشکیل می دن! ( بدیهیه! اثبات نمی خواد! چون اگه مجموعه مستقل نبودن، نمی شد همشون رو برداشت)
پس سوال تبدیل می شه به این: بزرگتری مجموعه مستقل رو توی یک گراف پیدا کنیم!

اما متاسفانه پیدا کردن بزرگترین مجموعه مستقل توی یک گراف، NP-complete هست و براش راه حل چند جمله ای وجود نداره!
فقط توی گراف 2 بخشی راه حل چند جمله ای وجود داره! برای همین اصلا نمی شه الگوریتمی از زمان چند جمله ای برای سوال شما ارائه داد

 

[monajem]

پاسخ : الگوریتم های گراف

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

 

[parsa_spy]

پاسخ : الگوریتم های گراف

ببین خوب الان قبول کردی سوال تو، دقیقا هم ارزه با اینکه بگیم : می خوایم بزرگترین مجموعه مستقل رو توی یک گراف پیدا کنیم.
این رو قبول داری؟ اگه نه بگو واست اثبات کنم

حالا اگه این رو قبول داری، این سوال ( بجز توی گراف 2 بخشی) الگوریتم چند جمله ای نداره! اگه حرف من رو باور نمی کنی ویکیپدیا رو بخون

 

[maziar]

پاسخ : الگوریتم های گراف

گراف
گراف ها به عنوانه ساده ي نقطه و خط تاثير بسيار زيادي در اساني حل يك سواله الگوريتمي مي تونن داشته باشن.
به خاطر همين خواستم توضيح كمي در باره ي اين موضوع بدم.
گراف : مجموعه اي از نقطه(راس يا هر چي شما بخواي كلن ورتكس ) و يال (خط منحني يا هر چيزي كه يك راس رو به خودش يا راسي ديگه متصل كنه. ادج)
حالا گراف ها مي تونن جهت دار(دايركتد) يابي جهت باشن(ايندايركتد )
مي تونن ساده باشن يا نباشن (a simple graph is a graph with no loop and multiple edge) يعني گراف پيچيده گرافيست كه طوقه(يالي كه يك راس رو به خودش وصل كنه) و يال هايه چندگانه(كلمه ي واضح تري براي توضيح نداشتم) نداشته باشه.

ما در گراف ها چيزي تحته عنوان قدم زدن(walk) و مسير (path) تعريف مي كنيم. تنها فرقشون اينه كه قدم زدن از ياله تكراري ممكنه ولي در مسير نه.

خوب با استفاده از تعريف بالا يك گراف رو كانكتد تعريفمي كنيم اگر بين هر جفت راسي خداقل يك مسير وجودداشته باشه.
بداهتن گرافي كه كانكتد نباشه ديس كانكتد هست يعني حداقل يك جفت راسي هست كه بينشون مسيريوجود نداره

دور : اگر ابتدا و انتهايه يك مسير يك راس باشه مادور داريم :)

dor : circle toqe : loop
اين دو تا رو قاطي نكنيد.

خب حالا يه مشت مقدمه مي گم :
اولاينكه من گرافو اولين بار از كتابه معروف وست خوندم و پدرم و اجدادم شب هابه خوابم اومدن چرا ؟
١. اولين كتابه رياضي بود كه به انگليسي خوندم
٢. وست خيلي سخت توضيح داده
٣. وست خيلي خيلي دقيقه و خب حله سوال هاش اونقدر سخت نيست كه فهميدن سوال هاش هست.

و من چند تا نتيجه گرفتم :
١. كتاب هايه تخصصي رو به زبانه انگليسي بخونم.
بياين بپذيريم كه بعضي بحث ها خيلي خوب نميشه ترجمه كرد. منابع فارسي كيفيته خوبي ندارن. خيلي رياضوي هستن. و خب بايد ياد گرفن به زبان مبدا كتاب هارو حوند

بعد چون برايه ما جنبه ي الگوريتمي و اناليكالي گراف ها بر بخش رياضويشون ارجحيت داره من يه منبع دارم كه اونو بهتون مي دم
درواقع نت هايه لكچره پيتر هافمن هست. البته من با اجازه دارم اين كار هارو مي كنم و از منابع ازاد استفاده مي كنم و مشكل كپي رايت وجود نداره.
خب بديهتا به راحتي بودن سره كلاس نيست ولي ميشه پيش رفت باهاش
اين تاپيك بسته مي مونه و يه تاپيك هم زمان با اين ايجاد ميشه برايه جواب به سوال هايه ممكن حتا اگه با زبانش مشكل داشتيد بگيد.
من هر هفته قسمتي از اين نوت هارو مي ذارم كه همه با يه سرعت پيش برن
اگه توضيحي بيشتر تو اون يكي تاپيك بخوايد كه فكر كنم برايه همه لازم هست اون رو هم اينجا اضافه مي كنم بعد در نهايت يه كتاب مانند به كسايي كه بخوان مي فرستم. با فرمت پي دي اف.
مشابه همين بحث رو برايه رمز گذاري و بحث هايه ديگه هم مي ذارم اگر بخوايد
اگر دوست داشتيد پايتون هم ياد بگيريد منبع مي دم

<a href = "http://www.udacity.com/wiki/CS215Unit1?course=cs215"> اینم لینکش درس اول کورس نت </a>

 

[Dark Eagle]

پاسخ : الگوریتم های گراف

تو کتاب creative هر چی الگوریتم گرافه اومده تازه یه عالمه منبع هم داده که میشه ازشون مستفیز گردید.
(فصل 7)