Kirchhoff's theorem (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Graph_with_all_its_spanning_trees.svg?width=300 |
| dbo:wikiPageExternalLink | http://math.fau.edu/locke/Graphmat.htm |
| dbo:wikiPageID | 1270691 (xsd:integer) |
| dbo:wikiPageLength | 12642 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094008650 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multigraph dbr:Monomial dbr:Determinant dbc:Spanning_tree dbr:List_of_graph_theory_topics dbr:Characteristic_polynomial dbr:Degree_matrix dbr:Incidence_matrix dbr:Indeterminate_(variable) dbr:Prüfer_sequence dbr:Complete_graph dbr:Mathematics dbr:Graph_(discrete_mathematics) dbr:Component_(graph_theory) dbr:Markov_chain_tree_theorem dbc:Algebraic_graph_theory dbr:Cayley's_formula dbr:Laplacian_matrix dbr:Adjacency_matrix dbc:Gustav_Kirchhoff dbr:Graph_theory dbr:Graphic_matroid dbr:Regular_matroid dbc:Theorems_in_graph_theory dbr:Gustav_Kirchhoff dbr:Homogeneous_polynomial dbr:Diamond_graph dbr:Polynomial_time dbr:Minimum_spanning_tree dbr:Cofactor_(linear_algebra) dbr:Loop_(graph_theory) dbr:Undergraduate_Texts_in_Mathematics dbr:Vertex_(graph_theory) dbr:Cauchy-Binet_formula dbr:Submatrix dbr:Eigenvalues dbr:Spanning_tree_(mathematics) dbr:File:Graph_with_all_its_spanning_trees.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Main dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Spanning_tree dbc:Algebraic_graph_theory dbc:Gustav_Kirchhoff dbc:Theorems_in_graph_theory |
| rdf:type | yago:WikicatMathematicalTheorems yago:WikicatTheorems yago:WikicatTheoremsInCombinatorics yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| 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 | freebase:Kirchhoff's theorem yago-res:Kirchhoff's theorem wikidata:Kirchhoff's theorem dbpedia-ca:Kirchhoff's theorem dbpedia-da:Kirchhoff's theorem dbpedia-de:Kirchhoff's theorem dbpedia-es:Kirchhoff's theorem dbpedia-fa:Kirchhoff's theorem dbpedia-fr:Kirchhoff's theorem dbpedia-he:Kirchhoff's theorem dbpedia-it:Kirchhoff's theorem dbpedia-pl:Kirchhoff's theorem dbpedia-ru:Kirchhoff's theorem dbpedia-vi:Kirchhoff's theorem dbpedia-zh:Kirchhoff's theorem https://global.dbpedia.org/id/2752t |
| prov:wasDerivedFrom | wikipedia-en:Kirchhoff's_theorem?oldid=1094008650&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Graph_with_all_its_spanning_trees.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Kirchhoff's_theorem |
| is dbo:wikiPageDisambiguates of | dbr:Kirchhoff |
| is dbo:wikiPageRedirects of | dbr:Kirchhoff's_matrix_tree_theorem dbr:Kirchhoff_polynomial dbr:Kirchhoff_theorem dbr:Kirchhoff’s_Matrix-Tree_theorem dbr:Kirchhoff’s_Matrix–Tree_theorem dbr:Kirchoff's_theorem dbr:Matrix-tree_theorem dbr:Matrix_tree_theorem |
| is dbo:wikiPageWikiLink of | dbr:Deletion–contraction_formula dbr:Spanning_tree dbr:Markov_chain_tree_theorem dbr:Laplacian_matrix dbr:Lindström–Gessel–Viennot_lemma dbr:Graph_theory dbr:Regular_matroid dbr:Gustav_Kirchhoff dbr:Abelian_sandpile_model dbr:Kirchhoff dbr:Loop-erased_random_walk dbr:List_of_theorems dbr:Kirchhoff's_matrix_tree_theorem dbr:Kirchhoff_polynomial dbr:Kirchhoff_theorem dbr:Kirchhoff’s_Matrix-Tree_theorem dbr:Kirchhoff’s_Matrix–Tree_theorem dbr:Kirchoff's_theorem dbr:Matrix-tree_theorem dbr:Matrix_tree_theorem |
| is foaf:primaryTopic of | wikipedia-en:Kirchhoff's_theorem |
