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

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

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

[Kesel]

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

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



شکل مساله :



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

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