درخت پوشای کمینه برای گراف همبند،جهت دار و بدون دور آیا یکتاست؟ این سوال پارسه هست و گفته این خودش درخا هست پس یکتاست تو این جور سوالا بدون دور یعنی بدون دور جهت دار یا کلن بدون هر گونه دوری ؟؟
یک سوالم پیوست کردم جوابش گزینه ی هست ولی من متوجهش نمیشم
وقتی گراف همبند و فاقد دور باشه میشه درخت...و درخت پوشا هم یکتا میشه.
سوال دوم جوابش گزینه ۴ هست؟
(۲۲ بهمن ۱۳۹۲ ۱۲:۲۳ ب.ظ)fulgent نوشته شده توسط: وقتی گراف همبند و فاقد دور باشه میشه درخت...و درخت پوشا هم یکتا میشه.
سوال دوم جوابش گزینه ۴ هست؟
در مورد سوال اول مشکل اینه که گفته جهت دار هست خب میشه گرافی داشت که دور جهت دار نداشته باشه ولی درخت نباشه
سوال دوم هم گفته به نوعی مرتب سازی هست و جواب گزینه یک هست
(۲۲ بهمن ۱۳۹۲ ۱۲:۲۹ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۲:۲۳ ب.ظ)fulgent نوشته شده توسط: وقتی گراف همبند و فاقد دور باشه میشه درخت...و درخت پوشا هم یکتا میشه.
سوال دوم جوابش گزینه ۴ هست؟
در مورد سوال اول مشکل اینه که گفته جهت دار هست خب میشه گرافی داشت که دور جهت دار نداشته باشه ولی درخت نباشه
سوال دوم هم گفته به نوعی مرتب سازی هست و جواب گزینه یک هست
دیگر دوستان نظر بدهند.
(۲۲ بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)zahra2012 نوشته شده توسط: درخت پوشای کمینه برای گراف همبند،جهت دار و بدون دور آیا یکتاست؟ این سوال پارسه هست و گفته این خودش درخا هست پس یکتاست تو این جور سوالا بدون دور یعنی بدون دور جهت دار یا کلن بدون هر گونه دوری ؟؟من کاری به اون سوال ضمیمه ندارم اما در مورد نکته اول یه چیزایی میگم
یک سوالم پیوست کردم جوابش گزینه ی هست ولی من متوجهش نمیشم
درخت پوشای کمینه برای گراف همبند جهتدار و بدون دور یکتا نیست. چون ممکنه دو یال یکسان داشته باشه
الگوریتم های کراسکال و پریم روی گراف جهتدار کار نمیکنند و جواب غلط میدن
مثل این مورد
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
پس درخت پوشای کمینه باید از یه الگوریتم دیگه ای غیر از کراسکال و پریم محاسبه بشه که اگر تو همین شکل که گذاشتم شما فرض کنید یالی که وزن ۶ داشت بشه وزن ۴/ اون وقت دو تا درخت پوشای کمینه داریم.
(۲۲ بهمن ۱۳۹۲ ۱۲:۳۱ ب.ظ)fulgent نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۲:۲۹ ب.ظ)zahra2012 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۲:۲۳ ب.ظ)fulgent نوشته شده توسط: وقتی گراف همبند و فاقد دور باشه میشه درخت...و درخت پوشا هم یکتا میشه.
سوال دوم جوابش گزینه ۴ هست؟
در مورد سوال اول مشکل اینه که گفته جهت دار هست خب میشه گرافی داشت که دور جهت دار نداشته باشه ولی درخت نباشه
سوال دوم هم گفته به نوعی مرتب سازی هست و جواب گزینه یک هست
دیگر دوستان نظر بدهند.
ممنون وقت گذاشتین
این سوال از نطفه غلطه، چون درخت پوشا واسه گراف جهت دار نداریم
(۲۲ بهمن ۱۳۹۲ ۰۱:۰۵ ب.ظ)Riemann نوشته شده توسط: این سوال از نطفه غلطه، چون درخت پوشا واسه گراف جهت دار نداریم
پس این چی میگه:
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می توان از الگوریتم‌های متفاوتی استفاده نمود.سه الگوریتم معروف پیدا کردن درخت پوشای کمینه عبارتند از : الگوریتم کروسکال الگوریتم پریم الگوریتم سولین
منبع : ویکی پدیا
(۲۲ بهمن ۱۳۹۲ ۱۲:۴۰ ب.ظ)masoud67 نوشته شده توسط:(22 بهمن ۱۳۹۲ ۱۱:۵۴ ق.ظ)zahra2012 نوشته شده توسط: درخت پوشای کمینه برای گراف همبند،جهت دار و بدون دور آیا یکتاست؟ این سوال پارسه هست و گفته این خودش درخا هست پس یکتاست تو این جور سوالا بدون دور یعنی بدون دور جهت دار یا کلن بدون هر گونه دوری ؟؟من کاری به اون سوال ضمیمه ندارم اما در مورد نکته اول یه چیزایی میگم
یک سوالم پیوست کردم جوابش گزینه ی هست ولی من متوجهش نمیشم
درخت پوشای کمینه برای گراف همبند جهتدار و بدون دور یکتا نیست. چون ممکنه دو یال یکسان داشته باشه
الگوریتم های کراسکال و پریم روی گراف جهتدار کار نمیکنند و جواب غلط میدن
مثل این مورد
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
پس درخت پوشای کمینه باید از یه الگوریتم دیگه ای غیر از کراسکال و پریم محاسبه بشه که اگر تو همین شکل که گذاشتم شما فرض کنید یالی که وزن ۶ داشت بشه وزن ۴/ اون وقت دو تا درخت پوشای کمینه داریم.
درسته منم سر جلسه آزمون همچین مثالی زدم و ردش کردم ولی دیدم تو جواب نوشته که چون گفته بدون دور پس خودش درخته و یکتاست که طاهرا اشتباه کرده
(۲۲ بهمن ۱۳۹۲ ۰۱:۰۵ ب.ظ)Riemann نوشته شده توسط: این سوال از نطفه غلطه، چون درخت پوشا واسه گراف جهت دار نداریم
منم همچین چیزی رو توی کتاب قدسی دیدم ولی باز جاهای دیگه دیدم حتی فکر کنم خود قدسی باز جهت دارم درخت پوشا براش داشت
(۲۲ بهمن ۱۳۹۲ ۰۱:۰۹ ب.ظ)fulgent نوشته شده توسط:(22 بهمن ۱۳۹۲ ۰۱:۰۵ ب.ظ)Riemann نوشته شده توسط: این سوال از نطفه غلطه، چون درخت پوشا واسه گراف جهت دار نداریم
پس این چی میگه:
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل می توان از الگوریتم‌های متفاوتی استفاده نمود.سه الگوریتم معروف پیدا کردن درخت پوشای کمینه عبارتند از : الگوریتم کروسکال الگوریتم پریم الگوریتم سولین
منبع : ویکی پدیا
For directed graphs, the minimum spanning tree problem is called the Arborescence problem and can be solved in quadratic time using the Chu–Liu/Edmonds algorithm.
منبع : ویکی پدیای انگلیسی