Матрица Тутте

В теории графов , то Тутте матрица из графа G  = ( V ,  Е ) является матрица используется для определения существования идеального соответствия : то есть, набор ребер , который падает с каждой вершиной ровно один раз.

Если набор вершин равен, то матрица Тутте представляет собой матрицу A размера n  ×  n с элементами${\ Displaystyle V = \ {1,2, \ точки, п \}}$

${\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. )

Матрица Тутте названа в честь У. Т. Тутте и является обобщением матрицы Эдмондса для сбалансированного двудольного графа .

Ссылки [ править ]

• Р. Мотвани, П. Рагхаван (1995). Рандомизированные алгоритмы . Издательство Кембриджского университета. п. 167.
• Аллен Б. Такер (2004). Справочник по информатике . CRC Press. п. 12.19. ISBN 1-58488-360-X.
• WT Tutte (апрель 1947 г.). «Факторизация линейных графиков» (PDF) . J. London Math. Soc . 22 (2): 107–111. DOI : 10,1112 / jlms / s1-22.2.107 . Проверено 15 июня 2008 . CS1 maint: discouraged parameter (link)