تالار گفتمان مانشت

از گراف کامل 12 رأسی یالهای یک تطابق کامل را بر می داریم. تعداد مثلث های گراف باقی مانده کدام است؟
الف)150
ب)160
ج) 190
د) 220

(18 دى 1392 10:33 ب.ظ)maria12 نوشته شده توسط: [ -> ]از گراف کامل ۱۲ رأسی یالهای یک تطابق کامل را بر می داریم. تعداد مثلث های گراف باقی مانده کدام است؟
الف)۱۵۰
ب)۱۶۰
ج) ۱۹۰
د) ۲۲۰

به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کامل مثلث وجود دارد.

حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱60 خواهیم رسید

(19 دى 1392 12:10 ق.ظ)wokesh نوشته شده توسط: [ -> ]به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کامل مثلث وجود دارد.

حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱۴۰ خواهیم رسید

سلام. راه حلتون کاملاً درسته. فقط [tex]\binom{12}{3}-60=160[/tex].

(19 دى 1392 02:55 ق.ظ)Jooybari نوشته شده توسط: [ -> ]به نظرم گزینه ۲ صحیح است
اول اینکه در یک گراف کامل مثلث وجود دارد.

حال اگر در گراف کامل زوج راسی یک تطابق کامل حذف شود نصف تعداد راسها یعنی در اینجا ۶ یال حذف خواهد شد.
هر یال که دو راس دارد با رئوس دیگر تشکیل مثلث میدهد. پس وقتی یک یال حذف میشود مثلثهایی که توسط آن ایجاد میشوند نیز حذف خواهد شد.
در اینجا ۶ یال را یعنی یک تطایق کامل را حذف کردیم که هر یال حذف شده (که از دو راس تشکیل یافته) با ده راس دیگر تشکیل تشکیل ۱۰ مثلث را میدهد. پس ما به طور کلی از مجموع مثلثهای گراف کامل ۱۲ راسی ۱۰*۶ مثلث را کسر میکنیم که به جواب ۱۴۰ خواهیم رسید

سلام. راه حلتون کاملاً درسته. فقط [tex]\binom{12}{3}-60=160[/tex].
[/quote]

تشکر، تصحیح کردم