رسم بياني منتظم

في نظرية المخططات ، المخطط المنتظم هو مخطط يكون فيه لكل رأس نفس عدد الجيران؛ أي أن لكل رأس نفس الدرجة أو التكافؤ. ويجب أن يحقق المخطط الموجه المنتظم أيضًا شرطًا أقوى، وهو أن تكون درجة الدخول ودرجة الخروج لكل رأس داخلي متساويتين. ^{[ 1 ]} يُسمى المخطط المنتظم ذو الرؤوس من الدرجة $k$ مخططًا منتظمًا من الدرجة $k$ أو مخططًا منتظمًا من الدرجة $k$ .

حالات خاصة

يسهل تصنيف الرسوم البيانية المنتظمة من الدرجة 2 على الأكثر: يتكون الرسم البياني المنتظم من الدرجة 0 من رؤوس منفصلة، ويتكون الرسم البياني المنتظم من الدرجة 1 من حواف منفصلة، ويتكون الرسم البياني المنتظم من الدرجة 2 من اتحاد منفصل من الدورات والسلاسل اللانهائية.

قياسًا على مصطلحات كثيرات الحدود ذات الدرجات المنخفضة، يُطلق على الرسم البياني المنتظم من الدرجة 3 أو المنتظم من الدرجة 4 غالبًا اسم الرسم البياني المكعب أو الرسم البياني الرباعي ، على التوالي. وبالمثل، من الممكن الإشارة إلى الرسوم البيانية المنتظمة من الدرجة k بـ $k=5,6,7,8,\ldots$ مثل الخماسي، والسداسي، والإنتاني، والثماني، وما إلى ذلك .

الرسم البياني المنتظم بقوة هو رسم بياني منتظم حيث يشترك كل زوج متجاور من الرؤوس في نفس العدد $(ل)$ من الجيران، ويشترك كل زوج غير متجاور من الرؤوس في نفس العدد $(ن)$ من الجيران. أصغر الرسوم البيانية المنتظمة ولكن غير المنتظمة بقوة هي الرسم البياني الدائري والرسم البياني الدائري ذو 6 رؤوس.

الرسم البياني الكامل $K m$ منتظم بقوة لأي قيمة لـ $m$ .

رسم بياني منتظم من 0
1- رسم بياني منتظم
2- رسم بياني منتظم
3- رسم بياني منتظم

ملكيات

بحسب صيغة مجموع الدرجات ، فإن الرسم البياني المنتظم من الدرجة $k ذو$ $n$ رأسًا يحتوي على ${\frac {nk}{2}}$ الحواف. على وجه الخصوص، يجب أن يكون أحد الرتبتين $n$ والدرجة $k$ على الأقل عددًا زوجيًا.

تنص نظرية ناش-ويليامز على أن كل رسم بياني منتظم من الدرجة $k$ على $2 k + 1$ رأسًا يحتوي على دورة هاميلتونية .

لتكن A مصفوفة التجاور لرسم بياني. يكون الرسم البياني منتظمًا إذا وفقط إذا ${\textbf {j}}=(1,\dots ,1)$ هو متجه ذاتي للمصفوفة A. [ ^{2 ]} ستكون قيمته الذاتية هي الدرجة الثابتة للرسم البياني. المتجهات الذاتية المقابلة ^للقيم الذاتية الأخرى متعامدة مع ${\textbf {j}}$ لذلك بالنسبة لمثل هذه المتجهات الذاتية $v=(v_{1},\dots ,v_{n})$ لدينا $\sum _{i=1}^{n}v_{i}=0$ .

يكون الرسم البياني المنتظم من الدرجة k متصلاً إذا وفقط إذا كانت القيمة الذاتية k لها تكرار يساوي واحدًا. اتجاه "فقط إذا" هو نتيجة لنظرية بيرون-فروبينيوس . ^{[ 2 ]}

يوجد أيضًا معيار للرسوم البيانية المنتظمة والمتصلة : يكون الرسم البياني متصلًا ومنتظمًا إذا وفقط إذا كانت مصفوفة الواحدات J ، مع $J_{ij}=1$ ، هو في جبر التجاور للرسم البياني (أي أنه عبارة عن توليفة خطية من قوى A ). ^{[ 3 ]}

ليكن G رسمًا بيانيًا منتظمًا من الدرجة k بقطر D وقيم ذاتية لمصفوفة التجاور $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$ إذا لم تكن G ثنائية الأجزاء، فإن

D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.

^{[ 4 ]}

وجود

يوجد $k$ - رسم بياني منتظم من الدرجة $n$ إذا وفقط إذا حقق العددان الطبيعيان $n$ و $k$ المتباينة $n\geq k+1$ وذلك $nk$ متساوٍ.

البرهان : إذا كان الرسم البياني ذو $n$ رأسًا منتظمًا من الدرجة $k$ ، فإن درجة $k$ لأي رأس v لا يمكن أن تتجاوز العدد $n-1$ من الرؤوس المختلفة عن v ، وفي الواقع يجب أن يكون واحد على الأقل من $n$ و $k$ زوجيًا، ومن ثم يكون حاصل ضربهما كذلك.

على العكس من ذلك، إذا كان $n$ و $k$ عددين طبيعيين يحققان كلاً من المتباينة وشرط الزوجية، فإنه يوجد بالفعل رسم بياني دائري منتظم من الدرجة $k$ $C_{n}^{s_{1},\ldots ,s_{r}}$ من الرتبة $ن$ (حيث $s_{i}$ لنرمز إلى "القفزات" الدنيا التي تجعل الرؤوس ذات المؤشرات المختلفة بمقدار $s_{i}$ إذا كانت متجاورة). وإذا كان $k$ زوجيًا، فإن $k=2r$ وأحد الخيارات الممكنة هو $(s_{1},\ldots ,s_{r})=(1,2,\ldots ,r)$ وإلا فإن $k$ عدد فردي، وبالتالي يجب أن يكون $n$ عددًا زوجيًا، لنقل مع $n=2m$ ، وثم $k=2r-1$ ويمكن اختيار "القفزات" على النحو التالي $(s_{1},\ldots ,s_{r})=(1,2,\ldots ,r-1,m)$ .