متعدد الأوجه متطابق

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

في نظرية المخططات ، يُعدّ متعدد السطوح المطابق لمخطط معين شكلاً هندسياً يُمثل المطابقات الممكنة في المخطط . وهو متعدد سطوح محدب، كل زاوية من زواياه تُقابل مطابقة. وله أهمية نظرية كبيرة في نظرية المطابقة. [ 1 ] : 273-285

التصفيات

متجهات ومصفوفات الوقوع

ليكن G = ( V , E ) رسمًا بيانيًا يحتوي على n = | V | عقدة و m = | E | حافة.

لكل مجموعة جزئية U من الرؤوس، يكون متجه وقوعها 1 U متجهًا بحجم n ، حيث يكون العنصر v مساويًا لـ 1 إذا كانت العقدة v تنتمي إلى U ، و 0 فيما عدا ذلك. وبالمثل، لكل مجموعة جزئية F من الحواف، يكون متجه وقوعها 1 F متجهًا بحجم m ، حيث يكون العنصر e مساويًا لـ 1 إذا كانت الحافة e تنتمي إلى F، و 0 فيما عدا ذلك.

لكل عقدة v في V ، يُرمز إلى مجموعة الحواف في E المجاورة لـ v بـ E ( v ). بالتالي، كل متجه 1 ∈ E(v) هو متجه من الرتبة 1× m، حيث يكون العنصر e مساويًا لـ 1 إذا كانت الحافة e مجاورة لـ v، و 0 فيما عدا ذلك. مصفوفة الوقوع للرسم البياني، والتي يُرمز لها بـ AG ، هي مصفوفة من الرتبة n × m، حيث يُمثل كل صف v متجه الوقوع 1 ∈ E(V) . بعبارة أخرى، كل عنصر v ، e في المصفوفة يساوي 1 إذا كانت العقدة v مجاورة للحافة e ، و 0 فيما عدا ذلك.

فيما يلي ثلاثة أمثلة على مصفوفات الوقوع: الرسم البياني المثلثي (دورة طولها 3)، والرسم البياني المربع (دورة طولها 4)، والرسم البياني الكامل على 4 رؤوس.

(110101011) ، (1100011000111001) ، (110010011001001110100101){\displaystyle {\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0\\0&1&1&0\\0&0&1&1\\1&0&0&1\\\end{pmatrix}}~,~{\begin{pmatrix}1&1&0&0&1&0\\0&1&1&0&0&1\\0&0&1&1&1&0\\1&0&0&1&0&1\\\end{pmatrix}}}

البرامج الخطية

لكل مجموعة جزئية F من الحواف، يمثل حاصل الضرب النقطي 1 E(v) · 1 F عدد الحواف في F المجاورة لـ v . لذلك، فإن العبارات التالية متكافئة:

  • تمثل مجموعة فرعية F من الحواف تطابقًا في G؛
  • لكل عقدة v في V : 1 E(v) · 1 F ≤ 1.
  • A G · 1 F ≤ 1 V .

عدد عناصر مجموعة F من الحواف هو حاصل الضرب النقطي 1 E · 1 F. لذلك، فإن مطابقة الحد الأقصى لعدد العناصر في G تُعطى بواسطة برنامج البرمجة الخطية الصحيحة التالي :

تعظيم 1 E · x

مع مراعاة: x في {0,1} م

__________ A G · x ≤ 1 V .

متعدد الوجوه المطابق الجزئي

متعدد السطوح للمطابقة الكسرية للرسم البياني G ، والذي يرمز له بـ FMP( G )، هو متعدد السطوح المحدد بواسطة تخفيف البرنامج الخطي أعلاه، حيث يمكن أن يكون كل x كسرًا وليس مجرد عدد صحيح:

تعظيم 1 E · x

مع مراعاة الشروط التالية: x ≥ 0 E

__________ A G · x ≤ 1 V .

هذا برنامج خطي . يحتوي على m قيدًا من نوع "على الأقل صفر" و n قيدًا من نوع "أقل من واحد". مجموعة حلوله الممكنة هي متعدد سطوح محدب . كل نقطة في هذا المتعدد السطوح تمثل تطابقًا جزئيًا . على سبيل المثال، في الرسم البياني المثلثي، توجد 3 أضلاع، ويحتوي البرنامج الخطي المقابل على القيود الستة التالية:

تعظيم x 1 + x 2 + x 3

مع مراعاة الشروط التالية: x 1 ≥0، x 2 ≥0، x 3 ≥0 .

__________ x 1 +x 2 ≤1 , x 2 +x 3 ≤1, x 3 +x 1 ≤1.

تمثل هذه المجموعة من المتباينات متعدد الوجوه في R 3 - الفضاء الإقليدي ثلاثي الأبعاد .

