از گراف کامل ۱۲ رأسی یالهای یک تطابق کامل را بر می داریم. تعداد مثلث های گراف باقی مانده کدام است؟
الف)۱۵۰
ب)۱۶۰
ج) ۱۹۰
د) ۲۲۰
(۱۸ دى ۱۳۹۲ ۱۰:۳۳ ب.ظ)maria12 نوشته شده توسط: از گراف کامل ۱۲ رأسی یالهای یک تطابق کامل را بر می داریم. تعداد مثلث های گراف باقی مانده کدام است؟
الف)۱۵۰
ب)۱۶۰
ج) ۱۹۰
د) ۲۲۰
به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کامل
حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱۶۰ خواهیم رسید
(۱۹ دى ۱۳۹۲ ۱۲:۱۰ ق.ظ)wokesh نوشته شده توسط: به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کاملمثلث وجود دارد.
حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱۴۰ خواهیم رسید
سلام. راه حلتون کاملاً درسته. فقط [tex]\binom{12}{3}-60=160[/tex].
(۱۹ دى ۱۳۹۲ ۰۲:۵۵ ق.ظ)Jooybari نوشته شده توسط: به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کامل
حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱۴۰ خواهیم رسید
سلام. راه حلتون کاملاً درسته. فقط [tex]\binom{12}{3}-60=160[/tex].
[/quote]
تشکر، تصحیح کردم