Spectral graph theory (original) (raw)
Das Spektrum dient in der Graphentheorie zur Untersuchung der Eigenschaften von Graphen. Das entsprechende Gebiet wird als Algebraische Graphentheorie oder Spektrale Graphentheorie bezeichnet. Die Berechnung des Spektrums eines Graphen ermöglicht einen sehr effektiven Algorithmus zum Graphenzeichnen (.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden.
| Property | Value |
|---|---|
| dbo:abstract | Das Spektrum dient in der Graphentheorie zur Untersuchung der Eigenschaften von Graphen. Das entsprechende Gebiet wird als Algebraische Graphentheorie oder Spektrale Graphentheorie bezeichnet. Die Berechnung des Spektrums eines Graphen ermöglicht einen sehr effektiven Algorithmus zum Graphenzeichnen (.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden. (de) En matemáticas, la Teoría Espectral de Grafos es el estudio de las propiedades de un grafo, en relación con su polinomio característico, valores y vectores propios de las matrices asociadas con el grafo, tales como su matriz de adyacencia y matriz laplaciana. La matriz de adyacencia de un grafo no dirigido simple es una matriz simétrica con coeficientes en los reales y, por lo tanto es diagonalizable ortogonalmente; sus valores propios son enteros algebraicos. Si bien la matriz de adyacencia depende del etiquetado del vértice, su es un gráfico invariante, aunque no completo. La teoría espectral de grafos también abarca con parámetros de grafos definimos por la multiplicidad de los valores propios de aquellas matrices asociadas con el grafo, tales como el número de Colin de Verdière. (es) En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. (fr) In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number. (en) 数学において、スペクトルグラフ理論は、隣接行列もしくはラプラシアン行列のような、そのグラフに結びついた行列の固有方程式、、に関係する、グラフの性質の研究である。 単純グラフの隣接行列は、実な対称行列であり、したがってであり；その固有値は実な代数的整数である。 頂点の名称付けによってその隣接行列が変わるのにたいして、それのスペクトルは、完全ではないものの、ひとつのである。 スペクトルグラフ理論は、のような、そのグラフと結びついた行列の固有値の重複度を通して定義される、グラフのパラメーターとも関係する。 (ja) Em matemática, a teoria espectral de grafos estuda propriedades de um grafo por meio de suas representações matriciais e de seus respectivos espectros. Em geral, a Teoria Algébrica dos Grafos estuda propriedades algébricas de funções de representação e operações em grafos, conceitos e propriedades algébricas delas decorrentes. Além disso, em Teoria Espectral de Grafos, estudam-se as propriedades estruturais decorrentes das matrizes que representam grafos. Estas últimas levam às propriedades espectrais das matrizes de representação, que é o elemento central da teoria espectral de grafos. (pt) Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа. Неориентированный граф имеет симметричную матрицу смежности, а потому имеет вещественные собственные значения (мультимножество которых называется спектр графа) и полное множество собственных векторов. В то время как матрица смежности графа зависит от нумерации вершин, его спектр является инвариантом графа. Спектральная теория графов занимается также параметрами, которые определяются путём умножения собственных значений матриц, связанных с графом, таких, как число Колен де Вердьера. (ru) 數學上，譜圖論（英語：spectral graph theory）是圖論的分支，研究图的性質與其邻接矩阵、调和矩阵等的特徵多項式、特征值和特征向量有何關聯。個頂點的圖，其鄰接矩陣是矩陣，各分量分別以或表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可，其特徵值皆是實代數整數。 雖然鄰接矩陣取決於如何標記頂點以作排序，但是矩阵的谱是圖不變量，不取決於標記方式。（不過也不是完備不變量，不足以完全刻畫圖的全部性質。） 譜圖論亦關注藉圖的矩陣特徵值重數定義的參數，如。 (zh) У математиці спектральна теорія графів — це вивчення властивостей графів характеристичних многочленів, власних векторів і власних значень матриць, пов'язаних з графом, таких, як його матриця суміжності або матриця Кірхгофа. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Isospectral_enneahedra.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.yale.edu/homes/spielman/eigs/ http://www.cs.yale.edu/~spielman/PAPERS/SGTChapter.pdf http://www.math.ucsd.edu/~fan/research/revised.html https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf http://www.win.tue.nl/~aeb/2WF02/spectra.pdf http://cs-www.cs.yale.edu/homes/spielman/sgta/ |
| dbo:wikiPageID | 534914 (xsd:integer) |
| dbo:wikiPageLength | 14795 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109107842 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_chemistry dbr:Enneahedron dbr:Algebraic_connectivity dbr:Algebraic_graph_theory dbc:Spectral_theory dbr:Regular_graph dbr:Characteristic_polynomial dbr:Cycle_(graph_theory) dbr:Vitali_Milman dbr:Incidence_geometry dbr:Independence_number dbr:Independent_set_(graph_theory) dbr:Complete_graph dbr:Mathematics dbr:Estrada_index dbr:Geometric_topology dbr:Symmetric_matrix dbr:Eigenvalue dbr:Eigenvector dbr:Graph_(discrete_mathematics) dbr:Multiset dbr:Orthogonal_diagonalization dbr:Star_(graph_theory) dbr:Spectrum_of_a_matrix dbc:Algebraic_graph_theory dbr:Toshikazu_Sunada dbr:Tree_(graph_theory) dbr:Distance-regular_graph dbr:Laplacian_matrix dbr:Adjacency_matrix dbr:Alan_J._Hoffman dbr:Algebraic_integer dbr:Almost_all dbr:Erdős–Ko–Rado_theorem dbr:Expander_graph dbr:Finite_field dbr:Noga_Alon dbr:Cheeger_bound dbr:Cheeger_constant dbr:Graph_isomorphism dbr:Graph_theory dbr:Isospectral dbr:Riemannian_geometry dbr:Hyperbolic_geometry dbr:Starlike_tree dbr:Academic_Press dbr:Colin_de_Verdière_graph_invariant dbr:Manifold dbr:Markov_chains dbr:Computer_networking dbr:Graph_invariant dbr:Graph_union dbr:Real_number dbr:Strongly_regular_graph dbr:Spectral_shape_analysis dbr:Polyhedral_graph dbr:Shuffling dbr:Spectral_clustering dbr:Lovász_theta dbr:File:Isospectral_enneahedra.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Cite_web dbt:Main dbt:Reflist dbt:Rp dbt:Sfn dbt:Sfnp dbt:Short_description |
| dcterms:subject | dbc:Spectral_theory dbc:Algebraic_graph_theory |
| gold:hypernym | dbr:Study |
| rdf:type | dbo:Book |
| rdfs:comment | Das Spektrum dient in der Graphentheorie zur Untersuchung der Eigenschaften von Graphen. Das entsprechende Gebiet wird als Algebraische Graphentheorie oder Spektrale Graphentheorie bezeichnet. Die Berechnung des Spektrums eines Graphen ermöglicht einen sehr effektiven Algorithmus zum Graphenzeichnen (.) Auch Expandergraphen können mittels spektraler Methoden charakterisiert werden. (de) En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. (fr) 数学において、スペクトルグラフ理論は、隣接行列もしくはラプラシアン行列のような、そのグラフに結びついた行列の固有方程式、、に関係する、グラフの性質の研究である。 単純グラフの隣接行列は、実な対称行列であり、したがってであり；その固有値は実な代数的整数である。 頂点の名称付けによってその隣接行列が変わるのにたいして、それのスペクトルは、完全ではないものの、ひとつのである。 スペクトルグラフ理論は、のような、そのグラフと結びついた行列の固有値の重複度を通して定義される、グラフのパラメーターとも関係する。 (ja) Em matemática, a teoria espectral de grafos estuda propriedades de um grafo por meio de suas representações matriciais e de seus respectivos espectros. Em geral, a Teoria Algébrica dos Grafos estuda propriedades algébricas de funções de representação e operações em grafos, conceitos e propriedades algébricas delas decorrentes. Além disso, em Teoria Espectral de Grafos, estudam-se as propriedades estruturais decorrentes das matrizes que representam grafos. Estas últimas levam às propriedades espectrais das matrizes de representação, que é o elemento central da teoria espectral de grafos. (pt) 數學上，譜圖論（英語：spectral graph theory）是圖論的分支，研究图的性質與其邻接矩阵、调和矩阵等的特徵多項式、特征值和特征向量有何關聯。個頂點的圖，其鄰接矩陣是矩陣，各分量分別以或表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可，其特徵值皆是實代數整數。 雖然鄰接矩陣取決於如何標記頂點以作排序，但是矩阵的谱是圖不變量，不取決於標記方式。（不過也不是完備不變量，不足以完全刻畫圖的全部性質。） 譜圖論亦關注藉圖的矩陣特徵值重數定義的參數，如。 (zh) У математиці спектральна теорія графів — це вивчення властивостей графів характеристичних многочленів, власних векторів і власних значень матриць, пов'язаних з графом, таких, як його матриця суміжності або матриця Кірхгофа. (uk) En matemáticas, la Teoría Espectral de Grafos es el estudio de las propiedades de un grafo, en relación con su polinomio característico, valores y vectores propios de las matrices asociadas con el grafo, tales como su matriz de adyacencia y matriz laplaciana. La matriz de adyacencia de un grafo no dirigido simple es una matriz simétrica con coeficientes en los reales y, por lo tanto es diagonalizable ortogonalmente; sus valores propios son enteros algebraicos. Si bien la matriz de adyacencia depende del etiquetado del vértice, su es un gráfico invariante, aunque no completo. (es) In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. (en) Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа. Неориентированный граф имеет симметричную матрицу смежности, а потому имеет вещественные собственные значения (мультимножество которых называется спектр графа) и полное множество собственных векторов. В то время как матрица смежности графа зависит от нумерации вершин, его спектр является инвариантом графа. (ru) |
| rdfs:label | Spektrum (Graphentheorie) (de) Teoría espectral de grafos (es) Théorie spectrale des graphes (fr) スペクトルグラフ理論 (ja) Spectral graph theory (en) Спектральная теория графов (ru) Teoria espectral de grafos (pt) Спектральна теорія графів (uk) 譜圖論 (zh) |
| owl:sameAs | freebase:Spectral graph theory wikidata:Spectral graph theory dbpedia-de:Spectral graph theory dbpedia-es:Spectral graph theory dbpedia-fa:Spectral graph theory dbpedia-fr:Spectral graph theory dbpedia-hu:Spectral graph theory dbpedia-ja:Spectral graph theory dbpedia-pt:Spectral graph theory dbpedia-ru:Spectral graph theory dbpedia-sk:Spectral graph theory dbpedia-sl:Spectral graph theory dbpedia-uk:Spectral graph theory dbpedia-zh:Spectral graph theory https://global.dbpedia.org/id/2wFgv |
| prov:wasDerivedFrom | wikipedia-en:Spectral_graph_theory?oldid=1109107842&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Isospectral_enneahedra.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Spectral_graph_theory |
| is dbo:knownFor of | dbr:Lothar_Collatz dbr:Fan_Chung |
| is dbo:wikiPageRedirects of | dbr:Isospectral_graph dbr:Graph_spectrum dbr:Perlis_theorem dbr:Isospectral_graphs |
| is dbo:wikiPageWikiLink of | dbr:Rook's_graph dbr:Rostislav_Grigorchuk dbr:Elementary_Number_Theory,_Group_Theory_and_Ramanujan_Graphs dbr:Enneahedron dbr:List_of_University_of_California,_San_Diego_people dbr:Desargues_graph dbr:Algebraic_graph_theory dbr:John_Urschel dbr:List_of_graph_theory_topics dbr:Characteristic_polynomial dbr:Integral_graph dbr:Iván_Gutman dbr:Pearls_in_Graph_Theory dbr:Proto-value_function dbr:Isospectral_graph dbr:Segmentation-based_object_categorization dbr:Petersen_graph dbr:Clique_problem dbr:Eigenvalues_and_eigenvectors dbr:Glossary_of_areas_of_mathematics dbr:Glossary_of_graph_theory dbr:Line_graph dbr:Lothar_Collatz dbr:Luca_Trevisan dbr:Clebsch_graph dbr:Hall–Janko_graph dbr:Harries–Wong_graph dbr:Horst_Sachs dbr:Spectral_theory dbr:Spectrum_(disambiguation) dbr:McKay–Miller–Širáň_graph dbr:Adjacency_algebra dbr:Wagner_graph dbr:Winnie_Li dbr:Distance-regular_graph dbr:Irene_Sciriha dbr:John_H._Smith_(mathematician) dbr:Laplacian_matrix dbr:Shrikhande_graph dbr:Adjacency_matrix dbr:Daniel_Spielman dbr:Alon–Boppana_bound dbr:Ernesto_Estrada dbr:Expander_graph dbr:Fan_Chung dbr:Breakthrough_Prize_in_Mathematics dbr:Brouwer's_conjecture dbr:Cayley_graph dbr:Graph_Fourier_transform dbr:Graph_energy dbr:Graph_theory dbr:Representation_(mathematics) dbr:Harries_graph dbr:Balaban_10-cage dbr:Hypergraph dbr:Cheeger_constant_(graph_theory) dbr:Bipartite_graph dbr:Higman–Sims_graph dbr:Hoffman_graph dbr:Hoffman–Singleton_graph dbr:Holonomy dbr:Homomorphism_density dbr:Graph_spectrum dbr:Ramanujan_graph dbr:Chang_graphs dbr:Root_system dbr:Strongly_regular_graph dbr:Extremal_graph_theory dbr:Ihara_zeta_function dbr:Odile_Favaron dbr:Planarity_testing dbr:Sudoku_graph dbr:Manifold_regularization dbr:Möbius–Kantor_graph dbr:Nauru_graph dbr:Tutte_12-cage dbr:Sidorenko's_conjecture dbr:Spectral_clustering dbr:Perlis_theorem dbr:Isospectral_graphs |
| is dbp:knownFor of | dbr:Lothar_Collatz dbr:Fan_Chung |
| is foaf:primaryTopic of | wikipedia-en:Spectral_graph_theory |
