المطابقة (نظرية الرسم البياني)

تنص نظرية كونيغ على أنه في الرسوم البيانية ثنائية الأجزاء، يكون حجم التطابق الأقصى مساوياً لحجم غطاء الرؤوس الأدنى. وبناءً على هذه النتيجة، يمكن حل مسائل غطاء الرؤوس الأدنى، ومجموعة الرؤوس المستقلة القصوى ، ومجموعة الرؤوس الثنائية القصوى في وقت متعدد الحدود للرسوم البيانية ثنائية الأجزاء.

توفر نظرية هول للزواج توصيفًا للرسوم البيانية ثنائية الأجزاء التي تحتوي على تطابق مثالي، بينما توفر نظرية توت حول التطابقات المثالية توصيفًا للرسوم البيانية العشوائية.

يُقدّم حسني منفرد ومالك وصفًا طيفيًا لعدد التطابقات في الرسم البياني على النحو التالي: ليكن${\displaystyle G}$كن رسمًا بيانيًا على${\displaystyle n}$الرؤوس، و${\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}$يكون${\displaystyle k}$أعداد تخيلية بحتة غير صفرية مميزة حيث${\displaystyle 2k\leq n}$ثم الرقم المطابق لـ${\displaystyle G}$يكون${\displaystyle k}$إذا وفقط إذا (أ) كانت هناك مصفوفة حقيقية متناظرة معكوسة${\displaystyle A}$مع رسم بياني${\displaystyle G}$والقيم الذاتية${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$و${\displaystyle n-2k}$(ب) جميع المصفوفات الحقيقية المتناظرة المائلة ذات الرسم البياني${\displaystyle G}$على الأكثر${\displaystyle 2k}$القيم الذاتية غير الصفرية . ^{[ 7 ]} لاحظ أن الرسم البياني (البسيط) لمصفوفة حقيقية متناظرة أو متناظرة معكوسة${\displaystyle A}$من النظام${\displaystyle n}$لديه${\displaystyle n}$الرؤوس والحواف المعطاة بواسطة العناصر غير الصفرية خارج القطر الرئيسي لـ${\displaystyle A}$.

إذا كان A و B تطابقين أقصى، فإن | A |  ≤  2| B | و | B |  ≤  2| A | . ولإثبات ذلك، لاحظ أن كل ضلع في B  \ A  يمكن أن يكون مجاورًا لضلعين على الأكثر في A  \ B  لأن A تطابق؛ علاوة على ذلك، فإن كل ضلع في A  \ B  مجاور لضلع في B  \ A  بحكم كون B تطابقًا أقصى ، وبالتالي

${\displaystyle |A\setminus B|\leq 2|B\setminus A|.}$

ونستنتج كذلك أن

${\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}$

على وجه الخصوص، يُظهر هذا أن أي تطابق أقصى هو تقريب من الدرجة الثانية لتطابق أقصى، وكذلك تقريب من الدرجة الثانية لتطابق أقصى أدنى. هذه المتباينة دقيقة: على سبيل المثال، إذا كان G مسارًا بثلاثة حواف وأربعة رؤوس، فإن حجم التطابق الأقصى الأدنى هو 1، وحجم التطابق الأقصى هو 2.

تُعدّ مسألة إيجاد التطابق الأمثل مشكلة أساسية في التحسين التوافقي . وتوجد لهذه المسألة خوارزميات متنوعة لأنواع مختلفة من الرسوم البيانية.

في الرسم البياني الثنائي غير الموزون ، تتمثل مشكلة التحسين في إيجاد تطابق ذي عدد عناصر أقصى . تُحل هذه المشكلة بواسطة خوارزمية هوبكروفت-كارب في زمن O ( √VE ) ، وهناك خوارزميات عشوائية أكثر كفاءة ، وخوارزميات تقريبية ، وخوارزميات لفئات خاصة من الرسوم البيانية مثل الرسوم البيانية المستوية الثنائية ، كما هو موضح في المقالة الرئيسية.

في الرسم البياني الثنائي الموزون ، تتمثل مشكلة التحسين في إيجاد تطابق ذي وزن أقصى؛ أما المشكلة المقابلة فهي إيجاد تطابق ذي وزن أدنى. تُعرف هذه المشكلة غالبًا باسم التطابق الثنائي الموزون الأقصى ، أو مشكلة التخصيص . تحل خوارزمية هنغاريا مشكلة التخصيص، وكانت من أوائل خوارزميات التحسين التوافقي. تستخدم هذه الخوارزمية بحثًا مُعدَّلًا عن أقصر مسار في خوارزمية المسار المُعزِّز. إذا استُخدمت خوارزمية بيلمان-فورد لهذه الخطوة، يصبح زمن تشغيل خوارزمية هنغاريا أقل.${\displaystyle O(V^{2}E)}$أو يمكن نقل تكلفة الحافة مع إمكانية تحقيق${\displaystyle O(V^{2}\log {V}+VE)}$وقت التشغيل باستخدام خوارزمية ديكسترا وكومة فيبوناتشي . ^{[ 8 ]}

في الرسم البياني الموزون غير الثنائي الأجزاء ، يمكن حل مشكلة مطابقة الوزن الأقصى في وقت${\displaystyle O(V^{2}E)}$باستخدام خوارزمية إدموندز بلوسوم .

يمكن إيجاد التطابق الأمثل باستخدام خوارزمية جشعة بسيطة . التطابق الأمثل هو تطابق أمثل، وبالتالي من الممكن إيجاد أكبر تطابق أمثل في وقت متعدد الحدود. كما يمكن إيجاد التطابق الأمثل باستخدام خوارزميات ضرب المصفوفات السريعة في وقت${\displaystyle O({n^{\أوميغا }})}$ل${\displaystyle ~2.37\leq \أوميغا <3}$^{[ 9 ]} . ومع ذلك، لا توجد خوارزمية زمنية متعددة الحدود معروفة لإيجادتطابق أقصى أدنى، أي تطابق أقصى يحتوي علىأقلعدد ممكن من الحواف.

التطابق الأقصى ذو k حافة هو مجموعة هيمنة حواف تحتوي على k حافة. ​​وعلى العكس، إذا توفرت لدينا مجموعة هيمنة حواف دنيا ذات k حافة، فيمكننا إنشاء تطابق أقصى ذي k حافة في وقت متعدد الحدود. لذا، فإن مسألة إيجاد تطابق أقصى أدنى تساوي في جوهرها مسألة إيجاد مجموعة هيمنة حواف دنيا. ^{[ 10 ]} من المعروف أن كلتا مسألتي التحسين هاتين من المسائل الصعبة من فئة NP ؛ وتُعدّ صيغ القرار لهاتين المسألتين أمثلة كلاسيكية على مسائل NP-كاملة . ^{[ 11 ]} يمكن تقريب كلتا المسألتين بمعامل 2 في وقت متعدد الحدود: ببساطة، إيجاد تطابق أقصى M عشوائي . ^{[ 12 ]}

يُعرف عدد التطابقات في الرسم البياني بمؤشر هوسويا . يُعد حساب هذا المؤشر مسألةً كاملةً من فئة #P ، حتى بالنسبة للرسوم البيانية ثنائية الأجزاء. ^{[ 13 ]} كما يُعد حساب التطابقات التامة مسألةً كاملةً من فئة #P ، حتى في الرسوم البيانية ثنائية الأجزاء ، لأن حساب العنصر الدائم لمصفوفة ثنائية عشوائية (وهي مسألة أخرى كاملة من فئة #P) يُعادل حساب عدد التطابقات التامة في الرسم البياني ثنائي الأجزاء الذي تكون فيه المصفوفة المعطاة هي مصفوفة التجاور الثنائي . مع ذلك، توجد طريقة تقريب عشوائية ذات زمن متعدد الحدود لحساب عدد التطابقات في الرسوم البيانية ثنائية الأجزاء. ^{[ 14 ]} تنص نظرية كاستيلين البارزة على أنه يمكن حساب عدد التطابقات التامة في رسم بياني مستوٍ بدقة في زمن متعدد الحدود باستخدام خوارزمية FKT .

يُعطى عدد التطابقات التامة في الرسم البياني الكامل K _{_n} (حيث n عدد زوجي) بالمعامل المزدوج ( n - 1)!!. ^{[ 15 ]} أما عدد التطابقات في الرسوم البيانية الكاملة، دون اشتراط أن تكون التطابقات تامة، فيُعطى بأرقام الهواتف . ^{[ 16 ]}  

يُعرف عدد التطابقات الكاملة في الرسم البياني أيضًا باسم هافنيان مصفوفة التجاور الخاصة به .

تتمثل إحدى المشكلات الأساسية في نظرية المطابقة في إيجاد جميع الحواف في رسم بياني مُعطى والتي يمكن تمديدها لتحقيق مطابقة قصوى في الرسم البياني (وتُسمى هذه الحواف بالحواف القابلة للمطابقة القصوى ، أو الحواف المسموح بها ). وتشمل الخوارزميات المُستخدمة لحل هذه المشكلة ما يلي:

• بالنسبة للرسوم البيانية العامة، خوارزمية حتمية في وقت${\displaystyle O(VE)}$وخوارزمية عشوائية في الوقت${\displaystyle {\tilde {O}}(V^{2.376})}$[ ^{17 ] [ 18 ]​}
• بالنسبة للرسوم البيانية ثنائية الأجزاء، إذا تم العثور على تطابق أقصى واحد، فإن الخوارزمية الحتمية تعمل في وقت${\displaystyle O(V+E)}$[ ^{19 ]​}

تم النظر في مشكلة تطوير خوارزمية عبر الإنترنت للمطابقة لأول مرة من قبل ريتشارد إم كارب ، وأوميش فازيراني ، وفيجاي فازيراني في عام 1990. ^{[ 20 ]}

في بيئة الإنترنت، تصل العقد على أحد جانبي الرسم البياني الثنائي ("العملاء") واحدة تلو الأخرى، ويجب إما مطابقتها فورًا مع الجانب الآخر من الرسم البياني ("الخوادم") أو تجاهلها. يُعد هذا تعميمًا طبيعيًا لمسألة السكرتير ، وله تطبيقات في مزادات الإعلانات عبر الإنترنت. خوارزمية جشعة بسيطة هي 1/2- تنافسية . في حالة التعظيم غير الموزون مع نموذج وصول عشوائي، قدم كارب وفازيراني وفازيراني خوارزمية عشوائية تحقق نسبة تنافسية قدرها 0.632 . تم تحسين الحد لاحقًا إلى 0.696 . ^{[ 21 ]} دُرست المسألة أيضًا في نموذج حيث يمكن للعملاء تبديل الخوادم لتحسين المطابقة، والهدف هو ترشيد عدد عمليات التبديل مع تحقيق أقصى قدر من المطابقة. ^{[ 22 ]}

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

• تتمحور مشكلة التخرج حول اختيار الحد الأدنى من الفصول الدراسية من المتطلبات المعطاة للتخرج.
• تتضمن مشكلة نقل هيتشكوك المطابقة الثنائية كمشكلة فرعية.
• تتضمن مشكلة تماثل الشجرة الفرعية المطابقة الثنائية كمشكلة فرعية.