میانگین درجات رئوس + تعیین حدود تعداد یالها +گسسته

[کاربر شماره ی یک]

چرا نمیشه با فرمول میانگین درجات رئوس یعنی 2q/p با وجود داشتن راس ماکزیمم درجه و مینیمم درجه و مرتبه ، حدود q رو معلوم کرد ؟

[Kesel]

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]{2q}{p}\leq&space;\Delta

چون ، با توجه به رابطه ی بالا ، تضمینی وجود ندارد که p وq مرتبه و اندازه ی یک گراف باشد و دو عدد کاملا بی ربط نباشد.
اگر q را بخواهیم از رابطه ی بالا به دست آوریم باید اول از خود بپرسیم آیا گرافی با این شرایط وجود دارد ؟
لذا فرمول بالا برای پیدا کردن حداقل یا حداکثر q کفایت نمی کند و بسیار کلی است.
به همین علت برای حل کردن چنین مساله هایی از دنباله ی درجات گراف استفاده می کنید و مدام چک می کنید که آیا این دنباله ، دنباله ی درجات یک گراف هست یا خیر .
مثال : در گراف مرتبه ی 4 با [ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ] حداکثر اندازه ی گراف را به دست آورید.

استفاده از رابطه ی بالا :

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]

شکل مساله :

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]

دنباله ی درجات :
3,3,2,2

لذا q=5 است اما رابطه ی [ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ] اندازه ی تمام رئوس را 3 و یکی را 2 فرض می کند. در حالی که می دانیم چنین اندازه هایی معرف یک گراف نیستند (با استفاده از الگوریتم هاول-حکیمی و یا قضایای مبحث گراف)