خوارزمية إدموندز

تأخذ الخوارزمية كمدخل رسمًا بيانيًا موجهًا${\displaystyle D=\langle V,E\rangle }$أين${\displaystyle V}$هي مجموعة العقد و${\displaystyle E}$هي مجموعة الحواف الموجهة، رأس مميز${\displaystyle r\in V}$يُطلق عليه الجذر ، ووزن ذو قيمة حقيقية${\displaystyle w(e)}$لكل حافة${\displaystyle e\in E}$. إنها تُعيد شجرة ممتدة${\displaystyle A}$متجذرة في${\displaystyle r}$ذات الوزن الأدنى، حيث يُعرَّف وزن التفرع بأنه مجموع أوزان حوافه،${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$.

للخوارزمية وصف تكراري. ليكن${\displaystyle f(D,r,w)}$لنرمز إلى الدالة التي تُرجع شجرة ممتدة متجذرة عند${\displaystyle r}$بأقل وزن ممكن. نقوم أولاً بإزالة أي حافة من${\displaystyle E}$وجهتها هي${\displaystyle r}$. يمكننا أيضًا استبدال أي مجموعة من الحواف المتوازية (الحواف بين نفس زوج الرؤوس في نفس الاتجاه) بحافة واحدة وزنها يساوي الحد الأدنى لأوزان هذه الحواف المتوازية.

الآن، لكل عقدة${\displaystyle v}$بخلاف الجذر، ابحث عن الحافة الواردة إلى${\displaystyle v}$ذات الوزن الأدنى (مع كسر التعادلات بشكل عشوائي). نرمز إلى مصدر هذه الحافة بـ${\displaystyle \pi (v)}$إذا كانت مجموعة الحواف${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$إذا لم يحتوي على أي دورات، فإذن${\displaystyle f(D,r,w)=P}$.

خلاف ذلك،${\displaystyle P}$تحتوي على دورة واحدة على الأقل. اختر عشوائيًا إحدى هذه الدورات وسمّها${\displaystyle C}$نُعرّف الآن رسمًا بيانيًا موجهًا جديدًا مُرجّحًا${\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }$حيث الدورة${\displaystyle C}$يتم "تقليصها" إلى عقدة واحدة على النحو التالي:

عقد${\displaystyle V^{\prime }}$هي عقد${\displaystyle V}$ليس في${\displaystyle C}$بالإضافة إلى عقدة جديدة يُشار إليها بـ${\displaystyle v_{C}}$.

• لو${\displaystyle (u,v)}$يُعدّ ذلك ميزة في${\displaystyle E}$مع${\displaystyle u\notin C}$ و${\displaystyle v\in C}$(حافة تدخل في الدورة)، ثم قم بتضمينها في${\displaystyle E^{\prime }}$حافة جديدة${\displaystyle e=(u,v_{C})}$، وتحديد${\displaystyle w^{\prime }(e)=w(u,v)-w(\pi (v),v)}$.
• لو${\displaystyle (u,v)}$يُعدّ ذلك ميزة في${\displaystyle E}$مع${\displaystyle u\in C}$و${\displaystyle v\notin C}$(حافة تبتعد عن الدورة)، ثم قم بتضمينها في${\displaystyle E^{\prime }}$حافة جديدة${\displaystyle e=(v_{C},v)}$، وتحديد${\displaystyle w^{\prime }(e)=w(u,v)}$.
• لو${\displaystyle (u,v)}$يُعدّ ذلك ميزة في${\displaystyle E}$مع${\displaystyle u\notin C}$و${\displaystyle v\notin C}$(حافة غير مرتبطة بالدورة)، ثم قم بتضمينها في${\displaystyle E^{\prime }}$حافة جديدة${\displaystyle e=(u,v)}$، وتحديد${\displaystyle w^{\prime }(e)=w(u,v)}$.

لكل حافة في${\displaystyle E^{\prime }}$نتذكر أي حافة في${\displaystyle E}$وهو ما يتوافق مع.

الآن ابحث عن الحد الأدنى الذي يمتد عبر التفرع الشجري${\displaystyle A^{\prime }}$ل${\displaystyle D^{\prime }}$باستخدام استدعاء لـ${\displaystyle f(D^{\prime },r,w^{\prime })}$. منذ${\displaystyle A^{\prime }}$هي شجرة ممتدة، ولكل رأس حافة واردة واحدة فقط.${\displaystyle (u,v_{C})}$كن الميزة الفريدة القادمة لـ${\displaystyle v_{C}}$في${\displaystyle A^{\prime }}$هذا الضلع يقابل ضلعًا آخر${\displaystyle (u,v)\in E}$مع${\displaystyle v\in C}$قم بإزالة الحافة${\displaystyle (\pi (v),v)}$من${\displaystyle C}$، مما يكسر الحلقة. حدد كل حافة متبقية في${\displaystyle C}$لكل حافة في${\displaystyle A^{\prime }}$حدد حافتها المقابلة في${\displaystyle E}$والآن نُعرّف${\displaystyle f(D,r,w)}$أن تكون مجموعة الحواف المميزة، والتي تشكل الحد الأدنى من التفرع الشجري الممتد.

لاحظ ذلك${\displaystyle f(D,r,w)}$يتم تعريفها من حيث${\displaystyle f(D^{\prime },r,w^{\prime })}$، مع${\displaystyle D^{\prime }}$يحتوي على عدد أقل من الرؤوس من${\displaystyle D}$إيجاد${\displaystyle f(D,r,w)}$بالنسبة للرسم البياني ذي الرأس الواحد، يكون الأمر تافهاً (فهو ببساطة${\displaystyle D}$لذا فإن الخوارزمية المتكررة مضمونة الانتهاء.