درستی یا نادرستی یک عبارت در مورد درخت فراگیر کمینه - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۲۰ نفر آنلاین
۲ عضو و ۱۱۸ مهمان در سایت حاضرند

درستی یا نادرستی یک عبارت در مورد درخت فراگیر کمینه

+2 امتیاز
46 بازدید
سلام

در مورد درستی عبارت زیر شک دارم :

درخت فراگیر کمینه برای یک گراف وزن دار با وزن های متمایز یک تاست .اما عکس آن درست نیست !

در مورد عکس جمله اینطور فهمیدم که  اگر گراف وزن دار با وزن متمایز داشته باشیم درخت فراگیر کمینه اش یکتا نیست
سوال شده آبان 18, 1393  بوسیله ی Pakniat (امتیاز 382)   1 4 24

1 پاسخ

+1 امتیاز
 
بهترین پاسخ

عکس جمله رو اشتباه فهمیدید.

p--> q   ----aks---> q-->p

منظور از عکس این بوده که اگر  درخت کمینه یکنا باشه ورن ها هم  متمایز هستند . (که درست نیست و میشه مثال نقض پیدا کرد )

ساده ترین مثال نقض فکر کنم این باشه :

    5      5
A------B------C

داخل گراف بالا درخت کمینه یکتاست ولی وزن ها متمایز نیستند .

 

برای اثبات درست بودن خود عبارت هم میتونید از برهان خلف استفاده کنید .(اثبات این جا هست )

پاسخ داده شده آبان 19, 1393 بوسیله ی BlueBlade (امتیاز 15,712)   13 16 85
ممنون

یک سوال داشتم خارج از موضوع این تاپیک :

جریان ماکزیمم در گراف جز سرفصل های دوره لیسانس هست یا خیر ؟
آره  همه ی مطالب کتاب CLRS جزو سرفصل های لیسانس حساب میشن .
...