0 مخالف

فرض کنیم $2n$ نقطه در فضا داریم و در مجموع $n^2+1$ پاره‌خط بین آنها رسم شده است. نشان دهید حداقل یک مجموعه از سه نقطه وجود دارد که دو به دو به وسیله‌ی پاره‌خط‌هایی به هم وصل شده‌اند.

<p>فرض کنیم $2n$ نقطه در فضا داریم و در مجموع $n^2+1$ پاره&zwnj;خط بین آنها رسم شده است. نشان دهید حداقل یک مجموعه از سه نقطه وجود دارد که دو به دو به وسیله&zwnj;ی پاره&zwnj;خط&zwnj;هایی به هم وصل شده&zwnj;اند.</p>

فرض کنیم $2n$ نقطه در فضا داریم و در مجموع $n^2+1$ پاره‌خط بین آنها رسم شده است. نشان دهید حداقل یک مجموعه از سه نقطه وجود دارد که دو به دو به وسیله‌ی پاره‌خط‌هایی به هم وصل شده‌اند.

# ریاضیات # نظریه گراف # ریاضیات گسسته
پاسخ‌ها

عکس نقیض قصیه را اثبات می‌کنیم. یعنی ثابت می‌کنیم گرافی که $2n$ رأس داشته باشد و بدون مثلث باشد، حداکثر $n^2$ یال دارد.

برای $n=1$ قضیه به وضوح برقرار است.
فرض کنیم برای گرافی با $2n$ رأس نیز برقرار باشد، قضیه را برای گراف با $2n+2$ رأس اثبات می‌کنیم.

فرض کنیم $G$ گرافی با $2n+2$ رأس  و بدون مثلث باشد. دو رأس $A$ و $B$ از $G$ را که به وسیله‌ی یک یال به هم متصل شده‌اند انتخاب می‌کنیم. حال $A$ و $B$ و تمام یال‌های متصل به آنها را ندید بگیریم.
گراف باقی‌مانده $G'$ دارای $2n$ رأس و بدون مثلث است. با توجه به فرض استقرا $G'$ حداکثر $n^2$ یال دارد.

$G$ چند یال می‌تواند داشته باشد؟
هیچ رأسی مانند $C$ وجود ندارد که رئوس $A$ و $B$ هر دو به آن متصل باشند زیرا اگر چنین باشد، $G$ مل یک مثلث است. بنابراین اگر $A$ به $x$ رأس از $G'$ متصل باشد، آنگاه $B$ به حداکثر $2n-x$ رأس از $G'$ متصل است. پس (یالی که $A$ را به $B$ وصل می‌کند را در شمارش از یاد نبرید) $G$ حداکثر n2+2n-x+x+1 یا n+12=n2+2n+1 یال دارد.

حالت تساوی مسأله نیز برقرار است و در حقیقت می‌توان گراف $n^2$ رأسی بدون مثلث را به این روش ساخت:
در واقع $2n$ رأس را به دو مجموعه‌ی $n$ تایی $P$ و $Q$ افراز می‌کنیم و تمام رئوس $P$ را به تمام رئوس $Q$ متصل می‌کنیم. گراف حاصل هیچ مثلثی ندارد.

0 مخالف
پیش نمایش پاسخ