صفحه‌ها: ۱ ۲
ببخشید من اشتباه کردم یه مکعب فقط یک گراف دو بخشی است ولی کامل نیست با توجه به این موضوع ما اگر هر یک از گره های مکعب رو انتخاب کنیم به ۳ طریق می تونیم با گره های متصل به اون تطبیق انجام بدیم پس از این مرحله دو گره و تمام یالهای متصل به اون رو حذف می کنیم که در اینجا یه پله دو ستونی بوجود میاد که تعداد تطابق های آن هم برابر ۳ =(۲)T ،که در کل میشه ۳*۳=۹ حالت کل تطابق‌ها ست.
من فکر میکنم با روشی که دکتر گفتن نمی شه همیشه تعداد درختهای پوشا رو درست بدست آورد.چرا که در مورد گراف های کامل صدق نمی کنه .(البته با احترام به روش ایشون)
پس چطوری میشه یه راه کلی پیدا کرد؟
مثلا این گرافها رو با توجه به گراف کامل باید حل کرد.
![[تصویر: 12941232871.jpg]](http://www.parsimg.com/uploads/12941232871.jpg)
میشه ۱ روش کلی برای پیدا کردن تعداد تطابق کامل در گراف دوبخشی غیرکامل بفرمایید؟
(۰۹ دى ۱۳۸۹ ۱۲:۱۶ ب.ظ)leilast نوشته شده توسط:(09 دى ۱۳۸۹ ۰۹:۴۲ ق.ظ)delta نوشته شده توسط: من این سوالها را یه طوری دیگه حل میکنم مثلا در سوال علوم کامپیوتر ۸۹ یه شکل داده بود (دو تا لوزی و در کنار هر لوزی یه مثلث قرار گرفته بود)خب دو تا مثلث که گراف کاملند جواب میشه ۳×۳=۹ حالا دو تا لوزی باقی میمونه این دو لوزی بسته هستند و تعداد مجموع یالهای هر دو ۸ تا میباشد و چون ۲ تا ناحیه بسته داریم ۲×۸=۱۶ و جواب آخر ۹×۱۶= ۱۴۴
حالا اگه سوال قبل را هم این طوری حل کنیم جواب ۲۱ میشه گراف کاملی که انتخاب میکنیم نباید منجر به ناحیه غیر بسته بشه پس شکل در کل ۷ یال داره با ۳ ناحیه و جواب میشه ۳×۷=۲۱ چند تا سوال دیگه هم با همین روش حل کردم درست بود نمیدونم راه حلم درسته یا نه اگه اشتباهه بگید
اگه گراف دارای زیر گراف همبند باشه از فرمول n^n-2 برای هر مولفه میشه کل درختهای پوشا رو حساب کرد
ولی این شکل رو نمیشه به مولفه های کامل مجزا تقسیم کرد چون یالها مشترکند
توی کتاب مقسمی جواب سوال رو همون ۲۱ گفته و اینجوری رفته
[tex]n^{n-2} ---->3^{1}*3^{1}*3^{1}=27[/tex]
بعد گفته ۶ تا از این حالتها منجر به ایجاد حلقه میشوند ۲۷-۶=۲۱!
کسی نظری نداره!!!!
جوابایی که دوستان دادنو خلاصه کردم:
عدد ۲۳
(۰۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)admin نوشته شده توسط: در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یالهاش حذف کنید و حالا از بین یالهای باقیمانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یالهای باقیمانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۱-۵-۰ که برابر می‍شود با ۲۳
(۰۸ دى ۱۳۸۹ ۰۱:۵۳ ق.ظ)A.A نوشته شده توسط: میتونید به این صورت هم بگید که ما باید ۳ یال رو حذف کنیم فقط نباید کل یالهای یک نود رو حذف کرد پس حالاتی که این کل یالهای یک نود رو حذف کردیم حساب میکنیم مثلا از نودی که دو یال داشته دو یالش رو برداشتیم پس یک یال از ۵ یال باقیمانده انتخاب کردیم که جواب آخر با جواب آقای دکتر یکی میشه (البته ایشون توی تفریق آخر یه یک رو جا انداختن)
[tex]\binom{7}{3}-(2*\binom{5}{1}+2*\binom{4}{0})=35-12=23[/tex]
عدد ۲۱:
(۱۲ دى ۱۳۸۹ ۱۱:۱۸ ب.ظ)moji67 نوشته شده توسط: سلام جواب پوران درسته:
تقسیم مساله به ۳ حالت:
۱- دو یال مشترک هیچکدام انتخاب نشوند یعنی شکل ۱ که در این حالت باید از بین ۵ یال ۴ یال را انتخاب کنیم تا درخت فراگیر ایجاد شود.( ۵ حالت)
۲- یک یال از دو یال مشترک حتما انتخاب شود. یعنی شکل ۲/
که از سمت چپ به ۲ طریق و از سمت راست به ۳ طریق میتوان یال انتخاب کرد تا درخت فراگیر ایجاد شود.(۶ حالت)
چون همین حالات را برای یال مشترک دیگر داریم پس۲*۶=۱۲ حالت)
۳- هر دو یال مشترک انتخاب شوند یعنی شکل ۳/
که ۲*۱*۲= ۴ حالت دارد.
پس در مجموع سه حالت: ۵+۱۲+۴ = ۲۱ حالت.
(۰۲ بهمن ۱۳۸۹ ۰۱:۰۸ ق.ظ)A.A نوشته شده توسط: توی کتاب مقسمی جواب سوال رو همون ۲۱ گفته و اینجوری رفته
[tex]n^{n-2} ---->3^{1}*3^{1}*3^{1}=27[/tex]
بعد گفته ۶ تا از این حالتها منجر به ایجاد حلقه میشوند ۲۷-۶=۲۱!
اینم جواب خودم با استفاده از قضیه زیر که در جلد ۳ گریمالدی گفته شده:
و میشه ۲۱
If G is a multigraph and e is an edge of G, then the number t(G) of spanning trees of G satisfies the deletion-contraction recurrence t(G)=t(G-e)+t(G/e), where G-e is the multigraph obtained by deleting e and G/e is the contraction of G by e, where multiple edges arising from this contraction are not deleted.
با توجه به شکل:
۲۱ =۴ + ۲*۲ + ۲*۲+ ۳*۳
سلام
با توجه به شکل بالا:اگه بگیم برا دوتا مثلث داریم:۳*۳=۹ و از اونجایی که دوتا یالشون مشترک با مثلث سومه پس:۹-۲=۷
حالا باید ۷ رو حالات مثلث سوم ضرب کرد یعنی ۳*۷=۲۱
(۰۷ دى ۱۳۸۹ ۰۴:۰۴ ب.ظ)leilast نوشته شده توسط: تطابق کامل =complete match
برای بدست آوردن تطابق های کامل شکل سمت راست باید از راه بازگشتی رفت
فرمولش میشه ( T(n)=T(n-1)+T(n-2
اینجا باید( T(6 رو حساب کنید به تعداد ستونها
توضیحشم اینه ستونها رو از ۱ تا ۶ شماره گذاری میکنیم
در مرحله اول ۲ حالت داریم:۱-ستون شماره۱ رو انتخاب کنیم که در این صورت یک ستون حذف میشه و میشه( T(n-1
حالت۲:به جای ستون ,سطر رو انتخاب میکنیم که در این حالت با انتخاب سطر ۲ ستون از کل ستونها کم میشه و باید( T(n-2 رو حساب کرد
حالا منم یک سوال دارم که نمیتونم از این راه حلش کنم
تعداد تطابق های کامل مکعب چند تا میشه؟
سلام
تعداد تطابق کامل مکعب n-منتظم(nبعدی) برابر است با : n ^2 (اِن به توان ۲ )
تعداد تطابق کامل گراف کامل K 2n برابر است با : [tex](2n)! / (2^n * n!)[/tex]
مثلا:گراف کامل K 8= K 2*4 و n=4 میباشد!
تعداد تطابق کامل گراف K n,n برابر است با : !n
چون یکی از دوستان در مورد اینکه کدام جواب درسته سوال کردن باید بگم که جواب همون ۲۱ میشه و راه حل آقای moji67 درسته.
اگه جواب ۲۱ میشه پس چرا جواب ۲۳ که جناب تنهایی دادن به عنوان پاسخ کامل انتخاب شده ؟