مصفوفة أحادية النمط

1. مصفوفة الوقوع غير الموجهة للرسم البياني ثنائي الأجزاء ، وهي مصفوفة المعاملات للمطابقة ثنائية الأجزاء ، أحادية المعامل تمامًا (TU). (مصفوفة الوقوع غير الموجهة للرسم البياني غير ثنائي الأجزاء ليست أحادية المعامل تمامًا). وبشكل أعم، في ملحق ورقة بحثية لهيلر وتومبكينز، ^{[ 2 ]} أثبت كل من إيه جيه هوفمان ودي غيل ما يلي. ليكن${\displaystyle A}$لتكن مصفوفة من الرتبة m × n يمكن تقسيم صفوفها إلى مجموعتين منفصلتين${\displaystyle B}$و ${\displaystyle C}$إذن، فإن الشروط الأربعة التالية مجتمعة كافية لكي تكون المصفوفة A أحادية النمط تمامًا:

• كل مدخل في${\displaystyle A}$هو 0 أو +1 أو -1؛
• كل عمود من${\displaystyle A}$يحتوي على مدخلين غير صفريين على الأكثر (أي +1 أو -1)؛
• إذا كان هناك مدخلان غير صفريين في عمود من${\displaystyle A}$إذا كانت لها نفس الإشارة، فإن صف الواحد يكون في${\displaystyle B}$والآخر في${\displaystyle C}$؛
• إذا كان هناك مدخلان غير صفريين في عمود من${\displaystyle A}$إذا كانت إشارات كل منهما متعاكسة، فإن صفوف كليهما تكون في${\displaystyle B}$أو كليهما في${\displaystyle C}$.

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

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

3. خاصية الواحدات المتتالية: إذا كانت المصفوفة A مصفوفة ثنائية (أو يمكن تحويلها إلى) مصفوفة ثنائية (0-1) بحيث تظهر الواحدات متتالية في كل صف، فإن A تكون مصفوفة منقولة من نوع TU. (وينطبق الأمر نفسه على الأعمدة لأن منقولة مصفوفة TU هي أيضًا مصفوفة TU). ^{[ 4 ]}

٤. كل مصفوفة شبكة هي شجرة من نوع TU. تمثل صفوف مصفوفة الشبكة شجرة T = ( V , R ) ، ولكل قوس منها اتجاه عشوائي (ليس بالضرورة وجود رأس جذر r بحيث تكون الشجرة "متجذرة في r " أو "خارجة من r "). تمثل الأعمدة مجموعة أخرى C من الأقواس على نفس مجموعة الرؤوس V. لحساب القيمة في الصف R والعمود C = st ، انظر إلى المسار P من s إلى t في T ؛ عندها تكون القيمة:

• +1 إذا ظهر القوس R للأمام في P ،
• -1 إذا ظهر القوس R معكوسًا في P ،
• 0 إذا لم يظهر القوس R في P.

انظر المزيد في Schrijver (2003).

5. أثبت غويلا-حوري أن المصفوفة تكون من نوع TU إذا وفقط إذا كان لكل مجموعة جزئية R من الصفوف، يوجد تعيين${\displaystyle s:R\to \pm 1}$من الإشارات إلى الصفوف بحيث يكون المجموع الموقّع${\displaystyle \sum _{r\in R}s(r)r}$(وهو متجه صف له نفس عرض المصفوفة) يحتوي على جميع عناصره في${\displaystyle \{0,\pm 1\}}$(أي أن المصفوفة الفرعية للصف تحتوي على اختلاف لا يتجاوز واحدًا). ​​وقد تم إثبات هذا والعديد من خصائص "إذا وفقط إذا" الأخرى في Schrijver (1998).

6. أثبت هوفمان وكروسكال ^{[ 5 ]} النظرية التالية. لنفترض${\displaystyle G}$هو رسم بياني موجه بدون دوائر ثنائية،${\displaystyle P}$هي مجموعة جميع المسارات الثنائية في${\displaystyle G}$، و${\displaystyle A}$هي مصفوفة الحدوث 0-1 لـ${\displaystyle V(G)}$عكس${\displaystyle P}$. ثم${\displaystyle A}$تكون أحادية النمط تمامًا إذا وفقط إذا كانت كل دورة بسيطة ذات اتجاه عشوائي في${\displaystyle G}$يتكون من أقواس متناوبة للأمام والخلف.

7. لنفترض أن مصفوفة ما تحتوي على 0-(${\displaystyle \pm }$1) المدخلات، وفي كل عمود، تكون المدخلات غير متناقصة من الأعلى إلى الأسفل (أي أن جميع القيم -1 في الأعلى، ثم الأصفار، ثم الآحاد في الأسفل). وقد أظهر فوجيشيغي ^{[ 6 ]} أن المصفوفة تكون TU إذا وفقط إذا كان لكل مصفوفة فرعية 2×2 محدد في${\displaystyle 0,\pm 1}$.

8. أثبت سيمور (1980) ^{[ 7 ]} توصيفًا كاملاً لجميع مصفوفات TU، والتي سنصفها هنا بشكل غير رسمي فقط. تنص نظرية سيمور على أن المصفوفة تكون TU إذا وفقط إذا كانت مزيجًا طبيعيًا معينًا من بعض مصفوفات الشبكة وبعض نسخ مصفوفة TU معينة بحجم 5×5.

1. المصفوفة التالية أحادية القيمة تمامًا:

${\displaystyle A=\left[{\begin{array}{rrrrrr}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\end{array}}\right].}$

تنشأ هذه المصفوفة كمصفوفة معاملات القيود في صياغة البرمجة الخطية لمسألة التدفق الأقصى على الشبكة التالية:

2. أي مصفوفة من الشكل

${\displaystyle A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].}$

ليست أحادية النمط تمامًا ، لأنها تحتوي على مصفوفة فرعية مربعة ذات محدد  −2.