زمان کنونی: ۲۴ آذر ۱۴۰۳, ۰۵:۰۶ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

تعداد درخت های پوشا و تعداد تطابق کامل

ارسال:
  

امیدوار پرسیده:

تعداد درخت های پوشا و تعداد تطابق کامل

یه نفر لطف کنه روش تشریحی برای بدست آوردن تعداد درخت های پوشای تصویر سمت چپ و تعداد تطابق های کامل تصویر سمت راست ارئه دهید؟ با تشکر


فایل‌(های) پیوست شده

۲
ارسال:
  

admin پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یال‍هاش حذف کنید و حالا از بین یال‍های باقی‍مانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یال‍های باقی‍مانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۱-۵-۰ که برابر می‍شود با ۲۳

در مورد تطابق کامل لطفاً تعریف تطابق کامل رو ارائه بدین( یا معادل انگلیسیش رو بنویسید)

ارسال:
  

leilast پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

(۰۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)admin نوشته شده توسط:  در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یال‍هاش حذف کنید و حالا از بین یال‍های باقی‍مانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یال‍های باقی‍مانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۵-۰ که برابر می‍شود با ۲۴

در مورد تطابق کامل لطفاً تعریف تطابق کامل رو ارائه بدین( یا معادل انگلیسیش رو بنویسید)

ولی پس چرا جواب این تست توی کتاب گسسته پوران ۲۱ شده؟
یافتن تمامی ارسال‌های این کاربر

۱
ارسال:
  

امیدوار پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

در مورد تعداد تطابق های کامل مکعب، همانطور که می دونید مکعب یه گراف دوبخشی کامل است که هر بخش چهار گره در اون اشت و گراف کامل دوبخشیK n,n برابر!n است پس جواب برابر!۴=۲۴ میشه.
روش دوم:شما در مرحله اول ۸ انتخاب برای تطابق بین دو گره در مکعب دارید پس از مرحله اول شما دو گره مربوطه با تمام یالهای متصل به اون حذف می کنید با این کار ما یه پله با دو ستون داریم که جوابش ۳=(۲)T ‌، پس جواب کلی میشه ۸*۳=۲۴
با تشکر از همه آقایون از اینکه کمک کردند

ارسال:
  

ROZA پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

(۰۹ دى ۱۳۸۹ ۰۲:۰۸ ب.ظ)امیدوار نوشته شده توسط:  در مورد تعداد تطابق های کامل مکعب، همانطور که می دونید مکعب یه گراف دوبخشی کامل است که هر بخش چهار گره در اون اشت و گراف کامل دوبخشیK n,n برابر!n است پس جواب برابر!۴=۲۴ میشه.

مکعب گراف ۲ بخشی کامل نیست.
یافتن تمامی ارسال‌های این کاربر

۱
ارسال:
  

امیدوار پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

ببخشید من اشتباه کردم یه مکعب فقط یک گراف دو بخشی است ولی کامل نیست با توجه به این موضوع ما اگر هر یک از گره های مکعب رو انتخاب کنیم به ۳ طریق می تونیم با گره های متصل به اون تطبیق انجام بدیم پس از این مرحله دو گره و تمام یالهای متصل به اون رو حذف می کنیم که در اینجا یه پله دو ستونی بوجود میاد که تعداد تطابق های آن هم برابر ۳ =(۲)T ،که در کل میشه ۳*۳=۹ حالت کل تطابق‌ها ست.

۱
ارسال:
  

M@A پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

سلام
با توجه به شکل بالا:اگه بگیم برا دوتا مثلث داریم:۳*۳=۹ و از اونجایی که دوتا یالشون مشترک با مثلث سومه پس:۹-۲=۷
حالا باید ۷ رو حالات مثلث سوم ضرب کرد یعنی ۳*۷=۲۱

(۰۷ دى ۱۳۸۹ ۰۴:۰۴ ب.ظ)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

۱
ارسال:
  

