پیچیدگی یافتن وزن درخت پوشای کمینه در یک گراف همبند جهت دار و بدون دور گراف G کدام است ؟
v
v+eloge
e+vlgv
۱
پارسه پاسخ داده گزینه ۱ یعنی v
ولی در گراف ممکنه دور بدون جهت داشته باشه و در این صورت یال عرضی هم داشته باشه بازم گزینه ۱ میشه ؟
سوال گفته گراف جهت دار و بدون دور
چطوری میشه دور داشته باشه؟!
درخت میشه دیگه.
گراف جهتدار و بدون دور یعنی اینکه تو MST باید همه ی گرهها باشن و یک پیمایش روی درخت اولیه مارو به جواب میرسونه.
(۲۷ دى ۱۳۹۳ ۰۹:۲۷ ق.ظ)ziba.O نوشته شده توسط: گراف جهتدار و بدون دور یعنی اینکه تو MST باید همه ی گرهها باشن و یک پیمایش روی درخت اولیه مارو به جواب میرسونه.آخه من تو کتاب قدسی دیدم که DAG میتونه دور بدون جهت داشته باشه و یال عرضی هم ممکنه داشته باشه
یعنی ممکنه گراف یال های بیشتر از درخت هم داشته باشه ولی ما میتونیم اونو در o(v
mst رو بدست بیاریم؟
ممنون
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.