۰
subtitle
ارسال: #۱
سوال ۴۷ پارسه ۱۰۰ درصد دوم
پیچیدگی یافتن وزن درخت پوشای کمینه در یک گراف همبند جهت دار و بدون دور گراف G کدام است ؟
v
v+eloge
e+vlgv
۱
پارسه پاسخ داده گزینه ۱ یعنی v
ولی در گراف ممکنه دور بدون جهت داشته باشه و در این صورت یال عرضی هم داشته باشه بازم گزینه ۱ میشه ؟
v
v+eloge
e+vlgv
۱
پارسه پاسخ داده گزینه ۱ یعنی v
ولی در گراف ممکنه دور بدون جهت داشته باشه و در این صورت یال عرضی هم داشته باشه بازم گزینه ۱ میشه ؟
۰
ارسال: #۲
RE: سوال ۴۷ پارسه ۱۰۰ درصد دوم
سوال گفته گراف جهت دار و بدون دور
چطوری میشه دور داشته باشه؟!
درخت میشه دیگه.
چطوری میشه دور داشته باشه؟!
درخت میشه دیگه.
۰
ارسال: #۳
RE: سوال ۴۷ پارسه ۱۰۰ درصد دوم
گراف جهتدار و بدون دور یعنی اینکه تو MST باید همه ی گرهها باشن و یک پیمایش روی درخت اولیه مارو به جواب میرسونه.
ارسال: #۴
RE: سوال ۴۷ پارسه ۱۰۰ درصد دوم
(۲۷ دى ۱۳۹۳ ۰۹:۲۷ ق.ظ)ziba.O نوشته شده توسط: گراف جهتدار و بدون دور یعنی اینکه تو MST باید همه ی گرهها باشن و یک پیمایش روی درخت اولیه مارو به جواب میرسونه.آخه من تو کتاب قدسی دیدم که DAG میتونه دور بدون جهت داشته باشه و یال عرضی هم ممکنه داشته باشه
یعنی ممکنه گراف یال های بیشتر از درخت هم داشته باشه ولی ما میتونیم اونو در o(v
mst رو بدست بیاریم؟
ممنون
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close