Tutte matrix (original) (raw)
グラフ理論において、グラフG = (V, E) のタット行列（タットぎょうれつ、英: Tutte matrix）Aは、完全マッチング、すなわち、それぞれの頂点と厳密に一度接続する辺の集合の存在を決定するために使われる行列である。 頂点の集合をとすると、タット行列は成分 を持つn × n行列Aである。上式においてxijは不定元である。この歪対称行列の行列式は多項式である（xij、i < jにおいて）: これは行列Aのパフィアンの二乗と一致し、完全マッチングが存在する時かつその時に限り（多項式として）非ゼロである（この多項式はGのではない）。 タット行列はに因んで命名され、釣り合い型2部グラフについてのの一般化である。
| Property | Value |
|---|---|
| dbo:abstract | En théorie des graphes, la matrice de Tutte d'un graphe est une matrice utilisée pour déterminer l'existence d'un couplage parfait, soit d'un ensemble d'arêtes incidentes à chaque sommet exactement une fois. Si l'ensemble des sommets est , alors la matrice de Tutte de est une matrice de taille ayant pour coefficients : où sont les indéterminées. Le déterminant de cette matrice antisymétrique est un polynôme (en les variables ) : il coïncide avec le déterminant pfaffien de et est non-identiquement nul si et seulement si un couplage parfait existe. (Ce polynôme ne doit pas être confondu avec le polynôme de Tutte de ). La nom matrice de Tutte provient du mathématicien W. T. Tutte, et est la généralisation de la matrice d'Edmonds pour les graphes bipartis équilibrés. * Portail des mathématiques (fr) In graph theory, the Tutte matrix A of a graph G = (V, E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vertices is then the Tutte matrix is an n × n matrix A with entries where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, i < j ): this coincides with the square of the pfaffian of the matrix A and is non-zero (as a polynomial) if and only if a perfect matching exists. (This polynomial is not the Tutte polynomial of G.) The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph. (en) グラフ理論において、グラフG = (V, E) のタット行列（タットぎょうれつ、英: Tutte matrix）Aは、完全マッチング、すなわち、それぞれの頂点と厳密に一度接続する辺の集合の存在を決定するために使われる行列である。 頂点の集合をとすると、タット行列は成分 を持つn × n行列Aである。上式においてxijは不定元である。この歪対称行列の行列式は多項式である（xij、i < jにおいて）: これは行列Aのパフィアンの二乗と一致し、完全マッチングが存在する時かつその時に限り（多項式として）非ゼロである（この多項式はGのではない）。 タット行列はに因んで命名され、釣り合い型2部グラフについてのの一般化である。 (ja) |
| dbo:wikiPageExternalLink | http://jlms.oxfordjournals.org/cgi/reprint/s1-22/2/107.pdf%7Ctitle= |
| dbo:wikiPageID | 18305460 (xsd:integer) |
| dbo:wikiPageLength | 1941 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1027628526 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Determinant dbr:Perfect_matching dbc:Matching_(graph_theory) dbr:Matrix_(mathematics) dbr:Graph_(discrete_mathematics) dbr:Pfaffian dbc:Algebraic_graph_theory dbc:Matrices dbr:W._T._Tutte dbr:Edge_(graph_theory) dbr:Edmonds_matrix dbr:Graph_theory dbr:Bipartite_graph dbr:Skew-symmetric_matrix dbr:Vertex_(graph_theory) dbr:Tutte_polynomial |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Combin-stub dbt:Matrix_classes |
| dcterms:subject | dbc:Matching_(graph_theory) dbc:Algebraic_graph_theory dbc:Matrices |
| rdf:type | yago:WikicatMatrices yago:Abstraction100002137 yago:Arrangement107938773 yago:Array107939382 yago:Group100031264 yago:Matrix108267640 |
| rdfs:comment | グラフ理論において、グラフG = (V, E) のタット行列（タットぎょうれつ、英: Tutte matrix）Aは、完全マッチング、すなわち、それぞれの頂点と厳密に一度接続する辺の集合の存在を決定するために使われる行列である。 頂点の集合をとすると、タット行列は成分 を持つn × n行列Aである。上式においてxijは不定元である。この歪対称行列の行列式は多項式である（xij、i < jにおいて）: これは行列Aのパフィアンの二乗と一致し、完全マッチングが存在する時かつその時に限り（多項式として）非ゼロである（この多項式はGのではない）。 タット行列はに因んで命名され、釣り合い型2部グラフについてのの一般化である。 (ja) En théorie des graphes, la matrice de Tutte d'un graphe est une matrice utilisée pour déterminer l'existence d'un couplage parfait, soit d'un ensemble d'arêtes incidentes à chaque sommet exactement une fois. Si l'ensemble des sommets est , alors la matrice de Tutte de est une matrice de taille ayant pour coefficients : La nom matrice de Tutte provient du mathématicien W. T. Tutte, et est la généralisation de la matrice d'Edmonds pour les graphes bipartis équilibrés. * Portail des mathématiques (fr) In graph theory, the Tutte matrix A of a graph G = (V, E) is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once. If the set of vertices is then the Tutte matrix is an n × n matrix A with entries The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph. (en) |
| rdfs:label | Matrice de Tutte (fr) タット行列 (ja) Tutte matrix (en) |
| owl:sameAs | freebase:Tutte matrix wikidata:Tutte matrix dbpedia-fr:Tutte matrix dbpedia-ja:Tutte matrix dbpedia-sl:Tutte matrix https://global.dbpedia.org/id/4wFqi yago-res:Tutte matrix |
| prov:wasDerivedFrom | wikipedia-en:Tutte_matrix?oldid=1027628526&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tutte_matrix |
| is dbo:knownFor of | dbr:W._T._Tutte |
| is dbo:wikiPageWikiLink of | dbr:List_of_University_of_Toronto_faculty dbr:List_of_named_matrices dbr:Computing_the_permanent dbr:Polynomial_identity_testing dbr:W._T._Tutte dbr:Edmonds_matrix dbr:Isolation_lemma dbr:Schwartz–Zippel_lemma dbr:FKT_algorithm dbr:Pfaffian_orientation |
| is dbp:knownFor of | dbr:W._T._Tutte |
| is foaf:primaryTopic of | wikipedia-en:Tutte_matrix |