پیش‌نویس:قضیه اردوش گالای

قضیه اردوش گالای نتیجه‌ای در نظریه گراف ، شاخه ای از ریاضیات ترکیبی است. یکی از دو رویکرد شناخته شده برای حل مسئله گرافیک بودن دنباله درجات را ارائه می دهد، یعنی شرط لازم و کافی را برای یک دنباله متناهی از اعداد صحیح غیرمنفی می دهد که دنباله درجات یک گراف ساده باشد. این قضیه در سال 1960 توسط پال اردوش و تیبور گالای منتشر شد که به نام آنها نامگذاری شده است.

شرح قضیه

دنباله ای از اعداد صحیح غیر منفی $d_{1} \geq \dots \geq d_{n}$ را می توان به عنوان دنباله درجه یک گراف ساده متناهی n راسی در نظر گرفت اگر و فقط اگر $d_{1} + \dots + d_{n}$ زوج باشد و

\sum_{i = 1}^{k} d_{i} \leq k (k - 1) + \sum_{i = k + 1}^{n} \min (d_{i}, k)

برای هر $1 \leq k \leq n$ برقرار باشد.

اثبات‌ها

نشان دادن اینکه شرایط قضیه Erdős-Gallai برای گرافیکی بودن دنباله‌ای از اعداد لازم است دشوار نیست. شرط زوج بودن مجموع درجات، لمای قیاس منطقی دست به دست است که قبلاً توسط اویلر در مقاله خود در سال 1736 در مورد هفت پل کونیگسبرگ استفاده شده است. نابرابری بین مجموع k بزرگ‌ترین درجه‌ها و مجموع درجات باقی‌مانده را می‌توان با شمارش مضاعف تعیین کرد: سمت چپ مجموع تعداد مجاورت‌ها را در بین k راس های بالاترین درجه، هر یک از این مجاورت ها یا بین دو راس با درجه‌ی زیاد است یا بین یک راس با درجه‌ی زیاد و یک راس با درجه‌ی کم. k(k−1) عبارت سمت راست حداکثر تعداد ممکن یال‌های بین دو راس با درجه زیاد را نشان می دهد و عبارت دیگر در سمت راست، تعداد یال‌هایی را نشان می دهد که دقیقاً یک راس درجه بالایی دارند. بنابراین، بخش دشوارتر اثبات این است که نشان دهیم، برای هر دنباله‌ای از اعداد که از این شرایط پیروی می کنند، گرافی وجود دارد که این دنباله برای آن، دنباله‌ی درجات است.

جستارهای وابسته

Havel–Hakimi algorithm

منابع

پیش‌نویس:قضیه اردوش گالای

فهرست

شرح قضیه

اثبات‌ها

جستارهای وابسته

منابع

منوی ناوبری

پیش‌نویس:قضیه اردوش گالای

شرح قضیه

اثبات‌ها

جستارهای وابسته

منابع

منوی ناوبری

جستجو