تالار گفتمان مانشت
سوال از درخت - نسخه‌ی قابل چاپ

سوال از درخت - zeinab - 13 آذر ۱۳۹۱ ۱۱:۴۴ ب.ظ

به نظرتون این جملات اشتباه نیستند؟؟!!
در هر درخت که تعداد رئوس بزرگتر مساوی ۲ است، حداقل دارای ۲ برگ خواهد بود!!!!!

در هر درخت که تعداد رئوس بزرگتر مساوی ۲ است، حداقل ۲ راس آویزان یعنی راس با درجه یک، وجود دارد!!!!!

تشکر

سوال از درخت - Jooybari - 13 آذر ۱۳۹۱ ۱۱:۵۹ ب.ظ

سلام. درستن. اگه خیلی ساده بگم درخت دور نداره. پس برای تعداد رئوس یشتر از ۱ اگه از یه یال به دوسمت حرکت کنیم حتماً حداقل به دو راس پایانی میرسیم. با فرمول هم قابل اثباته.

سوال از درخت - Jooybari - 14 آذر ۱۳۹۱ ۰۴:۲۲ ق.ظ

تعریف درخت رو از روی درایه های ماتریسش داریم. درخت گراف ساده ایه که دور نداره و همبنده و برگ راسی که توی سطرش فقط یک درایه ۱ داریم. اگه قرار باشه درخت ریشه داشته باشه، بحث روی درختها و گرافهای جهتدار میشه.

RE: سوال از درخت - mahsa.tsi - 15 آذر ۱۳۹۱ ۱۲:۳۶ ق.ظ

(۱۳ آذر ۱۳۹۱ ۱۱:۴۴ ب.ظ)zeinab نوشته شده توسط:  به نظرتون این جملات اشتباه نیستند؟؟!!
در هر درخت که تعداد رئوس بزرگتر مساوی ۲ است، حداقل دارای ۲ برگ خواهد بود!!!!!

در هر درخت که تعداد رئوس بزرگتر مساوی ۲ است، حداقل ۲ راس آویزان یعنی راس با درجه یک، وجود دارد!!!!!

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

سوال از درخت - m_sardaari - 15 آذر ۱۳۹۱ ۱۰:۳۶ ق.ظ

دوستان اگه درخت ما مورب چپ یا راست باشه با هر تعداد راُس حداقل تعداد برگ میشه یکی.
و حداقل تعداد راُس آویزان میشه به تعداد رآس ها

به نظرم اون جملات فقط برای درخت کامل صدق میکنه
درسته ؟

سوال از درخت - Jooybari - 15 آذر ۱۳۹۱ ۰۲:۰۹ ب.ظ

"درخت کامل"؟ چیزی که شما درخت مورب یا درخت ریشه دار معرفی میکنید درخت جهتداره. بحث ما روی درختهای سادست. اگه هون درخت جهتدار و ریشه دار رو بدون جهتش کنید ریشه هم به برگ تبدیل میشه. اونوقت همون دوتا برگ رو داریم.

RE: سوال از درخت - zeinab - 15 آذر ۱۳۹۱ ۰۴:۴۸ ب.ظ

(۱۳ آذر ۱۳۹۱ ۱۱:۵۹ ب.ظ)Jooybari نوشته شده توسط:  سلام. درستن. اگه خیلی ساده بگم درخت دور نداره. پس برای تعداد رئوس یشتر از ۱ اگه از یه یال به دوسمت حرکت کنیم حتماً حداقل به دو راس پایانی میرسیم. با فرمول هم قابل اثباته.

من سوالی که برام پیش اومده اینه که وقتی درخت ۲ راس داشته باشه، فقط یک برگ داره. درسته؟؟
پس در این جمله مساوی رو نباید داشته باشیم!!! در هر درخت که تعداد رئوس بزرگتر مساوی ۲ است، حداقل دارای ۲ برگ خواهد بود
وقتی میگیم درخت، منظور درخت جهت دار است دیگه!!

سوال از درخت - Jooybari - 16 آذر ۱۳۹۱ ۰۶:۵۲ ق.ظ

منظور درخت سادست. به مرجعی که این نکته رو ازش ذکر کردید یه نگاه بندازید. اگه این نکته توی درخت دودویی و هیپ و ... بود نکته اشتباهه. اگه توی درخت کمینه و یا مباحث کتابهای گسسته بود به احتمال زیاد سادست.

سوال از درخت - m_sardaari - 16 آذر ۱۳۹۱ ۱۲:۱۰ ب.ظ

ممنون بابت پاسخ.
لطف میکنین تعریف درخت ساده با ویژگی هاشو بگین.
من تو هر کتابی که خوندم فقط درخت ریشه دار و جهت دار رو دیدم .
راستش گیج شدم احه اگه جهت درخت حذف بشه میشه گراف بدون دور.

سوال از درخت - Jooybari - 16 آذر ۱۳۹۱ ۰۱:۴۷ ب.ظ

دقیقاً؛ درخت همون گراف همبند بدون دوره. درخت با n راس، n-1 یال داره. چون اگه تعداد یالهاش کمتر باشه همبند نیست و اگه قرار باشه بیشتر باشه یا ساده نیست و یا دور داره. درخت های پوشای مینیمم نمونه ای از درخت های ساده هستن. درکل مسائلی از درخت که بحث روی مجاورت باشه (بحث روی فرزند نباشه) و یا ساده سازی گراف ساده بفرم درخت باشه، از درخت ساده استفاده میشه.