عائلة بيترسن

في نظرية الرسوم البيانية ، تُعرف عائلة بيترسن بأنها مجموعة من سبعة رسوم بيانية غير موجهة تتضمن رسم بيترسن البياني والرسم البياني الكامل K _6. سُميت عائلة بيترسن نسبةً إلى عالم الرياضيات الدنماركي يوليوس بيترسن ، الذي سُمي رسم بيترسن البياني باسمه.

يمكن تحويل أيٍّ من الرسوم البيانية في عائلة بيترسن إلى أي رسم بياني آخر في العائلة باستخدام تحويلات YΔ وΔY ، وهي عمليات يتم فيها استبدال مثلث برأس من الدرجة الثالثة أو العكس. تُشكّل هذه الرسوم البيانية السبعة القواسم الصغرى المحظورة للرسوم البيانية القابلة للتضمين بدون روابط ، وهي رسوم بيانية يمكن تضمينها في فضاء ثلاثي الأبعاد بحيث لا ترتبط أي دورتين في الرسم البياني . [ ^{1 ] كما} أنها من بين القواسم الصغرى المحظورة للرسوم البيانية القابلة للاختزال YΔY . ^{[ 2 ] [ 3 ]}

يكون شكل تحويلات YΔ و ΔY المستخدمة لتحديد عائلة Petersen كما يلي:

• إذا كان الرسم البياني G يحتوي على رأس v مع ثلاثة جيران بالضبط، فإن تحويل YΔ لـ G عند v هو الرسم البياني المتكون عن طريق إزالة v من G وإضافة حواف بين كل زوج من جيرانه الثلاثة.
• إذا كان الرسم البياني H يحتوي على مثلث uvw ، فإن تحويل ΔY لـ H عند uvw هو الرسم البياني المتكون عن طريق إزالة الحواف uv و vw و uw من H وإضافة رأس جديد متصل بجميع الحواف u و v و w .

تُسمى هذه التحويلات بهذا الاسم نسبةً إلى شكل المثلث (Δ) في الرسم البياني وشكل الرأس ذي الدرجة الثالثة (Y). مع أن هذه العمليات قد تؤدي نظريًا إلى رسوم بيانية متعددة ، إلا أن ذلك لا يحدث ضمن عائلة بيترسن. ولأن هذه العمليات تحافظ على عدد الحواف في الرسم البياني، فإن عدد الرسوم البيانية أو الرسوم البيانية المتعددة التي يمكن تكوينها من رسم بياني ابتدائي واحد G باستخدام تركيبات من تحويلات ΔY و YΔ محدود.

تتألف عائلة بيترسن من كل رسم بياني يمكن الوصول إليه من رسم بيترسن البياني عن طريق دمج تحويلات ΔY و YΔ. يوجد سبعة رسوم بيانية في هذه العائلة، بما في ذلك الرسم البياني الكامل K6 ذو الستة رؤوس، والرسم البياني ذو الثمانية رؤوس الناتج عن إزالة حافة واحدة من الرسم البياني الثنائي الكامل K4,4 _، والرسم البياني الثلاثي الكامل _ذو السبعة رؤوس K3,3,1 _.

الرسم البياني الفرعي للرسم البياني G هو رسم بياني آخر مُشتق من G عن طريق تقليص وإزالة الحواف. وكما تُبين نظرية روبرتسون-سيمور ، يمكن تمييز العديد من عائلات الرسوم البيانية المهمة بمجموعة محدودة من الرسوم البيانية الفرعية المحظورة : على سبيل المثال، وفقًا لنظرية فاغنر ، فإن الرسوم البيانية المستوية هي تحديدًا الرسوم البيانية التي لا تحتوي على الرسم البياني الكامل K⁵ ولا الرسم البياني الثنائي الكامل K⁳ _{, ³} كرسوم بيانية فرعية.

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

تُشكّل عائلة بيترسن أيضًا بعضًا من القواسم الصغرى المحظورة لعائلة أخرى من الرسوم البيانية، وهي الرسوم البيانية القابلة للاختزال YΔY. يكون الرسم البياني المتصل قابلًا للاختزال YΔY إذا أمكن اختزاله إلى رأس واحد من خلال سلسلة من الخطوات، كل منها عبارة عن تحويل ΔY أو YΔ، وإزالة حلقة ذاتية أو تجاور متعدد، وإزالة رأس له جار واحد، واستبدال رأس من الدرجة الثانية وحافتيه المجاورتين بحافة واحدة. على سبيل المثال، يمكن اختزال الرسم البياني الكامل K ₄ إلى رأس واحد من خلال تحويل YΔ يحوله إلى مثلث ذي حواف مزدوجة، وإزالة الحواف المزدوجة الثلاث، وتحويل ΔY يحوله إلى شكل المخلب K _1,3 ، وإزالة رؤوس المخلب الثلاثة من الدرجة الأولى. يُشكّل كل رسم بياني من عائلة بيترسن قاسمًا صغريًا محظورًا أدنى لعائلة الرسوم البيانية القابلة للاختزال YΔY. ^{[ ٢ ]} مع ذلك، قدّم نيل روبرتسون مثالًا على رسم بياني رأسي (رسم بياني قابل للتضمين بدون روابط، يتكون من إضافة رأس واحد إلى رسم بياني مستوٍ) غير قابل للاختزال YΔY، مُبينًا أن الرسوم البيانية القابلة للاختزال YΔY تُشكّل فئة فرعية مناسبة من الرسوم البيانية القابلة للتضمين بدون روابط، ولها قواطع فرعية محظورة إضافية. ^{[ ٢ ]} في الواقع، كما أوضح يامينغ يو، يوجد ما لا يقل عن ٦٨,٨٩٧,٩١٣,٦٥٢ قاطعًا فرعيًا محظورًا للرسوم البيانية القابلة للاختزال YΔY، بالإضافة إلى سبعة من عائلة بيترسن. ^{[ ٣ ]}