تحليل الرسم البياني

يُقابل التحليل الأحادي للرسم البياني الكامل عمليات التزاوج في بطولة الدوري . ويُعدّ التحليل الأحادي للرسوم البيانية الكاملة حالة خاصة من نظرية باراني المتعلقة بالتحليل الأحادي للرسوم البيانية الفائقة الكاملة .

إحدى طرق إنشاء تحليل أحادي لرسم بياني كامل ذي عدد زوجي من الرؤوس تتضمن وضع جميع الرؤوس باستثناء رأس واحد في مضلع منتظم ، بحيث يكون الرأس المتبقي في المركز. مع هذا الترتيب للرؤوس، تتمثل إحدى طرق إنشاء عامل أحادي للرسم البياني في اختيار ضلع e من المركز إلى رأس واحد من المضلع، بالإضافة إلى جميع الأضلاع الممكنة التي تقع على خطوط عمودية على e . تشكل العوامل الأحادية التي يمكن إنشاؤها بهذه الطريقة تحليلًا أحاديًا للرسم البياني.

عدد التحليلات الفردية المختلفة لـ K ₂ ، K ₄ ، K ₆ ، K ₈ ، ... هو 1، 1، 6، 6240، 1225566720، 252282619805368320، 98758655816833727741338583040، ... (التسلسل A000438 في OEIS ) .

ليكن G رسمًا بيانيًا منتظمًا من الدرجة k يحتوي على 2 ^n عقدة. إذا كانت k كبيرة بما فيه الكفاية، فمن المعروف أن G يجب أن يكون قابلاً للتحليل إلى عامل واحد:

• إذا كان k  =  2 n − 1، فإن G هو الرسم البياني الكامل K _{2 n} ، وبالتالي قابل للتحليل إلى عامل واحد (انظر أعلاه ).  
• إذا كان k  =  2n - 2، فيمكن إنشاء G عن طريق إزالة تطابق تام من K2n . ومرة ​​أخرى، _فإن G قابلة للتحليل _إلى عامل واحد.  
• أظهر تشيتويند وهيلتون (1985) أنه إذا كان k  ≥  12 n /7، فإن G قابل للتحليل إلى عامل واحد.

تُعدّ فرضية التحليل إلى عوامل أولية ^{[ 3 ]} فرضيةً راسخةً تنصّ على أن k  ≈ n كافية. وبصورة أدق، فإن الفرضية هي: 

• إذا كان n فرديًا و k  ≥ n ، فإن G قابلة للتحليل إلى عامل واحد. وإذا كان n زوجيًا و k ≥ n − 1، فإن G قابلة للتحليل إلى عامل واحد.     

تُشير فرضية الامتلاء الزائد إلى فرضية التحليل إلى عامل واحد. وقد أكد تشابا، وكوهن، ولو، وأوستوس، وتريغلاون هذه الفرضية لقيم n الكبيرة بما فيه الكفاية . ^{[ 4 ]}

الزوج المثالي الناتج عن تحليل العامل الواحد هو زوج من العوامل الواحد التي يؤدي اتحادها إلى دورة هاميلتونية .

التحليل الأحادي المثالي (P1F) للرسم البياني هو تحليل أحادي يتميز بأن كل زوج من العوامل الأحادية فيه هو زوج مثالي. يجب عدم الخلط بين التحليل الأحادي المثالي والمطابقة المثالية (التي تُسمى أيضًا عاملًا أحاديًا).

في عام 1964، افترض أنطون كوتزيج أن كل رسم بياني كامل K _{2 n} حيث n ≥ 2 له تحليل مثالي من الدرجة 1. حتى الآن، من المعروف أن الرسوم البيانية التالية لها تحليل مثالي من الدرجة 1: ^{[ 5 ]}

• العائلة اللانهائية من الرسوم البيانية الكاملة K _{2 p} حيث p عدد أولي فردي (بحسب أندرسون وناكامورا، بشكل مستقل)،
• العائلة اللانهائية من الرسوم البيانية الكاملة K _{p +1} حيث p عدد أولي فردي،
• ونتائج إضافية متفرقة، بما في ذلك K _{2 n} حيث 2 n ∈ {16، 28، 36، 40، 50، 126، 170، 244، 344، 730، 1332، 1370، 1850، 2198، 3126، 6860، 12168، 16808، 29792}. وقد جُمعت بعض النتائج الأحدث هنا .

إذا كان للرسم البياني الكامل K _{n +1} تحليل مثالي من الدرجة 1، فإن الرسم البياني الثنائي الكامل K _{n , n} له أيضًا تحليل مثالي من الدرجة 1. ^{[ 6 ]}