گراف k-منظم (k-Regular Graph)، در ریاضیات (Mathematics)

انواع گراف منتظم (Regular Graph) را در آموزش زیر شرح دادیم :

گراف k-منظم (k-Regular Graph) :

این حالت کلی گراف های منظم است. یک گراف

\[ k \]

-منظم، گرافی است که درجه همه رئوس آن برابر با عدد ثابت

\[ k \]

باشد. مقدار

\[ k \]

می تواند هر عدد صحیح غیرمنفی باشد. شرط لازم برای وجود یک گراف

\[ k \]

-منظم با

\[ n \]

راس این است که حاصلضرب

\[ n \times k \]

عددی زوج باشد (چرا که این حاصلضرب دو برابر تعداد یال هاست).

برای مقادیر خاص

\[ k \]

و

\[ n \]

، گراف های شناخته شده ای وجود دارند. به عنوان مثال:

اگر

\[ k = n-1 \]

باشد، گراف یک گراف کامل (Complete Graph) با نماد

\[ K_n \]

خواهد بود که در آن هر راس به همه رئوس دیگر (به جز خودش) متصل است.

اگر

\[ k = 0 \]

باشد، گراف تهی (Empty Graph) یا گراف بدون یال خواهیم داشت.

بررسی وجود و یکتایی این گراف ها برای مقادیر مختلف

\[ k \]

و

\[ n \]

یکی از مسائل بنیادی در نظریه گراف است.