| dbo:abstract
|
- En matemàtiques, i més concretament en teoria de grafs, el teorema de Kirchhoff, anomenat en referència a Gustav Kirchhoff, és un teorema sobre el nombre d'arbres d'expansió en un , i mostra que aquest nombre es pot calcular en temps polinòmic com el determinant d'una matriu derivada del graf. És una generalització de la que proporciona el nombre d'arbres d'expansió en un graf complet. El teorema de Kirchhoff es basa en la noció de la d'un graf, igual a la diferència entre la del graf (una matriu diagonal amb el grau dels vèrtexs a la diagonal) i la seva matriu d'adjacència (una matriu-(0,1) amb 1 en els llocs corresponents a les entrades on els vèrtexs són adjacents i 0 en cas contrari). Per a un graf connex G amb n vèrtexs etiquetats, siguin λ1, λ₂, ..., λn-1 els valors propis diferents de zero de la seva matriu laplaciana. Llavors el nombre d'arbres d'expansió de G és Equivalentment, el nombre d'arbres d'expansió és igual a qualsevol cofactor de la matriu laplaciana de G. (ca)
- Der Satz von Kirchhoff (auch Satz von Kirchhoff-Trent, oder Matrix-Gerüst-Satz) ist ein Satz aus dem mathematischen Gebiet der Graphentheorie, welcher nach Gustav Kirchhoff benannt ist. Der Satz besagt, dass die Anzahl der beschrifteten Spannbäume eines Graphen in polynomieller Zeit über die Determinante einer aus dem Graphen gewonnenen Matrix berechnet werden kann. (de)
- En el campo matemático de la teoría de grafos, el teorema de Kirchhoff, nombrado por Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo, mostrando que ese número puede ser computado en tiempo polinomial como el determinante de una matriz derivada del grafo. Es una generalización de la fórmula de Cayley que provee el número total de árboles de expansión en un grafo completo. (es)
- In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise). For a given connected graph G with n labeled vertices, let λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is (en)
- Dans le domaine de la théorie des graphes, le théorème de Kirchhoff, aussi appelé matrix-tree theorem, nommé d'après le physicien Gustav Kirchhoff, est un théorème donnant le nombre exact d'arbres couvrants pour un graphe non orienté quelconque. C'est une généralisation de la formule de Cayley qui donne ce résultat pour les graphes complets non orientés. (fr)
- Twierdzenie Kirchhoffa (twierdzenie macierzowe o drzewach) – twierdzenie matematyczne z teorii grafów nazwane na cześć Gustava Kirchhoffa, mówiące o liczbie drzew rozpinających w grafie. Jest ono uogólnieniem o liczbie drzew rozpinających w grafie pełnym. (pl)
- In teoria dei grafi, il teorema di Kirchhoff è un teorema sul numero di alberi ricoprenti in un grafo. Esso prende il nome da Gustav Kirchhoff, ed è una generalizzazione della formula di Cayley che fornisce il numero di alberi ricoprenti in un grafo completo. (it)
- Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы. Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей. (ru)
- 在图论中，基尔霍夫定理（Kirchhoff theorem）或矩阵树定理（matrix tree theorem）是指，图的生成树数量等于调和矩阵的行列式（所以需要时间多项式计算）。 若 G 有 n 个顶点，λ1, λ2, ..., λn-1 是拉普拉斯矩阵的非零特征值，则 这个定理以基尔霍夫名字命名。 这也是凯莱公式的推广（若图是完全图）。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12642 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der Satz von Kirchhoff (auch Satz von Kirchhoff-Trent, oder Matrix-Gerüst-Satz) ist ein Satz aus dem mathematischen Gebiet der Graphentheorie, welcher nach Gustav Kirchhoff benannt ist. Der Satz besagt, dass die Anzahl der beschrifteten Spannbäume eines Graphen in polynomieller Zeit über die Determinante einer aus dem Graphen gewonnenen Matrix berechnet werden kann. (de)
- En el campo matemático de la teoría de grafos, el teorema de Kirchhoff, nombrado por Gustav Kirchhoff es un teorema sobre el número de árboles de expansión en un grafo, mostrando que ese número puede ser computado en tiempo polinomial como el determinante de una matriz derivada del grafo. Es una generalización de la fórmula de Cayley que provee el número total de árboles de expansión en un grafo completo. (es)
- Dans le domaine de la théorie des graphes, le théorème de Kirchhoff, aussi appelé matrix-tree theorem, nommé d'après le physicien Gustav Kirchhoff, est un théorème donnant le nombre exact d'arbres couvrants pour un graphe non orienté quelconque. C'est une généralisation de la formule de Cayley qui donne ce résultat pour les graphes complets non orientés. (fr)
- Twierdzenie Kirchhoffa (twierdzenie macierzowe o drzewach) – twierdzenie matematyczne z teorii grafów nazwane na cześć Gustava Kirchhoffa, mówiące o liczbie drzew rozpinających w grafie. Jest ono uogólnieniem o liczbie drzew rozpinających w grafie pełnym. (pl)
- In teoria dei grafi, il teorema di Kirchhoff è un teorema sul numero di alberi ricoprenti in un grafo. Esso prende il nome da Gustav Kirchhoff, ed è una generalizzazione della formula di Cayley che fornisce il numero di alberi ricoprenti in un grafo completo. (it)
- Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы. Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей. (ru)
- 在图论中，基尔霍夫定理（Kirchhoff theorem）或矩阵树定理（matrix tree theorem）是指，图的生成树数量等于调和矩阵的行列式（所以需要时间多项式计算）。 若 G 有 n 个顶点，λ1, λ2, ..., λn-1 是拉普拉斯矩阵的非零特征值，则 这个定理以基尔霍夫名字命名。 这也是凯莱公式的推广（若图是完全图）。 (zh)
- En matemàtiques, i més concretament en teoria de grafs, el teorema de Kirchhoff, anomenat en referència a Gustav Kirchhoff, és un teorema sobre el nombre d'arbres d'expansió en un , i mostra que aquest nombre es pot calcular en temps polinòmic com el determinant d'una matriu derivada del graf. És una generalització de la que proporciona el nombre d'arbres d'expansió en un graf complet. Per a un graf connex G amb n vèrtexs etiquetats, siguin λ1, λ₂, ..., λn-1 els valors propis diferents de zero de la seva matriu laplaciana. Llavors el nombre d'arbres d'expansió de G és (ca)
- In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. (en)
|
| rdfs:label
|
- Teorema de Kirchhoff (ca)
- Satz von Kirchhoff (de)
- Teorema de Kirchhoff (es)
- Teorema di Kirchhoff (it)
- Théorème de Kirchhoff (fr)
- Kirchhoff's theorem (en)
- Twierdzenie Kirchhoffa (pl)
- Матричная теорема о деревьях (ru)
- 矩阵树定理 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