للمضلع خمس زوايا ( نقاط قصوى ). هذه النقاط هي التي تحقق التساوي في ثلاث من أصل ست متباينات أساسية. الزوايا هي (0,0,0)، (1,0,0)، (0,1,0)، (0,0,1)، و(1/2,1/2,1/2). [ 2 ] تمثل الزاوية الأولى (0,0,0) التطابق البسيط (الفارغ). أما الزوايا الثلاث التالية (1,0,0)، (0,1,0)، (0,0,1) فتمثل ثلاثة تطابقات من الحجم 1. الزاوية الخامسة (1/2,1/2,1/2) لا تمثل تطابقًا، بل تمثل تطابقًا كسريًا يكون فيه كل ضلع "نصفه داخل ونصفه خارج". لاحظ أن هذا هو أكبر تطابق كسري في هذا الرسم البياني، إذ يبلغ وزنه 3/2، على عكس التطابقات الصحيحة الثلاثة التي يبلغ حجمها 1 فقط.

كمثال آخر، في الدورة الرباعية، توجد أربعة حواف. يحتوي برنامج البرمجة الخطية المقابل على 8 قيود (4+4=8). يمثل FMP متعدد سطوح محدب في الفضاء الإقليدي رباعي الأبعاد ( R⁴ ) . زوايا هذا المتعدد هي (0,0,0,0)، (1,0,0,0)، (0,1,0,0)، (0,0,1,0)، (0,0,0,1)، (1,0,1,0)، (0,1,0,1). تمثل كل من الزاويتين الأخيرتين تطابقًا بحجم 2، وهو تطابق أقصى. لاحظ أن جميع الزوايا في هذه الحالة لها إحداثيات صحيحة.

متعدد السطوح المتطابق المتكامل

متعدد السطوح المطابق التكاملي (يسمى عادةً متعدد السطوح المطابق فقط ) للرسم البياني G ، ويرمز له بـ MP( G )، هو متعدد السطوح الذي تمثل زواياه متجهات الوقوع للمطابقات التكاملية في G.

تُحتوى MP( G ) دائمًا في FMP( G ). في الأمثلة أعلاه:

  • تقع نقطة MP للرسم البياني للمثلث بشكل صارم في نقطة FMP الخاصة به، لأن نقطة MP لا تحتوي على الزاوية غير الصحيحة (1/2، 1/2، 1/2).
  • نقطة الذروة للرسم البياني ذي الدورة الرباعية مطابقة لنقطة الذروة النهائية، لأن جميع زوايا نقطة الذروة النهائية صحيحة.

المضلعات المتطابقة في الرسم البياني ثنائي الأجزاء

المثال أعلاه هو حالة خاصة من النظرية العامة التالية: [ 1 ] : 274

G هو رسم بياني ثنائي الأجزاء إذا وفقط إذا MP( G ) = FMP( G ) إذا وفقط إذا كانت جميع زوايا FMP( G ) لها إحداثيات صحيحة فقط.

يمكن إثبات هذه النظرية بعدة طرق.

البرهان باستخدام المصفوفات

عندما تكون G ثنائية الأجزاء، فإن مصفوفة وقوعها A<sub> G</sub> تكون أحادية القيمة تمامًا - أي أن كل مصفوفة فرعية مربعة منها لها محدد يساوي 0 أو +1 أو -1. ويُبرهن على ذلك بالاستقراء على k - وهو حجم المصفوفة الفرعية (والتي نرمز لها بـ K ). الأساس k  =  1 ينتج من تعريف A <sub> G</sub> - فكل عنصر فيها إما 0 أو 1. أما بالنسبة لـ k > 1، فهناك عدة حالات:

  • إذا كان للمصفوفة K عمود يتكون فقط من أصفار، فإن det K = 0.
  • إذا كان K يحتوي على عمود واحد بقيمة 1، فيمكن توسيع det K حول هذا العمود وهو يساوي إما +1 أو -1 مضروبًا في محدد مصفوفة ( k  −  1) × ( k  −  1)، والذي يكون، وفقًا لفرضية الاستقراء، 0 أو +1 أو  −1.
  • بخلاف ذلك، يحتوي كل عمود في المصفوفة K على قيمتين 1. ولأن الرسم البياني ثنائي الأجزاء، يمكن تقسيم الصفوف إلى مجموعتين فرعيتين، بحيث تحتوي كل مجموعة فرعية على قيمة 1 واحدة في المجموعة العلوية وأخرى في المجموعة السفلية. هذا يعني أن مجموع المجموعتين الفرعيتين يساوي 1E ناقص متجه من | E | قيمة 1. وهذا يعني أن صفوف المصفوفة K مرتبطة خطيًا، وبالتالي فإن det K = 0.   

