نظرية بيترسن

في فرع الرياضيات المعروف بنظرية المخططات ، تُعد نظرية بيترسن ، التي سُميت نسبةً إلى يوليوس بيترسن ، واحدة من أقدم النتائج في نظرية المخططات، ويمكن صياغتها على النحو التالي:

نظرية بيترسن. كل رسم بياني مكعب بدون جسور يحتوي على تطابق مثالي . ^{[ 1 ]}

بمعنى آخر، إذا كان للرسم البياني ثلاثة حواف بالضبط عند كل رأس، وكل حافة تنتمي إلى دورة، فإنه يحتوي على مجموعة من الحواف التي تلامس كل رأس مرة واحدة بالضبط.

نُبين أنه لكل رسم بياني مكعب الشكل، خالٍ من الجسور، G = ( V , E ) ، فإنه لكل مجموعة U ⊆ V، يكون عدد المكونات المتصلة في الرسم البياني الناتج عن V − U   ، والذي يحتوي على عدد فردي من الرؤوس، على الأكثر عدد عناصر U. وبناءً على ذلك، ووفقًا لنظرية توت حول المطابقات الكاملة، فإن G يحتوي على مطابقة كاملة.

ليكن Gᵢ مكونًا ذا عدد فردي من الرؤوس في الرسم البياني المستحث بواسطة مجموعة الرؤوس V − U.   ولتكن Viᵢ رؤوس Gᵢ _، وليكن mᵢ عدد حواف G التي تحتوي _على رأس واحد في Viᵢ ورأس واحد في _{U. وباستخدام حجة بسيطة للعد المزدوج ،} نحصل على _:

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},}$

حيث E _i هي مجموعة حواف G _i التي تقع رؤوسها في V _i . بما أن

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|}$

بما أن m عدد فردي و 2| E _i | عدد زوجي، فإن m _i يجب أن يكون عددًا فرديًا. علاوة على ذلك، بما أن G لا تحتوي على جسور، فإن m _i  ≥  3 .

ليكن m عدد الحواف في G التي لها رأس واحد في U ورأس واحد في الرسم البياني الناتج عن V − U.   كل مكون ذي عدد فردي من الرؤوس يُساهم بثلاث حواف على الأقل في m ، وهذه الحواف فريدة، وبالتالي، فإن عدد هذه المكونات لا يتجاوز m /3 . في أسوأ الحالات، تكون U مجموعة مستقلة، وبالتالي m  ≤  3| U | . نحصل على

${\displaystyle |U|\geq {\frac {1}{3}}m\geq |\{{\text{المكونات ذات عدد فردي من الرؤوس}}\}|,}$

وهذا يدل على أن شرط نظرية توت بشأن المطابقات الكاملة صحيح.

تُنسب هذه النظرية إلى يوليوس بيترسن ، عالم الرياضيات الدنماركي. ويمكن اعتبارها من أوائل النتائج في نظرية المخططات . ظهرت النظرية لأول مرة في مقالة عام 1891 بعنوان " نظرية المخططات المنتظمة ". ^{[ 1 ]} وبمعايير اليوم، يُعد برهان بيترسن على النظرية معقدًا. وقد أدت سلسلة من التبسيطات للبرهان إلى البراهين التي قدمها فرينك (1926) وكونيغ (1936) .

في الكتب المدرسية الحديثة، يتم تناول نظرية بيترسن كتطبيق لنظرية توت حول المطابقات الكاملة .

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

• نظرية العاملين – نظرية ذات صلة لبيترسن