خوارزميات كليتمان-وانغ

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

تعتمد الخوارزمية على النظرية التالية.

يترك${\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))}$لتكن قائمة منتهية من الأعداد الصحيحة غير السالبة مرتبة ترتيبًا معجميًا تنازليًا ، ولتكن${\displaystyle (a_{i},b_{i})}$ليكن زوجًا من الأعداد الصحيحة غير السالبة مع${\displaystyle b_{i}>0}$. قائمة${\displaystyle S}$تكون ثنائية الكتابة إذا وفقط إذا كانت القائمة المنتهية${\displaystyle S'=((a_{1}-1,b_{1}),\dots ,(a_{b_{i}-1}-1,b_{b_{i}-1}),(a_{b_{i}},0),(a_{b_{i}+1},b_{b_{i}+1}),(a_{b_{i}+2},b_{b_{i}+2}),\dots ,(a_{n},b_{n}))}$يحتوي على أزواج من الأعداد الصحيحة غير السالبة وهو ثنائي الكتابة.

لاحظ أن الزوج${\displaystyle (a_{i},b_{i})}$بشكل تعسفي باستثناء الأزواج${\displaystyle (a_{j},0)}$إذا كانت القائمة المعطاة${\displaystyle S}$إذا كان الرسم البياني ثنائي الاتجاه، فسيتم تطبيق النظرية على الأكثر${\displaystyle n}$تحديد الأوقات في كل خطوة لاحقة${\displaystyle S:=S'}$تنتهي هذه العملية عندما تنتهي القائمة بأكملها${\displaystyle S'}$يتكون من${\displaystyle (0,0)}$أزواج. في كل خطوة من خطوات الخوارزمية، يتم إنشاء أقواس الرسم البياني الموجه ذي الرؤوس.${\displaystyle v_{1},\dots ,v_{n}}$أي إذا كان من الممكن تقليص القائمة${\displaystyle S}$ل${\displaystyle S'}$ثم نضيف الأقواس${\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$عندما تكون القائمة${\displaystyle S}$لا يمكن اختزالها إلى قائمة${\displaystyle S'}$في أي خطوة من خطوات هذا النهج، تثبت النظرية أن القائمة${\displaystyle S}$كلمة "من البداية" ليست ثنائية الحروف.

تعتمد الخوارزمية على النظرية التالية.

يترك${\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))}$لتكن قائمة منتهية من الأعداد الصحيحة غير السالبة بحيث${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$ودع${\displaystyle (a_{i},b_{i})}$ليكن زوجًا بحيث${\displaystyle (b_{i},a_{i})}$تكون القيمة القصوى فيما يتعلق بالترتيب المعجمي تحت جميع الأزواج${\displaystyle (b_{1},a_{1}),\dots ,(b_{n},a_{n})}$. قائمة${\displaystyle S}$تكون ثنائية الكتابة إذا وفقط إذا كانت القائمة المنتهية${\displaystyle S'=((a_{1}-1,b_{1}),\cdots ,(a_{b_{i}-1}-1,b_{b_{i}-1}),(a_{b_{i}},0),(a_{b_{i}+1},b_{b_{i}+1}),(a_{b_{i}+2},b_{b_{i}+2}),\dots ,(a_{n},b_{n}))}$يحتوي على أزواج من الأعداد الصحيحة غير السالبة وهو ثنائي الكتابة.

لاحظ أن القائمة${\displaystyle S}$يجب ألا تكون مرتبة ترتيبًا معجميًا كما في النسخة الأولى. إذا كانت القائمة المعطاة${\displaystyle S}$إذا كانت ثنائية الرسم، فسيتم تطبيق النظرية على الأكثر${\displaystyle n}$أوقات، وتحديد كل خطوة لاحقة${\displaystyle S:=S'}$تنتهي هذه العملية عندما تنتهي القائمة بأكملها${\displaystyle S'}$يتكون من${\displaystyle (0,0)}$أزواج. في كل خطوة من خطوات الخوارزمية، يتم إنشاء أقواس الرسم البياني الموجه ذي الرؤوس.${\displaystyle v_{1},\dots ,v_{n}}$أي إذا كان من الممكن تقليص القائمة${\displaystyle S}$ل${\displaystyle S'}$ثم يضيف المرء الأقواس${\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})}$عندما تكون القائمة${\displaystyle S}$لا يمكن اختزالها إلى قائمة${\displaystyle S'}$في أي خطوة من خطوات هذا النهج، تثبت النظرية أن القائمة${\displaystyle S}$كلمة "من البداية" ليست ثنائية الحروف.

• نظرية فولكرسون-تشين-أنستي

• كليتمان، دي جيه؛ وانغ، دي إل (1973)، "خوارزميات لإنشاء الرسوم البيانية والرسوم البيانية الموجهة ذات التكافؤات والعوامل المعطاة"، الرياضيات المتقطعة ، 6 : 79-88 ، doi : 10.1016/0012-365x(73)90037-x