صفحه‌ها: ۱ ۲
یه نفر لطف کنه روش تشریحی برای بدست آوردن تعداد درخت های پوشای تصویر سمت چپ و تعداد تطابق های کامل تصویر سمت راست ارئه دهید؟ با تشکر
اون که خیلی حالت داره.
شما باید تعداد گره‌ها رو در نظر بگیرید (n)تعداد یالها باید n-1 باشه حالتهای مختلف حذف یال تا رسیدن به n-1 یال درختهای پوشای مختلف رو میسازه.
مثلا توی شکل سمت چپ شما ۵ گره دارید پس باید ۴ یال باقی بمونه پس میتونید ۳ یال رو حذف کنید مثلا ۳ یال قاعده مثلث یا هر ۳ یال دیگه که حذف کنید یک درخت پوشا رو به شما میده.
* من یادم رفته حالتهایی که منجر به جدا شدن کامل یک نود از بقیه میشه رو در نظر بگیرم یعنی از تعداد حالات کسر کنم.توضیحاتی که آقای دکتر دادن کامل تره.
در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یالهاش حذف کنید و حالا از بین یالهای باقیمانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یالهای باقیمانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۱-۵-۰ که برابر می‍شود با ۲۳
در مورد تطابق کامل لطفاً تعریف تطابق کامل رو ارائه بدین( یا معادل انگلیسیش رو بنویسید)
تطابق کامل =complete match
برای بدست آوردن تطابق های کامل شکل سمت راست باید از راه بازگشتی رفت
فرمولش میشه ( T(n)=T(n-1)+T(n-2
اینجا باید( T(6 رو حساب کنید به تعداد ستونها
توضیحشم اینه ستونها رو از ۱ تا ۶ شماره گذاری میکنیم
در مرحله اول ۲ حالت داریم:۱-ستون شماره۱ رو انتخاب کنیم که در این صورت یک ستون حذف میشه و میشه( T(n-1
حالت۲:به جای ستون ,سطر رو انتخاب میکنیم که در این حالت با انتخاب سطر ۲ ستون از کل ستونها کم میشه و باید( T(n-2 رو حساب کرد
حالا منم یک سوال دارم که نمیتونم از این راه حلش کنم
تعداد تطابق های کامل مکعب چند تا میشه؟
(۰۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)admin نوشته شده توسط: در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یالهاش حذف کنید و حالا از بین یالهای باقیمانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یالهای باقیمانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۵-۰ که برابر می‍شود با ۲۴
در مورد تطابق کامل لطفاً تعریف تطابق کامل رو ارائه بدین( یا معادل انگلیسیش رو بنویسید)
ولی پس چرا جواب این تست توی کتاب گسسته پوران ۲۱ شده؟
(۰۸ دى ۱۳۸۹ ۰۱:۵۳ ق.ظ)afagh1389 نوشته شده توسط: میتونید به این صورت هم بگید که ما باید ۳ یال رو حذف کنیم فقط نباید کل یالهای یک نود رو حذف کرد پس حالاتی که این کل یالهای یک نود رو حذف کردیم حساب میکنیم مثلا از نودی که دو یال داشته دو یالش رو برداشتیم پس یک یال از ۵ یال باقیمانده انتخاب کردیم که جواب آخر با جواب آقای دکتر یکی میشه (البته ایشون توی تفریق آخر یه یک رو جا انداختن)
[tex]\binom{7}{3}-(2*\binom{5}{1}+2*\binom{4}{0})=35-12=23[/tex]
من خودمم ۲۳ درآوردم ولی کلید ۲۱ هست
نمی دونم چرا؟
من بابت اشتباهم معذرت می‍خوام، فکر میکنم یه دونه از ۴ از ۴ها رو توی جواب آخری که گذاشتم حساب نکرده بودم که میشه همون ۲۳ که شما فرمودین.
کلید هم حتماً اشتباه کرده
من این سوالها را یه طوری دیگه حل میکنم مثلا در سوال علوم کامپیوتر ۸۹ یه شکل داده بود (دو تا لوزی و در کنار هر لوزی یه مثلث قرار گرفته بود)خب دو تا مثلث که گراف کاملند جواب میشه ۳×۳=۹ حالا دو تا لوزی باقی میمونه این دو لوزی بسته هستند و تعداد مجموع یالهای هر دو ۸ تا میباشد و چون ۲ تا ناحیه بسته داریم ۲×۸=۱۶ و جواب آخر ۹×۱۶= ۱۴۴
حالا اگه سوال قبل را هم این طوری حل کنیم جواب ۲۱ میشه گراف کاملی که انتخاب میکنیم نباید منجر به ناحیه غیر بسته بشه پس شکل در کل ۷ یال داره با ۳ ناحیه و جواب میشه ۳×۷=۲۱ چند تا سوال دیگه هم با همین روش حل کردم درست بود نمیدونم راه حلم درسته یا نه اگه اشتباهه بگید
(۰۹ دى ۱۳۸۹ ۰۹:۴۲ ق.ظ)delta نوشته شده توسط: من این سوالها را یه طوری دیگه حل میکنم مثلا در سوال علوم کامپیوتر ۸۹ یه شکل داده بود (دو تا لوزی و در کنار هر لوزی یه مثلث قرار گرفته بود)خب دو تا مثلث که گراف کاملند جواب میشه ۳×۳=۹ حالا دو تا لوزی باقی میمونه این دو لوزی بسته هستند و تعداد مجموع یالهای هر دو ۸ تا میباشد و چون ۲ تا ناحیه بسته داریم ۲×۸=۱۶ و جواب آخر ۹×۱۶= ۱۴۴
حالا اگه سوال قبل را هم این طوری حل کنیم جواب ۲۱ میشه گراف کاملی که انتخاب میکنیم نباید منجر به ناحیه غیر بسته بشه پس شکل در کل ۷ یال داره با ۳ ناحیه و جواب میشه ۳×۷=۲۱ چند تا سوال دیگه هم با همین روش حل کردم درست بود نمیدونم راه حلم درسته یا نه اگه اشتباهه بگید
اگه گراف دارای زیر گراف همبند باشه از فرمول n^n-2 برای هر مولفه میشه کل درختهای پوشا رو حساب کرد
ولی این شکل رو نمیشه به مولفه های کامل مجزا تقسیم کرد چون یالها مشترکند
در مورد تعداد تطابق های کامل مکعب، همانطور که می دونید مکعب یه گراف دوبخشی کامل است که هر بخش چهار گره در اون اشت و گراف کامل دوبخشیK n,n برابر!n است پس جواب برابر!۴=۲۴ میشه.
روش دوم:شما در مرحله اول ۸ انتخاب برای تطابق بین دو گره در مکعب دارید پس از مرحله اول شما دو گره مربوطه با تمام یالهای متصل به اون حذف می کنید با این کار ما یه پله با دو ستون داریم که جوابش ۳=(۲)T ، پس جواب کلی میشه ۸*۳=۲۴
با تشکر از همه آقایون از اینکه کمک کردند
با تشکر از همه آقایون!!!!!؟ پس خانمها چی می‍شن؟
(۰۹ دى ۱۳۸۹ ۰۲:۵۵ ب.ظ)admin نوشته شده توسط: با تشکر از همه آقایون!!!!!؟ پس خانمها چی می‍شن؟خانمها رفتن گل بچینن.
سلام جواب پوران درسته:
تقسیم مساله به ۳ حالت:
۱- دو یال مشترک هیچکدام انتخاب نشوند یعنی شکل ۱ که در این حالت باید از بین ۵ یال ۴ یال را انتخاب کنیم تا درخت فراگیر ایجاد شود.( ۵ حالت)
۲- یک یال از دو یال مشترک حتما انتخاب شود. یعنی شکل ۲/
که از سمت چپ به ۲ طریق و از سمت راست به ۳ طریق میتوان یال انتخاب کرد تا درخت فراگیر ایجاد شود.(۶ حالت)
چون همین حالات را برای یال مشترک دیگر داریم پس
۲*۶=۱۲ حالت)۳- هر دو یال مشترک انتخاب شوند یعنی شکل ۳/
که ۲*۱*۲= ۴ حالت دارد.
پس در مجموع سه حالت: ۵+۱۲+۴ = ۲۱ حالت.
بالاخره جواب ۲۱ میشه یا ۲۳؟
(۰۹ دى ۱۳۸۹ ۰۲:۰۸ ب.ظ)امیدوار نوشته شده توسط: در مورد تعداد تطابق های کامل مکعب، همانطور که می دونید مکعب یه گراف دوبخشی کامل است که هر بخش چهار گره در اون اشت و گراف کامل دوبخشیK n,n برابر!n است پس جواب برابر!۴=۲۴ میشه.
مکعب گراف ۲ بخشی کامل نیست.