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
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 1941 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dbp:wikiPageUsesTemplate
| |
dcterms:subject
| |
rdf:type
| |
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
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:knownFor
of | |
is dbo:wikiPageWikiLink
of | |
is dbp:knownFor
of | |
is foaf:primaryTopic
of | |