على سبيل المثال، في الدورة الرباعية (وهي ثنائية الأجزاء)، يكون det A G = 1. في المقابل، في الدورة الثلاثية (وهي ليست ثنائية الأجزاء)، يكون det A G = 2.    

كل زاوية من زوايا FMP( G ) تحقق مجموعة من m متباينات مستقلة خطيًا مع المساواة. لذا، لحساب إحداثيات الزوايا، علينا حل نظام معادلات مُعرَّف بمصفوفة فرعية مربعة من AG . وفقًا لقاعدة كرامر ، يكون الحل عددًا نسبيًا مقامه هو محدد هذه المصفوفة الفرعية. يجب أن يكون هذا المحدد إما +1 أو -1؛ وبالتالي، يكون الحل متجهًا صحيحًا. لذلك ، جميع إحداثيات الزوايا أعداد صحيحة.

بحسب قيود "أقل من واحد" n ، فإن إحداثيات الزاوية إما 0 أو 1؛ لذلك فإن كل زاوية هي متجه وقوع لمطابقة تكاملية في G. ومن ثم فإن FMP( G )  =  MP( G ).

أوجه متعدد السطوح المتطابق

وجه متعدد السطوح هو مجموعة نقاطه التي تحقق متباينة أساسية تُعرّف متعدد السطوح مع المساواة. إذا كان متعدد السطوح ذا بُعد d ، فإن أوجهه ذات بُعد ( d  -  1). لأي رسم بياني G ، تُعطى أوجه MP( G ) بالمتباينات التالية: [ 1 ] : 275-279

  • x ≥ 0 E
  • 1 E ( v ) · x ≤ 1 (حيث v هو رأس غير معزول بحيث إذا كان لـ v جار واحد فقط u ، ​​فإن { u ، v } هو مكون متصل من G ، وإذا كان لـ v جارين بالضبط ، فإنهما ليسا متجاورين).
  • 1 E ( S ) · x ≤ (| S | − 1)/2 (حيث S يمتد على رسم بياني فرعي حرج للعامل متصل بـ 2. )

متعدد الأوجه متطابق تمامًا

متعدد السطوح للمطابقة الكاملة للرسم البياني G ، ويرمز له بـ PMP( G )، هو متعدد سطوح تمثل زواياه متجهات وقوع المطابقات الكاملة الصحيحة في G. [ 1 ] : 274 من الواضح أن PMP( G ) مُحتوى في MP( G )؛ في الواقع، PMP(G) هو وجه MP( G ) المحدد بالمساواة التالية:

1 E · x = n /2.

أثبت إدموندز [ 3 ] أنه بالنسبة لكل رسم بياني G، يمكن وصف PMP(G) بالقيود التالية:

1 E(v) · x = 1 لجميع v في V (-- يوجد ضلع واحد فقط مجاور لـ v في المطابقة)

1 E(W) · x ≥ 1 لكل مجموعة جزئية W من V حيث |W| فردي (أي يجب أن يربط ضلع واحد على الأقل W بـ V\W). تُسمى هذه القيود قيود القطع الفردي .

x ≥ 0 E

باستخدام هذا التوصيف ومبرهنة فاركاس ، يُمكن الحصول على توصيف دقيق للرسوم البيانية التي تتمتع بتطابق تام. [ 4 ] : ​​206. من خلال حل مسائل خوارزمية على مجموعات محدبة ، يُمكن إيجاد تطابق تام بأقل وزن. [ 4 ] : ​​206-208

انظر أيضاً

مراجع

  1. 1 2 3 4 لوفاسز, لازلو ; بلامر ، دكتوراه في الطب (1986)، نظرية المطابقة ، حوليات الرياضيات المنفصلة، ​​المجلد.  29، شمال هولندا، ISBN 0-444-87916-1، MR 0859549 
  2. ↑ "1 متعدد السطوح المطابق ثنائي الأجزاء، متعدد السطوح المطابق المستقر x1 x2 x3 المحاضرة 10: فبراير تنزيل عرض تقديمي" . slideplayer.com . تم الاسترجاع في 17-07-2020 .
  3. ↑ إدموندز، جاك (يناير 1965). "المطابقة القصوى ومتعدد السطوح ذو الرؤوس 0،1" (ملف PDF) . مجلة البحوث التابعة للمكتب الوطني للمعايير، القسم ب . 69ب (1 و2): 125. doi : 10.6028/jres.069B.013 . ISSN 0022-4340 . 
  4. 1 2 جروتشيل, مارتن ; الأماكن القريبة : شريفر ، ألكسندر (1993)، الخوارزميات الهندسية والتحسين التوافقي ، الخوارزميات والتوافقيات، المجلد. 2 ( الطبعة الثانية)، Springer-Verlag، برلين، دوى : 10.1007 / 978-3-642-78240-4 ، ISBN   978-3-642-78242-8MR 1261419​