چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
گراف
چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
فکر نمیکنین که اینو باید تو قسمت الگوریتم مطرح میکردین؟
قفل مخفی تلگرام، واتس اپ و همه برنامه ها - قفل حرفه ای برای دستگاه اندرویدی شما - با امکان مخفی شدن و جلوگیری از Unisntall شدن
--آموزش ایجاد برنامه های چند زبانه در WPF
-BeRMOoDA File Encrypter-open source-using WPF, C# and MVVM Pattern
-نمونه برنامه ساده و کامل با الگوی MVVM برای کار با دیتابیس با استفاده از Entity Framework در WPF
-WPFMessageBox فارسی/انگلیسی - با قابلیت تغییر Skin
سلام
من منظور از گراف دو بخشی رو نمیدونم ولی اگر منظور گراف نا همبند باشه ناهمبند بودن یک گراف معادل اینه که از حداقل یکی از راس ها به حداقل یک راس دیگه مسیری وجود نداشته باشه. حالا اینو اگه بشه با ماتریس مجاورت حل کرد، جواب سوال شما هم در میاد.
ممنون علی
با الگوریتم Depth First Search اگه مجبور بشی بیش از یک بار تابع بازگشتی رو کال کنی یعنی گراف چند تکه هست.چه طور می تونیم از روی ماتریس مجاورت یک گراف دو بخشی بودن یا نبودن را تشخیص بدیم؟؟؟
You never know what you can do until you try
از روش بالا هم میشه می تونی از جستجوی سطحی هم استفاده کنی که پیاده شازیش راحتتره
می تونید از همبندی استفاده کنین
یعنی اینکه یه آرایه بگیرین که اندازش تعداد گره های گرافتون باشه،
مقدار اولیه کل آرایه رو صفر میدین
حالا به اولین گره که می رسین اونو یکی اضافه می کنین
حالا واسه گره بعدی نگاه می کنید که اگه گره فعلی به قبلی وصله،همون عدد قبلی رو بهش میدین اما اگه وصل نیست یه عدد متمایز دیگه میدید
واسه همه گره ها این کار رو می کنید
در آخر اگر فقط در عناصر آرایه فقط دو دسته عدد داشتین(مثلا 1و1و1و2و2و1و1) این گراف دو بخشیه؛ در غیر اینصورت این شرط وجود ندارد
البته فکر کنم این الگوریتم واسه گراف جهتدار کار نکنه چون ممکنه یک گره داشته باشی که بهش فقط یال وارد می شه !!!!!نوشته شده توسط Mega7000
برای حالتی که گراف جهت دار باشه، چه راه حلی رو باید پیش گرفت؟
روشهای اشاره شده در بالا واسه گراف جهت دار هم جواب میده
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول