Матрица Тутте - Tutte matrix

В теория графов, то Матрица Тутте А из график грамм = (V, E) это матрица используется для определения существования идеальное соответствие: то есть набор края что происходит с каждым вершина ровно один раз.

Если множество вершин ${displaystyle V={1,2,dots ,n}}$ то матрица Тутте является п × п матрица A с элементами

${displaystyle A_{ij}={egin{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�;;;;{mbox{otherwise}}end{cases}}}$

где Икс_ij неопределенны. В детерминант этого кососимметричный Тогда матрица является полиномом (от переменных Икс_ij, я ): это совпадает с квадратом пфаффианец матрицы А и отличен от нуля (как полином) тогда и только тогда, когда существует идеальное соответствие. (Этот многочлен не является Полином Тутте из грамм.)

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

Рекомендации

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