۲
subtitle
ارسال: #۱
سوال گراف IT 88
سلام
گراف بدون جهت [tex]G(V,E)[/tex] مفروض است.میخواهیم مشخص کنیم آیا گراف شامل حلقه است یا نه. کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
۱-[tex]O(|E|)[/tex]
۲-[tex]O(|V|*|E|)[/tex]
۳-[tex]O(|V|)[/tex]
۴-[tex]O(|V| |E|)[/tex]
من در اینجوری مسئله های یکم مشکل دارم و تحلیلم قوی نیست. اگه میشه یکی واسم تحلیل کنه سوالو.ممنون
گراف بدون جهت [tex]G(V,E)[/tex] مفروض است.میخواهیم مشخص کنیم آیا گراف شامل حلقه است یا نه. کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
۱-[tex]O(|E|)[/tex]
۲-[tex]O(|V|*|E|)[/tex]
۳-[tex]O(|V|)[/tex]
۴-[tex]O(|V| |E|)[/tex]
من در اینجوری مسئله های یکم مشکل دارم و تحلیلم قوی نیست. اگه میشه یکی واسم تحلیل کنه سوالو.ممنون
۱
ارسال: #۲
RE: سوال گراف IT 88
طبق قانون : درصورتی گراف بدون دور است که dfs آن یال پشتی ندهد
برای این سوال هم dfs انجام میدیم اگه یال پشتی داد یعنی دور داره و اگه نداد پس نداره
dfs هم در زمان خطی انجام میشه در زمان( O (v انجام میشه
برای این سوال هم dfs انجام میدیم اگه یال پشتی داد یعنی دور داره و اگه نداد پس نداره
dfs هم در زمان خطی انجام میشه در زمان( O (v انجام میشه
۱
ارسال: #۳
RE: سوال گراف IT 88
(۱۴ آذر ۱۳۹۲ ۰۸:۰۰ ب.ظ)tabassomesayna نوشته شده توسط: سلام
گراف بدون جهت [tex]G(V,E)[/tex] مفروض است.میخواهیم مشخص کنیم آیا گراف شامل حلقه است یا نه. کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
۱-[tex]O(|E|)[/tex]
۲-[tex]O(|V|*|E|)[/tex]
۳-[tex]O(|V|)[/tex]
۴-[tex]O(|V| |E|)[/tex]
من در اینجوری مسئله های یکم مشکل دارم و تحلیلم قوی نیست. اگه میشه یکی واسم تحلیل کنه سوالو.ممنون
برای تحلیل این مساله نیاز به دو گام است :
در گام اول : E>v-1 اگر اینگونه باشد ، قطعا در گراف دور داریم.
در گام دوم : اگر رابطه بالا صدق نکنه ، پس E کمتر یا مساوی V هست . بنابراین با بکارگیری DFS ، میتونیم به مرتیه(O ( V+E برسیم که چون E کوچکتر V هست پس میشه همون (O(V . علت به کارگیری DFS هم جناب ۲۰۱۳محمد توضیح دادند
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close