رسم بياني منتظم للمسافة

الموسوعة الحرة

في المجال الرياضي لنظرية الرسم البياني ، فإن الرسم البياني المنتظم المسافة هو رسم بياني منتظم بحيث أنه بالنسبة لأي رأسين v و w ، فإن عدد الرؤوس على مسافة j من v وعلى مسافة k من w يعتمد فقط على j و k والمسافة بين v و w .

يستثني بعض المؤلفين الرسوم البيانية الكاملة والرسوم البيانية غير المتصلة من هذا التعريف.

كل رسم بياني متعدٍ للمسافة هو رسم بياني منتظم للمسافة. في الواقع، تم تقديم الرسوم البيانية المنتظمة للمسافة كتعميم توافقي للرسوم البيانية المتعدية للمسافة، حيث تتمتع بخصائص الانتظام العددي للأخيرة دون أن يكون لها بالضرورة مجموعة تماثل ذاتي كبيرة .

مصفوفات التقاطع

مصفوفة التقاطع للرسم البياني المنتظم المسافة هي المصفوفة(ب0،ب1،...،بد-1؛ج1،...،جد){\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}في أيد{\displaystyle d}يمثل قطر الرسم البياني ولكل1≤ج≤د{\displaystyle 1\leq j\leq d}،بج{\displaystyle b_{j}}يعطي عدد جيرانu{\displaystyle u}عن بعدج+1{\displaystyle j+1}منv{\displaystyle v}وجج{\displaystyle c_{j}}يعطي عدد جيرانu{\displaystyle u}عن بعدج-1{\displaystyle j-1}منv{\displaystyle v}لأي زوج من الرؤوسu{\displaystyle u}وv{\displaystyle v}عن بعدج{\displaystyle j}وهناك أيضاً الرقمأج{\displaystyle a_{j}}وهذا يعطي عدد جيرانu{\displaystyle u}عن بعدج{\displaystyle j}منv{\displaystyle v}الأرقامأج،بج،جج{\displaystyle a_{j},b_{j},c_{j}}تُسمى هذه الأرقام أرقام تقاطع الرسم البياني. وهي تحقق المعادلة التالية:أج+بج+جج=ك،{\displaystyle a_{j}+b_{j}+c_{j}=k,}أينك=ب0{\displaystyle k=b_{0}}هي التكافؤ ، أي عدد الجيران، لأي رأس.

اتضح أن الرسم البيانيجي{\displaystyle G}قطرد{\displaystyle d}تكون المسافة منتظمة إذا وفقط إذا كان لها مصفوفة تقاطع بالمعنى السابق.

الرسوم البيانية الطيفية المشتركة والمنفصلة ذات المسافة المنتظمة

يكون زوج من الرسوم البيانية المتصلة ذات المسافة المنتظمة متطابقين طيفياً إذا كانت مصفوفات التجاور الخاصة بهما لها نفس الطيف . وهذا يكافئ امتلاكهما نفس مصفوفة التقاطع.

يكون الرسم البياني المنتظم المسافة منفصلاً إذا وفقط إذا كان اتحادًا منفصلاً للرسوم البيانية المنتظمة المسافة الطيفية المشتركة.

ملكيات

يفترضجي{\displaystyle G}هو رسم بياني متصل منتظم المسافة من التكافؤك{\displaystyle k}مع مصفوفة التقاطع(ب0،ب1،...،بد-1؛ج1،...،جد){\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}لكل0≤ج≤د،{\displaystyle 0\leq j\leq d,}يترككج{\displaystyle k_{j}}يشير إلى عدد الرؤوس على مسافةج{\displaystyle j}من أي رأس معين، ولتكن جيج{\displaystyle G_{j}}يشير إلىكج{\displaystyle k_{j}}- رسم بياني منتظم مع مصفوفة تجاورأج{\displaystyle A_{j}}تتكون من خلال ربط أزواج من الرؤوس علىجي{\displaystyle G}عن بعدج{\displaystyle j}.

خصائص نظرية الرسم البياني

  • كج+1كج=بججج+1{\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}للجميع0≤ج<د{\displaystyle 0\leq j<d}.
  • ب0>ب1≥⋯≥بد-1>0{\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}و1=ج1≤⋯≤جد≤ب0{\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}.

