Graph power (original) (raw)
In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. (en) Степень k (записывается Gk) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом. Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф. (ru) 在数学的一个分支图论中，一个无向图的k次幂Gk指的是另一个有相同顶点集的图，但在G中所有距离小于k的顶点在该图中是相邻的。图的次幂常用数的次幂相关术语来表示：G2被称为G的平方，G3被称为立方，以此类推。 图的次幂应该与区别开来，图的乘积（与次幂不同）通常比原图有更多的顶点。 (zh) У теорії графів, графом k-степені Gk неорієнтованого графа G є інший граф, що має таку ж саму кількість вершин, але дві його вершини є суміжними, коли відстань між ними не перевищує k. Аналогічну термінологію використовують при піднесенні чисел до степеня: G2 називається G квадрат, G3 називається G куб, тощо. Степінь графа слід відрізняти від добутку графа на себе, який (на відміну від графа в степені) має набагато більше вершин, ніж початковий граф. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Square_of_a_graph.svg?width=300 |
| dbo:wikiPageID | 38618878 (xsd:integer) |
| dbo:wikiPageLength | 11433 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096494042 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Half-square dbr:Degeneracy_(graph_theory) dbr:Hypercube_graph dbr:Undirected_graph dbr:Complete_graph dbr:Matrix_multiplication dbr:Chromatic_number dbr:Clique-width dbr:Girth_(graph_theory) dbr:Graph_coloring dbr:Graph_product dbr:NP-complete dbr:NP-hard dbr:K-vertex-connected_graph dbr:Leaf_power dbr:Adjacency_matrix dbr:Cube_(algebra) dbr:Exponentiation dbr:Angular_resolution_(graph_drawing) dbr:Graph_drawing dbr:Graph_theory dbr:Halved_cube_graph dbr:Bipartite_graph dbc:Graph_operations dbr:Distance_(graph_theory) dbr:Map_graph dbr:Planar_graph dbr:Square_number dbr:Greedy_coloring dbr:Graph_diameter dbr:Vertex_(graph_theory) dbr:Fleischner's_theorem dbr:Hamiltonian_cycle dbr:Breadth_first_search dbr:Sparse_graph dbr:File:Demi-3-cube.svg dbr:File:Square_of_a_graph.svg |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Reflist dbt:Sfrac dbt:Short_description dbt:Sup |
| dct:subject | dbc:Graph_operations |
| rdf:type | yago:Abstraction100002137 yago:Action114006945 yago:Attribute100024264 yago:Operation114008806 yago:WikicatGraphOperations yago:State100024720 |
| rdfs:comment | In graph theory, a branch of mathematics, the kth power Gk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. (en) Степень k (записывается Gk) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом. Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф. (ru) 在数学的一个分支图论中，一个无向图的k次幂Gk指的是另一个有相同顶点集的图，但在G中所有距离小于k的顶点在该图中是相邻的。图的次幂常用数的次幂相关术语来表示：G2被称为G的平方，G3被称为立方，以此类推。 图的次幂应该与区别开来，图的乘积（与次幂不同）通常比原图有更多的顶点。 (zh) У теорії графів, графом k-степені Gk неорієнтованого графа G є інший граф, що має таку ж саму кількість вершин, але дві його вершини є суміжними, коли відстань між ними не перевищує k. Аналогічну термінологію використовують при піднесенні чисел до степеня: G2 називається G квадрат, G3 називається G куб, тощо. Степінь графа слід відрізняти від добутку графа на себе, який (на відміну від графа в степені) має набагато більше вершин, ніж початковий граф. (uk) |
| rdfs:label | Graph power (en) Степень графа (ru) Степінь графа (uk) 图的次幂 (zh) |
| owl:sameAs | freebase:Graph power yago-res:Graph power wikidata:Graph power dbpedia-hu:Graph power dbpedia-ru:Graph power dbpedia-uk:Graph power dbpedia-zh:Graph power https://global.dbpedia.org/id/4kjB4 |
| prov:wasDerivedFrom | wikipedia-en:Graph_power?oldid=1096494042&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Demi-3-cube.svg wiki-commons:Special:FilePath/Square_of_a_graph.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_power |
| is dbo:wikiPageRedirects of | dbr:Square_of_a_graph dbr:Power_of_graph |
| is dbo:wikiPageWikiLink of | dbr:Michael_D._Plummer dbr:Bipartite_half dbr:Induced_matching dbr:Intersection_number_(graph_theory) dbr:Clique-width dbr:Glossary_of_graph_theory dbr:Bottleneck_traveling_salesman_problem dbr:Line_graph dbr:Square_of_a_graph dbr:Leaf_power dbr:Halved_cube_graph dbr:Blow-up_lemma dbr:Distance-hereditary_graph dbr:Map_graph dbr:Second_neighborhood_problem dbr:Power_of_graph |
| is foaf:primaryTopic of | wikipedia-en:Graph_power |
