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

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

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

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

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

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

تشکر

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

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

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

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

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

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

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