سوال ۵۲هوش سال ۸۸ هست.
در مورد گزینه ۱باید d[v]<d[u] باشه اون علامت مساوی برای چیه؟
توی درختی که من برای خودم کشیدم تعداد Treeها از همه بیشتره!
برایEdge Cross هم رابطه باید d[v]<d[u] باشه؟
(۲۹ دى ۱۳۸۹ ۰۷:۰۸ ب.ظ)sepid نوشته شده توسط: توی درختی که من برای خودم کشیدم تعداد Treeها از همه بیشتره!این که Tree Edgeها چند تا باشه به تعداد راسها بستگی داره! (یکی کمتر از تعداد راس هاست) ممکنه کمتر باشه یا بیشتر!
(۲۹ دى ۱۳۸۹ ۰۷:۰۸ ب.ظ)sepid نوشته شده توسط: برایEdge Cross هم رابطه باید d[v]<d[u] باشه؟به نظرم [tex]d[v]\leq d[u] 1 \equiv d[v]< d[u][/tex]
سپید جان این فایل ضمیمه رو هم یه نگاه بنداز ممکنه کمکت کنه .
متشکرم از همه.
تو CLRS جوابش را یافتم.
اول اینکه گزینه ۳هم غلطه.یا مثال هم میشه فهمید پارسه هم گفته.
دوم اینکه مساوی گزینه ۱ به خاطر اینکه یالی که رو خودش حلقه داره Backهست.
(۲۹ دى ۱۳۸۹ ۰۸:۰۲ ب.ظ)۵۴m4n3h نوشته شده توسط:(29 دى ۱۳۸۹ ۰۷:۰۸ ب.ظ)sepid نوشته شده توسط: توی درختی که من برای خودم کشیدم تعداد Treeها از همه بیشتره!این که Tree Edgeها چند تا باشه به تعداد راسها بستگی داره! (یکی کمتر از تعداد راس هاست) ممکنه کمتر باشه یا بیشتر!
تعداد یالهای درختی یکی کمتراز تعداد راسها نیست!
در واقع به نظر من درخت فراگیر یک گراف تشکیل شده از تمام یالهای درختی بعلاوه بعضی یالهای تقاطعی یا همون Cross.
مثالش رو هم میتونید تو همون فایلی که parsaNA ضمیمه کردن ببینید.