PDA

View Full Version : گراف



funnygirl
دوشنبه 04 اردیبهشت 1385, 13:55 عصر
چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟

Amir Oveisi
دوشنبه 04 اردیبهشت 1385, 16:24 عصر
فکر نمیکنین که اینو باید تو قسمت الگوریتم مطرح میکردین؟

seyedof
سه شنبه 05 اردیبهشت 1385, 08:48 صبح
سلام
من منظور از گراف دو بخشی رو نمیدونم ولی اگر منظور گراف نا همبند باشه ناهمبند بودن یک گراف معادل اینه که از حداقل یکی از راس ها به حداقل یک راس دیگه مسیری وجود نداشته باشه. حالا اینو اگه بشه با ماتریس مجاورت حل کرد، جواب سوال شما هم در میاد.
ممنون علی

mzjahromi
سه شنبه 05 اردیبهشت 1385, 08:53 صبح
چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
با الگوریتم Depth First Search اگه مجبور بشی بیش از یک بار تابع بازگشتی رو کال کنی یعنی گراف چند تکه هست.

mohandese_hiclass
چهارشنبه 06 اردیبهشت 1385, 02:05 صبح
از روش بالا هم میشه می تونی از جستجوی سطحی هم استفاده کنی که پیاده شازیش راحتتره

Mega7000
چهارشنبه 06 اردیبهشت 1385, 19:10 عصر
می تونید از همبندی استفاده کنین
یعنی اینکه یه آرایه بگیرین که اندازش تعداد گره های گرافتون باشه،
مقدار اولیه کل آرایه رو صفر میدین
حالا به اولین گره که می رسین اونو یکی اضافه می کنین
حالا واسه گره بعدی نگاه می کنید که اگه گره فعلی به قبلی وصله،همون عدد قبلی رو بهش میدین اما اگه وصل نیست یه عدد متمایز دیگه میدید
واسه همه گره ها این کار رو می کنید
در آخر اگر فقط در عناصر آرایه فقط دو دسته عدد داشتین(مثلا 1و1و1و2و2و1و1) این گراف دو بخشیه؛ در غیر اینصورت این شرط وجود ندارد

mohandese_hiclass
پنج شنبه 07 اردیبهشت 1385, 00:17 صبح
می تونید از همبندی استفاده کنین
یعنی اینکه یه آرایه بگیرین که اندازش تعداد گره های گرافتون باشه،
مقدار اولیه کل آرایه رو صفر میدین
حالا به اولین گره که می رسین اونو یکی اضافه می کنین
حالا واسه گره بعدی نگاه می کنید که اگه گره فعلی به قبلی وصله،همون عدد قبلی رو بهش میدین اما اگه وصل نیست یه عدد متمایز دیگه میدید
واسه همه گره ها این کار رو می کنید
در آخر اگر فقط در عناصر آرایه فقط دو دسته عدد داشتین(مثلا 1و1و1و2و2و1و1) این گراف دو بخشیه؛ در غیر اینصورت این شرط وجود ندارد
البته فکر کنم این الگوریتم واسه گراف جهتدار کار نکنه چون ممکنه یک گره داشته باشی که بهش فقط یال وارد می شه !!!!!

Mega7000
پنج شنبه 07 اردیبهشت 1385, 16:59 عصر
برای حالتی که گراف جهت دار باشه، چه راه حلی رو باید پیش گرفت؟

mohandese_hiclass
جمعه 08 اردیبهشت 1385, 10:42 صبح
روشهای اشاره شده در بالا واسه گراف جهت دار هم جواب میده