[go: up one dir, main page]

An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

Property Value
dbo:abstract
  • Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde |V'| ≥ (1+ε) |V| (cs)
  • In der Mathematik sind Expander-Graphen Familien von Graphen, die gleichzeitig dünn und hochzusammenhängend sind und sehr gute Stabilitätseigenschaften haben, sich also nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen lassen. Anschaulich heißt das, dass jede „kleine“ Teilmenge von Knoten eine relativ „große“ Nachbarschaft hat. (de)
  • In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes. (en)
  • En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique. (fr)
  • Ekspander – graf o niewielkiej liczbie krawędzi, w którym każdy podzbiór wierzchołków ma dużo sąsiadów. Istnieje kilka nierównoważnych formalizacji tej własności, definiujących różne klasy ekspanderów. Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki: dowodów w teorii złożoności, projektowaniu sieci sortujących, kodów korekcji błędów, ekstraktorów losowości i odpornych na błędy schematów komunikacji w sieciach komputerowych. (pl)
  • Экспандер (от англ. expander graph — расширяющий граф) — разреженный граф, при этом связность может определяться по вершинам, дугам или спектру (смотрите ниже). (ru)
  • 在组合数学中,扩展图(英語:Expander graph)是一种具有强连通性质的,可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究,并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。 (zh)
  • Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче). (uk)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 9313 (xsd:integer)
dbo:wikiPageLength
  • 33702 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1121114256 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dct:subject
gold:hypernym
rdf:type
rdfs:comment
  • Expander je graf, v němž pro každou množinu vrcholů V velikosti menší než k a pro množinu V' obsahující právě sousedy vrcholů z množiny V platí, že velikost V' je větší než velikost V. Jako ε-expander označujeme takový expander, kde |V'| ≥ (1+ε) |V| (cs)
  • In der Mathematik sind Expander-Graphen Familien von Graphen, die gleichzeitig dünn und hochzusammenhängend sind und sehr gute Stabilitätseigenschaften haben, sich also nicht durch Entfernen relativ weniger Kanten in mehrere Zusammenhangskomponenten zerlegen lassen. Anschaulich heißt das, dass jede „kleine“ Teilmenge von Knoten eine relativ „große“ Nachbarschaft hat. (de)
  • In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes. (en)
  • En mathématiques, et plus particulièrement en théorie des graphes, le taux d'expansion d'un graphe est une mesure de connectivité de ce graphe. Informellement, un grand taux d'expansion veut dire que n'importe quel sous-ensemble de sommets relativement petit possède beaucoup de connexions avec le reste du graphe. Cette mesure est surtout utilisée en raison des propriétés intéressantes des graphes ayant un fort taux d'expansion, parfois appelés graphes expanseurs. On les retrouve notamment en informatique théorique. (fr)
  • Ekspander – graf o niewielkiej liczbie krawędzi, w którym każdy podzbiór wierzchołków ma dużo sąsiadów. Istnieje kilka nierównoważnych formalizacji tej własności, definiujących różne klasy ekspanderów. Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki: dowodów w teorii złożoności, projektowaniu sieci sortujących, kodów korekcji błędów, ekstraktorów losowości i odpornych na błędy schematów komunikacji w sieciach komputerowych. (pl)
  • Экспандер (от англ. expander graph — расширяющий граф) — разреженный граф, при этом связность может определяться по вершинам, дугам или спектру (смотрите ниже). (ru)
  • 在组合数学中,扩展图(英語:Expander graph)是一种具有强连通性质的,可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究,并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。 (zh)
  • Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче). (uk)
rdfs:label
  • Expander (graf) (cs)
  • Expander-Graph (de)
  • Expander graph (en)
  • Taux d'expansion (théorie des graphes) (fr)
  • Ekspander (pl)
  • Экспандер (теория графов) (ru)
  • Збільшувач (теорія графів) (uk)
  • 扩展图 (zh)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License