الرسم البياني ذو الحواف المتعدية

في المجال الرياضي لنظرية الرسم البياني ، فإن الرسم البياني المتعدي على الحواف هو رسم بياني G بحيث، بالنظر ^إلى أي حافتين e ₁ و e ₂ من G ، يوجد تماثل ذاتي لـ G يقوم بتحويل e ₁ إلى e _2. ^{[ 1} ]

بمعنى آخر، يكون الرسم البياني متعدياً على الحواف إذا كانت مجموعة التشاكل الذاتي الخاصة به تعمل بشكل متعدٍ على حوافه.

عدد الرسوم البيانية البسيطة المتصلة ذات الحواف المتعدية على n رأس هو 1، 1، 2، 3، 4، 6، 5، 8، 9، 13، 7، 19، 10، 16، 25، 26، 12، 28 ... (التسلسل A095424 في OEIS )

تشمل الرسوم البيانية المتعدية للحواف جميع الرسوم البيانية المتناظرة ، مثل رؤوس وحواف المكعب . [ ^{1 ] الرسوم} البيانية المتناظرة هي أيضًا متعدية للرؤوس (إذا كانت متصلة )، ولكن بشكل عام، لا يشترط أن تكون الرسوم البيانية المتعدية للحواف متعدية للرؤوس. يجب أن يكون كل رسم بياني متصل متعدٍ للحواف وغير متعدٍ للرؤوس ثنائي الأجزاء ، [ ^{1 ] (} وبالتالي يمكن تلوينه بلونين فقط)، وأن يكون إما شبه متناظر أو ثنائي الانتظام . ^{[ 2 ]}

من أمثلة الرسوم البيانية المتعدية على الحواف ولكن ليس على الرؤوس، الرسوم البيانية الثنائية الكاملة.${\displaystyle K_{m,n}}$حيث m ≠ n، وهو ما يشمل الرسوم البيانية النجمية${\displaystyle K_{1,n}}$بالنسبة للرسوم البيانية ذات n رأسًا، يوجد (n-1)/2 رسمًا بيانيًا من هذا النوع عندما يكون n فرديًا، و(n-2) عندما يكون n زوجيًا. يمكن تكوين رسوم بيانية إضافية متعدية الحواف، غير متناظرة، كرسوم بيانية فرعية لهذه الرسوم البيانية الثنائية الكاملة في حالات معينة. توجد رسوم بيانية فرعية للرسوم البيانية الثنائية الكاملة K_{_m,n} عندما يشترك m وn في عامل أكبر من 2. عندما يكون العامل المشترك الأكبر هو 2، توجد رسوم بيانية فرعية عندما يكون 2n/m زوجيًا، أو إذا كان m=4 وn مضاعفًا فرديًا للعدد 6. ^{[ 3 ]} لذا، توجد رسوم بيانية فرعية متعدية الحواف للرسوم البيانية K _{_3,6} وK_{_4,6} وK _{_5,10} ، ولكن لا توجد للرسم البياني K _{_4,10} . يتمثل أحد البدائل لبناء بعض الرسوم البيانية المتعدية للحواف في إضافة رؤوس إلى منتصف حواف الرسم البياني المتماثل الذي يحتوي على v رأسًا و e حافة، مما يؤدي إلى إنشاء رسم بياني ثنائي الأجزاء يحتوي على e رأسًا من الرتبة 2، و v من الرتبة 2e/v.

يُطلق على الرسم البياني شبه المتناظر اسم الرسم البياني الذي يتميز بخاصية التعدي على الحواف ، ولكنه ليس متعديًا على الرؤوس . يُعدّ رسم غراي البياني ، وهو رسم بياني مكعب الشكل ذو 54 رأسًا، مثالًا على رسم بياني منتظم يتميز بخاصية التعدي على الحواف ولكنه ليس متعديًا على الرؤوس. أما رسم فولكمان البياني ، وهو رسم بياني من الدرجة الرابعة ذو 20 رأسًا، فهو أصغر رسم بياني من هذا النوع.

إن اتصال الرؤوس في الرسم البياني المتعدي على الحواف يساوي دائمًا الحد الأدنى لدرجته . ^{[ 4 ]}

• خاصية التعدي على الحواف (في الهندسة)

• وايسشتاين، إريك دبليو. "الرسم البياني المتعدي على الحواف" . عالم الرياضيات .