الخصائص الطيفية

  • جي{\displaystyle G}لديهد+1{\displaystyle d+1}قيم ذاتية مميزة.
  • القيمة الذاتية البسيطة الوحيدة لـجي{\displaystyle G}يكونك،{\displaystyle k,}أو كليهماك{\displaystyle k}و-ك{\displaystyle -k}لوجي{\displaystyle G}هو ثنائي الأجزاء.
  • ك≤12(م-1)(م+2){\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}لأي تعددية قيم ذاتيةم>1{\displaystyle m>1}لجي،{\displaystyle G,}إلا إذاجي{\displaystyle G}هو رسم بياني متعدد الأجزاء كامل.
  • د≤3م-4{\displaystyle d\leq 3m-4}لأي تعددية قيم ذاتيةم>1{\displaystyle m>1}لجي،{\displaystyle G,}إلا إذاجي{\displaystyle G}هو رسم بياني دوري أو رسم بياني متعدد الأجزاء كامل.

لوجي{\displaystyle G}إذا كانت منتظمة بقوة ، فإنن≤4م-1{\displaystyle n\leq 4m-1}وك≤2م-1{\displaystyle k\leq 2m-1}.

مخطط الجمعية

الأنا{\displaystyle i}مصفوفات تجاور المسافةأأنا{\displaystyle A_{i}}لأنا=0،1،...،د{\displaystyle i=0,1,...,d}تشكل الرسوم البيانية المنتظمة المسافة مخطط ارتباط .

أمثلة

الرسم البياني كلاين من الدرجة 7 والخريطة المرتبطة به مضمنة في سطح قابل للتوجيه من النوع 3. هذا الرسم البياني منتظم المسافة مع مصفوفة التقاطع {7,4,1;1,2,7} ومجموعة التماثل الذاتي PGL(2,7).

تتضمن بعض الأمثلة الأولى للرسوم البيانية المنتظمة المسافة ما يلي:

تصنيف الرسوم البيانية المنتظمة المسافة

يوجد عدد محدود فقط من الرسوم البيانية المتصلة والمنتظمة المسافة والمختلفة لأي تكافؤ معين.ك>2{\displaystyle k>2}[ 1 ]​

وبالمثل، لا يوجد سوى عدد محدود من الرسوم البيانية المتصلة والمنتظمة المسافة المتميزة ذات أي تعددية قيم ذاتية معينة.م>2{\displaystyle m>2}[ 2 ] (باستثناء الرسوم البيانية متعددة الأجزاء الكاملة).

رسوم بيانية منتظمة للمسافة التكعيبية

تم تصنيف الرسوم البيانية ذات المسافة التكعيبية المنتظمة بشكل كامل.

الرسوم البيانية الـ 13 المتميزة ذات المسافة المنتظمة المكعبة هي K 4 (أو الرسم البياني رباعي الأوجه )، K 3,3 ، الرسم البياني لبيترسن ، الرسم البياني المكعب ، الرسم البياني لهيوود ، الرسم البياني لبابوس ، الرسم البياني لكوكسيتر ، الرسم البياني لتوت-كوكسيتر ، الرسم البياني ذو الاثني عشر وجهًا ، الرسم البياني لديسارج ، قفص توت ذو 12 وجهًا ، الرسم البياني لبيغز-سميث ، والرسم البياني لفستر .

مراجع

  1. ↑ بانغ، س.؛ دوبيكاس، أ.؛ كولين، ج.هـ.؛ مولتون، ف. (10 يناير 2015). "لا يوجد سوى عدد محدود من الرسوم البيانية المنتظمة المسافة ذات التكافؤ الثابت الأكبر من اثنين" . التقدم في الرياضيات . 269 (ملحق ج): 1-55 . arXiv : 0909.5253 . doi : 10.1016/j.aim.2014.09.025 . S2CID 18869283 . 
  2. ↑ جودسيل، سي دي (1988-12-01). "تحديد قطر الرسوم البيانية المنتظمة المسافة". كومبيناتوريكا . 8 (4): 333-343 . doi : 10.1007/BF02189090 . ISSN 0209-9683 . S2CID 206813795 .  

للمزيد من القراءة