سوال ۸۰ کنکور ارشد علوم کامپیوتر ۱۴۰۱
اهمیت
۰/۵
بهترین زمان برای تعیین دوبخشی بودن و نبودن یک گراف با n رأس و e یال از چه مرتبه زمانی است؟ (گراف دوبخشی یعنی گرافی که بتوان رأس‌های آن را به دو بخش A و B افراز کرد بطوریکه هر یال G یک سر در A و یک سر در B داشته باشد.)
پاسخ صحیح: گزینهٔ A —
پاسخ تشریحی
A graph is bipartite iff it has no odd-length cycle, equivalently iff its vertices can be properly 2-colored. …
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#bipartite#graph-traversal#bfs#two-coloring#time-complexity#graph-algorithms