چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
Printable View
چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
فکر نمیکنین که اینو باید تو قسمت الگوریتم مطرح میکردین؟
سلام
من منظور از گراف دو بخشی رو نمیدونم ولی اگر منظور گراف نا همبند باشه ناهمبند بودن یک گراف معادل اینه که از حداقل یکی از راس ها به حداقل یک راس دیگه مسیری وجود نداشته باشه. حالا اینو اگه بشه با ماتریس مجاورت حل کرد، جواب سوال شما هم در میاد.
ممنون علی
با الگوریتم Depth First Search اگه مجبور بشی بیش از یک بار تابع بازگشتی رو کال کنی یعنی گراف چند تکه هست.نقل قول:
چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
از روش بالا هم میشه می تونی از جستجوی سطحی هم استفاده کنی که پیاده شازیش راحتتره
می تونید از همبندی استفاده کنین
یعنی اینکه یه آرایه بگیرین که اندازش تعداد گره های گرافتون باشه،
مقدار اولیه کل آرایه رو صفر میدین
حالا به اولین گره که می رسین اونو یکی اضافه می کنین
حالا واسه گره بعدی نگاه می کنید که اگه گره فعلی به قبلی وصله،همون عدد قبلی رو بهش میدین اما اگه وصل نیست یه عدد متمایز دیگه میدید
واسه همه گره ها این کار رو می کنید
در آخر اگر فقط در عناصر آرایه فقط دو دسته عدد داشتین(مثلا 1و1و1و2و2و1و1) این گراف دو بخشیه؛ در غیر اینصورت این شرط وجود ندارد
البته فکر کنم این الگوریتم واسه گراف جهتدار کار نکنه چون ممکنه یک گره داشته باشی که بهش فقط یال وارد می شه !!!!!نقل قول:
نوشته شده توسط Mega7000
برای حالتی که گراف جهت دار باشه، چه راه حلی رو باید پیش گرفت؟
روشهای اشاره شده در بالا واسه گراف جهت دار هم جواب میده