Edmondsonova matrika

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

Edmondsova matrika v teoriji grafov za uravnoteženi dvodelni graf z oznako , kjer sta in množici vozlišč
je enaka

kjer so

  • nedoločene vrednosti

Imenuje se po kanadskem matematiku Jacku Edmondsu (rojen 1934).

Ena izmed uporab Edmondsonove matrike za dvodelni graf je v tem, da graf omogoča polno ujemanje, če in samo, če polinom ni enak nič.

Tuttejeva matrika je posplošitev Edmondsonove matrike na nedvodelne grafe.