مصفوفة توتي

في نظرية الرسم البياني ، مصفوفة Tutte A للرسم البياني G  =  ( V , E ) هي مصفوفة تستخدم لتحديد وجود تطابق مثالي : أي مجموعة من الحواف التي تتصل بكل رأس مرة واحدة بالضبط. 

إذا كانت مجموعة الرؤوس هي${\displaystyle V=\{1,2,\dots ,n\}}$إذن، مصفوفة توت هي مصفوفة متناظرة معكوسة من الرتبة n × n ، وقيمها A

${\displaystyle A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i<j\\-x_{ji}\;\;{\mbox{if}}\;(i,j)\in E{\mbox{ and }}i>j\\0\;\;\;\;{\mbox{otherwise}}\end{cases}}}$

حيث تكون x_{_ij} متغيرات غير محددة . يكون محدد هذه المصفوفة متعدد حدود (في المتغيرات x _{_ij} ، حيث i < j ): يتطابق هذا المحدد مع مربع بفافيان المصفوفة A ، ويكون غير صفري (كمتعدد حدود) إذا وفقط إذا وُجد تطابق تام. (متعدد الحدود هذا ليس متعدد حدود توت للمصفوفة G ).   

سميت مصفوفة Tutte على اسم WT Tutte ، وهي تعميم لمصفوفة Edmonds للرسم البياني الثنائي المتوازن .

• ر. موتاني، ب. راغافان (1995). الخوارزميات العشوائية . مطبعة جامعة كامبريدج. ص  167.
• ألين ب. تاكر (2004). دليل علوم الحاسوب . دار نشر سي آر سي. ص  12.19. رقم ISBN 1-58488-360-X.
• دبليو تي توت (أبريل 1947). "تحليل الرسوم البيانية الخطية" (ملف PDF) . مجلة جمعية لندن الرياضية 22 (2): 107-111 . doi : 10.1112/jlms/s1-22.2.107 . تاريخ الاسترجاع: 15 يونيو 2008 .