This HTML5 document contains 71 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Geometric_spanner
rdf:type
yago:Act100030358 yago:Procedure101023820 yago:VisualCommunication106873252 yago:WikicatGeometricAlgorithms yago:WikicatGeometricGraphs yago:Graph107000195 yago:Rule105846932 yago:YagoPermanentlyLocatedEntity yago:Activity100407535 yago:PsychologicalFeature100023100 yago:Abstraction100002137 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378
rdfs:label
Геометрический остов Geometric spanner Геометричний кістяк
rdfs:comment
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется остова. В вычислительной геометрии концепцию первым обсуждал Л.П. Чу в 1986, хотя термин «spanner» (остов) в статье упомянут не был. A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. Геометричний кістяк (англ. geometric spanner) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають кістяка. В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986), хоча термін «spanner» (кістяк) у статті не згадано.
dcterms:subject
dbc:Geometric_algorithms dbc:Geometric_graphs
dbo:wikiPageID
11844294
dbo:wikiPageRevisionID
1088547078
dbo:wikiPageWikiLink
dbr:Well-separated_pair_decomposition dbr:Yao_graph dbr:Gautam_Das_(computer_scientist) dbr:Spanning_subgraph dbr:Roaming dbr:Motion_planning dbr:Computational_geometry dbr:Degree_(graph_theory) dbr:Euclidean_distance dbr:Mobile_network dbr:Theta_graph dbr:Triangulation dbr:Telecommunication_network dbr:Glossary_of_graph_theory dbr:Proximity_problems dbr:Delaunay_triangulation dbr:NP-hard dbr:Minimum_spanning_tree dbr:Graph_theory dbc:Geometric_algorithms dbr:Asymptotic_notation dbr:Ingo_Althöfer dbr:Weighted_graph dbr:Graph_spanner dbr:Graph_embedding dbc:Geometric_graphs dbr:Stretch_factor dbr:Complete_graph
owl:sameAs
dbpedia-uk:Геометричний_кістяк dbpedia-ru:Геометрический_остов freebase:m.02rvcbq n17:4kE2A wikidata:Q5535497 yago-res:Geometric_spanner
dbp:wikiPageUsesTemplate
dbt:R dbt:Use_mdy_dates dbt:Reflist dbt:Main dbt:Mvar dbt:Short_description dbt:Use_American_English
dbo:abstract
A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. The notion of graph spanners has been known in graph theory: t-spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric. Spanners may be used in computational geometry for solving some proximity problems. They have also found applications in other areas, such as in motion planning, in telecommunication networks: network reliability, optimization of roaming in mobile networks, etc. Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется остова. В вычислительной геометрии концепцию первым обсуждал Л.П. Чу в 1986, хотя термин «spanner» (остов) в статье упомянут не был. Понятие остовных деревьев известно в теории графов — t-остова, это остовные подграфы графов с похожими свойствами растяжения, где расстояние между вершинами графа определяется в терминах теории графов. Поэтому геометрические остовы являются остовными деревьями полных графов, вложенных в плоскость, в которых веса рёбер равны расстояниям между вершинами в соответствующей метрике. Остовы могут быть использованы в вычислительной геометрии для решения некоторых . Они находят также приложения в других областях, таких как , в коммуникационных сетях — надёжность сети, оптимизация роуминга в мобильных сетях и т.д.. Геометричний кістяк (англ. geometric spanner) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають кістяка. В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986), хоча термін «spanner» (кістяк) у статті не згадано. Поняття кістякового дерева відоме в теорії графів: t-кістяки — це кістякові підграфи графів зі схожими властивостями розтягування, де відстань між вершинами графа визначається в термінах теорії графів. Тому геометричні кістяки є кістяковими деревами повних графів, укладених у площину, в яких ваги ребер дорівнюють відстаням між вершинами у відповідній метриці. Остовы можна використати в обчислювальній геометрії для розв'язання деяких . Вони мають також застосування в інших галузях, таких як планування руху, в комунікаційних мережах — надійність мережі, оптимізація роумінгу в мобільних мережах тощо.
prov:wasDerivedFrom
wikipedia-en:Geometric_spanner?oldid=1088547078&ns=0
dbo:wikiPageLength
9759
foaf:isPrimaryTopicOf
wikipedia-en:Geometric_spanner