Все матрицы

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

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

$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 неопределенны. Определитель когда этой кососимметричной матрицы тогда является полиномом (от переменных xij ₎ , i <j : он совпадает с квадратом пфаффиана матрицы A и отличен от нуля (как полином) тогда и только тогда, существует идеальное совпадение. (Этот полином не является полиномом Тутте для G .)

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

Ссылки

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