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

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

+2 امتیاز
سلام

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

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

در مورد عکس جمله اینطور فهمیدم که  اگر گراف وزن دار با وزن متمایز داشته باشیم درخت فراگیر کمینه اش یکتا نیست
سوال شده آبان 18, 1393  بوسیله ی Pakniat (امتیاز 247)   9 21 32

1 پاسخ

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

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

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

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

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

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

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

 

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

پاسخ داده شده آبان 19, 1393 بوسیله ی BlueBlade (امتیاز 15,315)   15 18 89
انتخاب شد آبان 19, 1393 بوسیله ی Pakniat
ممنون

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

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