Edmondsova matice - Edmonds matrix

v teorie grafů, Edmondsova matice ${displaystyle A}$ vyváženého bipartitní graf ${displaystyle G (U, V, E)}$ s sady vrcholů ${displaystyle U = {u_ {1}, u_ {2}, tečky, u_ {n}}}$ a ${displaystyle V = {v_ {1}, v_ {2}, tečky, v_ {n}}}$ je definováno

${displaystyle A_ {ij} = left {{egin {array} {ll} x_ {ij} & (u_ {i}, v_ {j}) in E 0 & (u_ {i}, v_ {j}) otin Eend {array}} hned.}$

Kde X_ij jsou neurčí. Jednou z aplikací Edmondsovy matice bipartitního grafu je, že graf připouští a perfektní shoda právě tehdy, když polynom det (A_ij) v X_ij není identicky nula. Kromě toho se počet dokonalých shod rovná počtu monomials v polynomu det (A), a rovná se také trvalý z ${displaystyle A}$. Navíc, hodnost z ${displaystyle A}$ se rovná maximální shoda velikost ${displaystyle G}$.

Edmondsova matice je pojmenována po Jack Edmonds. The Tutte matrix je zobecnění na non-bipartitní grafy.

Reference

• R. Motwani, P. Raghavan (1995). Randomizované algoritmy. Cambridge University Press. p. 167. ISBN  9780521474658.
• Allen B. Tucker (2004). Příručka k počítačové vědě. CRC Press. p. 12.19. ISBN  1-58488-360-X.

Tento kombinatorika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.