سلام
صورت سوال این هست چند مورد رو میتونیم توی v+e در گراف بدون جهت وبی وزن باdfsب دست بیاریم که مورد اول بررسی دو بخشی بودن هست وجواب گفته که میشه این مورد روبا dfsب دست اورد مگه دو بخشی روباbfsنمیگفتیم؟هر دومیشه؟یا شرایط خاص داره؟
ممنون[/size]
(۳۰ اسفند ۱۳۹۵ ۱۰:۱۸ ق.ظ)mzha نوشته شده توسط: سلام
صورت سوال این هست چند مورد رو میتونیم توی v+e در گراف بدون جهت وبی وزن باdfsب دست بیاریم که مورد اول بررسی دو بخشی بودن هست وجواب گفته که میشه این مورد روبا dfsب دست اورد مگه دو بخشی روباbfsنمیگفتیم؟هر دومیشه؟یا شرایط خاص داره؟
ممنون[/size]
سلام
لطفاً صورت سؤال رو کامل بذارید. هر دو میشه:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
در تشخیص دو بخشی بودن از هر دوی bfs , dfs می توان استفاده کرد.
در دوبخشی می توان رئوس را به دوبخش تقسیم کردطوری که برای هر یال دو سر ان در دو بخش قرار می گیرد.در هر دو از این نکته که هر گرافی که عدد کروماتیک ان ۲ باشد دوبخشی است و برعکس استفاده می شود(در اصل برای اثبات نبود دور فرد استفاده می شود).یعنی در دوبخشی می توان رئوس را با دو رنگ رنگ امیزی کرد.
در bfs که به صورت سطح به سطح پیمایش می شود(استفاده از صف) از دو رنگ مثلا قرمز و ابی استفاده می کنیم ریشه را قرمز و فرزندان ان را ابی و بعد که فرزندان فرزندهای ریشه را پیمایش می کینم را دوباره ابی و ال اخر ...در dfs هم که در عمق حرکت می کنیم نودها را یک در میان قرمز و ابی می کنیم (البته توجه شود که هر نود یک بار رنگ می گیرد) بعد از اتمام پیمایش تمامی یال ها را بررسی می کنیم که دو راس هر یال دارای دو رنگ متفاوت باشند این الگورتیم در کل از مرتبه[tex]O(n+e)[/tex] البته با لیست و با مارتریس [tex]O(n^2)[/tex]
ممنون از پاسختون