Edmonds matrix (original) (raw)
In graph theory, the Edmonds matrix of a balanced bipartite graph with sets of vertices and is defined by where the xij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(Aij) in the xij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of . In addition, rank of is equal to the maximum matching size of .
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, the Edmonds matrix of a balanced bipartite graph with sets of vertices and is defined by where the xij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(Aij) in the xij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of . In addition, rank of is equal to the maximum matching size of . The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs. (en) En théorie des graphes, la matrice d'Edmonds d'un graphe biparti équilibré , c'est-à-dire tel que (où et sont les deux ensembles disjoints de ses sommets), est définie par : où sont les indéterminées. Une application de la matrice d'Edmonds d'un graphe biparti est que le graphe admet un couplage parfait si et seulement si le polynôme en les est non-identiquement nul. De plus, le nombre de couplage parfaits est égal au nombre de monômes dans le polynôme et est aussi égal au permanent de . Enfin, le rang de est égal au nombre de couplages maximaux de . Le nom matrice d'Edmonds provient du mathématicien Jack Edmonds. Sa généralisation aux graphes non-bipartis est la matrice de Tutte. * Portail des mathématiques (fr) |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=QKVY4mDivBEC&pg=PR5 |
| dbo:wikiPageID | 11415890 (xsd:integer) |
| dbo:wikiPageLength | 1565 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1121877933 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Perfect_matching dbr:Indeterminate_(variable) dbr:Tutte_matrix dbr:Permanent_(mathematics) dbc:Algebraic_graph_theory dbr:Graph_theory dbr:Rank_(linear_algebra) dbr:Jack_Edmonds dbr:Bipartite_graph dbr:Monomials dbr:Maximum_matching dbr:Set_(mathematics) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Combin-stub dbt:Matrix_classes |
| dct:subject | dbc:Algebraic_graph_theory |
| rdf:type | yago:WikicatMatrices yago:Abstraction100002137 yago:Arrangement107938773 yago:Array107939382 yago:Group100031264 yago:Matrix108267640 |
| rdfs:comment | In graph theory, the Edmonds matrix of a balanced bipartite graph with sets of vertices and is defined by where the xij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(Aij) in the xij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of . In addition, rank of is equal to the maximum matching size of . (en) En théorie des graphes, la matrice d'Edmonds d'un graphe biparti équilibré , c'est-à-dire tel que (où et sont les deux ensembles disjoints de ses sommets), est définie par : où sont les indéterminées. Une application de la matrice d'Edmonds d'un graphe biparti est que le graphe admet un couplage parfait si et seulement si le polynôme en les est non-identiquement nul. De plus, le nombre de couplage parfaits est égal au nombre de monômes dans le polynôme et est aussi égal au permanent de . Enfin, le rang de est égal au nombre de couplages maximaux de . * Portail des mathématiques (fr) |
| rdfs:label | Edmonds matrix (en) Matrice d'Edmonds (fr) |
| owl:sameAs | freebase:Edmonds matrix wikidata:Edmonds matrix dbpedia-fr:Edmonds matrix dbpedia-sl:Edmonds matrix https://global.dbpedia.org/id/4ixT3 |
| prov:wasDerivedFrom | wikipedia-en:Edmonds_matrix?oldid=1121877933&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Edmonds_matrix |
| is dbo:knownFor of | dbr:Jack_Edmonds |
| is dbo:wikiPageRedirects of | dbr:Edmonds_Matrix |
| is dbo:wikiPageWikiLink of | dbr:List_of_named_matrices dbr:Tutte_matrix dbr:Jack_Edmonds dbr:Schwartz–Zippel_lemma dbr:Edmonds_Matrix |
| is foaf:primaryTopic of | wikipedia-en:Edmonds_matrix |