csharpisatechnology پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

اگه جواب ۲۱ میشه پس چرا جواب ۲۳ که جناب تنهایی دادن به عنوان پاسخ کامل انتخاب شده ؟

۰
ارسال:
  

ف.ش پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

اون که خیلی حالت داره.
شما باید تعداد گره‌ها رو در نظر بگیرید (n)تعداد یالها باید n-1 باشه حالتهای مختلف حذف یال تا رسیدن به n-1 یال درختهای پوشای مختلف رو میسازه.

مثلا توی شکل سمت چپ شما ۵ گره دارید پس باید ۴ یال باقی بمونه پس میتونید ۳ یال رو حذف کنید مثلا ۳ یال قاعده مثلث یا هر ۳ یال دیگه که حذف کنید یک درخت پوشا رو به شما میده.
* من یادم رفته حالتهایی که منجر به جدا شدن کامل یک نود از بقیه میشه رو در نظر بگیرم یعنی از تعداد حالات کسر کنم.توضیحاتی که آقای دکتر دادن کامل تره.

۰
ارسال: #۱۰
  

leilast پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

تطابق کامل =complete match
برای بدست آوردن تطابق های کامل شکل سمت راست باید از راه بازگشتی رفت
فرمولش میشه ( T(n)=T(n-1)+T(n-2
اینجا باید( T(6 رو حساب کنید به تعداد ستونها
توضیحشم اینه ستونها رو از ۱ تا ۶ شماره گذاری میکنیم
در مرحله اول ۲ حالت داریم:۱-ستون شماره۱ رو انتخاب کنیم که در این صورت یک ستون حذف میشه و میشه( T(n-1
حالت۲:به جای ستون ,سطر رو انتخاب میکنیم که در این حالت با انتخاب سطر ۲ ستون از کل ستونها کم میشه و باید( T(n-2 رو حساب کرد

حالا منم یک سوال دارم که نمیتونم از این راه حلش کنم
تعداد تطابق های کامل مکعب چند تا میشه؟

۰
ارسال: #۱۱
  

admin پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

من بابت اشتباهم معذرت می‍خوام، فکر می‍کنم یه دونه از ۴ از ۴‌ها رو توی جواب آخری که گذاشتم حساب نکرده بودم که می‍شه همون ۲۳ که شما فرمودین.
کلید هم حتماً اشتباه کرده Smile

۰
ارسال: #۱۲
  

delta پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

من این سوالها را یه طوری دیگه حل میکنم مثلا در سوال علوم کامپیوتر ۸۹ یه شکل داده بود (دو تا لوزی و در کنار هر لوزی یه مثلث قرار گرفته بود)خب دو تا مثلث که گراف کاملند جواب میشه ۳×۳=۹ حالا دو تا لوزی باقی میمونه این دو لوزی بسته هستند و تعداد مجموع یالهای هر دو ۸ تا میباشد و چون ۲ تا ناحیه بسته داریم ۲×۸=۱۶ و جواب آخر ۹×۱۶= ۱۴۴
حالا اگه سوال قبل را هم این طوری حل کنیم جواب ۲۱ میشه گراف کاملی که انتخاب میکنیم نباید منجر به ناحیه غیر بسته بشه پس شکل در کل ۷ یال داره با ۳ ناحیه و جواب میشه ۳×۷=۲۱ چند تا سوال دیگه هم با همین روش حل کردم درست بود نمیدونم راه حلم درسته یا نه اگه اشتباهه بگید

ارسال: #۱۳
  

leilast پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

(۰۹ دى ۱۳۸۹ ۰۹:۴۲ ق.ظ)delta نوشته شده توسط:  من این سوالها را یه طوری دیگه حل میکنم مثلا در سوال علوم کامپیوتر ۸۹ یه شکل داده بود (دو تا لوزی و در کنار هر لوزی یه مثلث قرار گرفته بود)خب دو تا مثلث که گراف کاملند جواب میشه ۳×۳=۹ حالا دو تا لوزی باقی میمونه این دو لوزی بسته هستند و تعداد مجموع یالهای هر دو ۸ تا میباشد و چون ۲ تا ناحیه بسته داریم ۲×۸=۱۶ و جواب آخر ۹×۱۶= ۱۴۴
حالا اگه سوال قبل را هم این طوری حل کنیم جواب ۲۱ میشه گراف کاملی که انتخاب میکنیم نباید منجر به ناحیه غیر بسته بشه پس شکل در کل ۷ یال داره با ۳ ناحیه و جواب میشه ۳×۷=۲۱ چند تا سوال دیگه هم با همین روش حل کردم درست بود نمیدونم راه حلم درسته یا نه اگه اشتباهه بگید

اگه گراف دارای زیر گراف همبند باشه از فرمول n^n-2 برای هر مولفه میشه کل درختهای پوشا رو حساب کرد
ولی این شکل رو نمیشه به مولفه های کامل مجزا تقسیم کرد چون یالها مشترکند
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۴
  

admin پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

با تشکر از همه آقایون!!!!!؟ پس خانم‍ها چی می‍شن؟

ارسال: #۱۵
  

roz1 پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

(۰۹ دى ۱۳۸۹ ۰۲:۵۵ ب.ظ)admin نوشته شده توسط:  با تشکر از همه آقایون!!!!!؟ پس خانم‍ها چی می‍شن؟
خانمها رفتن گل بچینن.Tongue
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۶
  

moji67 پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

سلام جواب پوران درسته:

تقسیم مساله به ۳ حالت:
۱- دو یال مشترک هیچکدام انتخاب نشوند یعنی شکل ۱ که در این حالت باید از بین ۵ یال ۴ یال را انتخاب کنیم تا درخت فراگیر ایجاد شود.( ۵ حالت)

۲- یک یال از دو یال مشترک حتما انتخاب شود. یعنی شکل ۲/
که از سمت چپ به ۲ طریق و از سمت راست به ۳ طریق میتوان یال انتخاب کرد تا درخت فراگیر ایجاد شود.(۶ حالت)
چون همین حالات را برای یال مشترک دیگر داریم پس Sad ۲*۶=۱۲ حالت)

۳- هر دو یال مشترک انتخاب شوند یعنی شکل ۳/
که ۲*۱*۲= ۴ حالت دارد.

پس در مجموع سه حالت: ۵+۱۲+۴ = ۲۱ حالت.


فایل‌(های) پیوست شده

۰
ارسال: #۱۷
  

delta پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

بالاخره جواب ۲۱ میشه یا ۲۳؟

۰
ارسال: #۱۸
  

ROZA پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

من فکر میکنم با روشی که دکتر گفتن نمی شه همیشه تعداد درختهای پوشا رو درست بدست آورد.چرا که در مورد گراف های کامل صدق نمی کنه .(البته با احترام به روش ایشون)
پس چطوری میشه یه راه کلی پیدا کرد؟

مثلا این گرافها رو با توجه به گراف کامل باید حل کرد.
[تصویر:  12941232871.jpg]

۰
ارسال: #۱۹
  

saharp پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

میشه ۱ روش کلی برای پیدا کردن تعداد تطابق کامل در گراف دوبخشی غیرکامل بفرمایید؟Huh

۰
ارسال: #۲۰
  

reyhaneh64 پاسخ داده:

RE: تعداد درخت های پوشا و تعداد تطابق کامل

جوابایی که دوستان دادنو خلاصه کردم:
عدد ۲۳
(۰۷ دى ۱۳۸۹ ۰۳:۲۹ ب.ظ)admin نوشته شده توسط:  در شکل سمت چپ شما ۷ تا یال دارید که باید ۴ تا یال رو از بین اون‍ها انتخاب کنید. اما یه نکته وجود داره! باید تعداد حالاتی که ممکنه یک راس و یا بیشتر ایزوله بشن رو ازش کم کنید. پس شما این طوری کار می‍کنید:
انتخاب ۴ از ۷ منهای( راس اول رو با یال‍هاش حذف کنید و حالا از بین یال‍های باقی‍مانده انتخاب کنید + راس دوم رو با یالهاش حذف کنید و از بین یال‍های باقی‍مانده انتخاب کنید+ ....) =
انتخاب ۴ از ۷ منهای( انتخاب ۴ از ۵ + انتخاب ۴ از ۴ + انتخاب ۴ از ۴ + انتخاب ۴ از ۵ + ۰) ==
۳۵-۵-۱-۱-۵-۰ که برابر می‍شود با ۲۳

(۰۸ دى ۱۳۸۹ ۰۱:۵۳ ق.ظ)A.A نوشته شده توسط:  میتونید به این صورت هم بگید که ما باید ۳ یال رو حذف کنیم فقط نباید کل یالهای یک نود رو حذف کرد پس حالاتی که این کل یالهای یک نود رو حذف کردیم حساب میکنیم مثلا از نودی که دو یال داشته دو یالش رو برداشتیم پس یک یال از ۵ یال باقیمانده انتخاب کردیم که جواب آخر با جواب آقای دکتر یکی میشه (البته ایشون توی تفریق آخر یه یک رو جا انداختن)

[tex]\binom{7}{3}-(2*\binom{5}{1}+2*\binom{4}{0})=35-12=23[/tex]

عدد ۲۱:
(۱۲ دى ۱۳۸۹ ۱۱:۱۸ ب.ظ)moji67 نوشته شده توسط:  سلام جواب پوران درسته:

تقسیم مساله به ۳ حالت:
۱- دو یال مشترک هیچکدام انتخاب نشوند یعنی شکل ۱ که در این حالت باید از بین ۵ یال ۴ یال را انتخاب کنیم تا درخت فراگیر ایجاد شود.( ۵ حالت)

۲- یک یال از دو یال مشترک حتما انتخاب شود. یعنی شکل ۲/
که از سمت چپ به ۲ طریق و از سمت راست به ۳ طریق میتوان یال انتخاب کرد تا درخت فراگیر ایجاد شود.(۶ حالت)
چون همین حالات را برای یال مشترک دیگر داریم پس Sad ۲*۶=۱۲ حالت)

۳- هر دو یال مشترک انتخاب شوند یعنی شکل ۳/
که ۲*۱*۲= ۴ حالت دارد.

پس در مجموع سه حالت: ۵+۱۲+۴ = ۲۱ حالت.

(۰۲ بهمن ۱۳۸۹ ۰۱:۰۸ ق.ظ)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.


با توجه به شکل:
۲۱ =۴ + ۲*۲ + ۲*۲+ ۳*۳


فایل‌(های) پیوست شده

۰
ارسال: #۲۱
  

ف.ش پاسخ داده:

تعداد درخت های پوشا و تعداد تطابق کامل

چون یکی از دوستان در مورد اینکه کدام جواب درسته سوال کردن باید بگم که جواب همون ۲۱ میشه و راه حل آقای moji67 درسته.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۸۸۱ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  فیلم کامل آفلاین پایگاه داده استاد خلیلی فر mona64 ۶ ۶,۶۳۹ ۱۱ آذر ۱۴۰۲ ۱۰:۱۵ ق.ظ
آخرین ارسال: Noura9999
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۶۲۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۹۱ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۴۰۸ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۴۱۸ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  فروش کتابهای ارشد کاملا نو و تمیز Fatemeh-Arshad ۳ ۳,۰۹۵ ۰۹ شهریور ۱۳۹۹ ۱۱:۲۰ ق.ظ
آخرین ارسال: hamedmohsenee
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۱۴۸ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد روش های نوشتن عدد n ss311 ۲ ۳,۳۸۴ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد درخت فراگیر ss311 ۰ ۲,۳۳۲ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close