| http://dbpedia.org/ontology/abstract
|
In der Mathematik sind Expander-Graphen Fa … 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.en eine relativ „große“ Nachbarschaft hat.
, 在组合数学中，扩展图（英語：Expander graph）是一种具有强连通性质的，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。
, En mathématiques, et plus particulièrement … 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.rouve notamment en informatique théorique.
, Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче).
, Ekspander – graf o niewielkiej liczbie kra … 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.atów komunikacji w sieciach komputerowych.
, In graph theory, an expander graph is a sp … 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. and the theory of error-correcting codes.
, Экспандер (от англ. expander graph — расширяющий граф) — разреженный граф, при этом связность может определяться по вершинам, дугам или спектру (смотрите ниже).
, 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|
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.wisdom.weizmann.ac.il/%7Eoded/COL/expander.pdf +
, https://web.archive.org/web/20160629170338/http:/www.math.ias.edu/~boaz/ExpanderCourse/ +
, https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ +
, https://www.ams.org/notices/200407/what-is.pdf +
, http://michaelnielsen.org/blog/archive/notes/expander_graphs.pdf +
, http://www.cs.huji.ac.il/~dinuri/mypapers/combpcp.pdf%7Cciteseerx=10.1.1.103.2644%7Cs2cid=53244523 +
, http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf +
, https://www.quantamagazine.org/universal-method-to-sort-complex-information-found-20180813/ +
, http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html +
, https://web.archive.org/web/20070523090323/http:/www.yann-ollivier.org/specgraph/specgraph.html +
|
| http://dbpedia.org/ontology/wikiPageID
|
9313
|
| http://dbpedia.org/ontology/wikiPageLength
|
33702
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1121114256
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Avi_Wigderson +
, http://dbpedia.org/resource/Degree_%28graph_theory%29 +
, http://dbpedia.org/resource/2-norm +
, http://dbpedia.org/resource/Graph_coloring +
, http://dbpedia.org/resource/Omer_Reingold +
, http://dbpedia.org/resource/Extractor_%28mathematics%29 +
, http://dbpedia.org/resource/Regular_graph +
, http://dbpedia.org/resource/PCP_theorem +
, http://dbpedia.org/resource/ACM_SIGACT_News +
, http://dbpedia.org/resource/Edge_%28graph_theory%29 +
, http://dbpedia.org/resource/Extremal_graph_theory +
, http://dbpedia.org/resource/Computer_science +
, http://dbpedia.org/resource/Vertex_%28graph_theory%29 +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/Noga_Alon +
, http://dbpedia.org/resource/Eigenvector +
, http://dbpedia.org/resource/Complete_graph +
, http://dbpedia.org/resource/Independent_set_%28graph_theory%29 +
, http://dbpedia.org/resource/Multigraph +
, http://dbpedia.org/resource/Distance_%28graph_theory%29 +
, http://dbpedia.org/resource/Random_graph +
, http://dbpedia.org/resource/Abstract_algebra +
, http://dbpedia.org/resource/Computer_network +
, http://dbpedia.org/resource/Chernoff_bound +
, http://dbpedia.org/resource/Hypercube_graph +
, http://dbpedia.org/resource/Connectivity_%28graph_theory%29 +
, http://dbpedia.org/resource/Stationary_distribution +
, http://dbpedia.org/resource/Singular_values +
, http://dbpedia.org/resource/Cayley_graph +
, http://dbpedia.org/resource/Pseudorandom_generator +
, http://dbpedia.org/resource/Riemannian_geometry +
, http://dbpedia.org/resource/SL_%28complexity%29 +
, http://dbpedia.org/resource/Hash_function +
, http://dbpedia.org/resource/L_%28complexity%29 +
, http://dbpedia.org/resource/Linear_algebra +
, http://dbpedia.org/resource/Cambridge_University_Press +
, http://dbpedia.org/resource/Cheeger_constant_%28graph_theory%29 +
, http://dbpedia.org/resource/Erd%C5%91s%E2%80%93R%C3%A9nyi_model +
, http://dbpedia.org/resource/Journal_of_the_ACM +
, http://dbpedia.org/resource/Cheeger_bound +
, http://dbpedia.org/resource/Cryptography +
, http://dbpedia.org/resource/Zig-zag_product +
, http://dbpedia.org/resource/Derandomization +
, http://dbpedia.org/resource/Alon-Boppana_bound +
, http://dbpedia.org/resource/Markov_transition_matrix +
, http://dbpedia.org/resource/Markov_chains +
, http://dbpedia.org/resource/Symmetric_matrix +
, http://dbpedia.org/resource/Expander_mixing_lemma +
, http://dbpedia.org/resource/Spectral_gap +
, http://dbpedia.org/resource/Expander_code +
, http://dbpedia.org/resource/Peter_Sarnak +
, http://dbpedia.org/resource/Finite_geometry +
, http://dbpedia.org/resource/Superstrong_approximation +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Rayleigh_quotient +
, http://dbpedia.org/resource/Component_%28graph_theory%29 +
, http://dbpedia.org/resource/Eigenvalue +
, http://dbpedia.org/resource/Boundary_%28graph_theory%29 +
, http://dbpedia.org/resource/Orthogonal +
, http://dbpedia.org/resource/Ramanujan_graph +
, http://dbpedia.org/resource/Salil_Vadhan +
, http://dbpedia.org/resource/Sparse_graph +
, http://dbpedia.org/resource/Cheeger_constant +
, http://dbpedia.org/resource/Alexander_Lubotzky +
, http://dbpedia.org/resource/Sorting_network +
, http://dbpedia.org/resource/Adjacency_matrix +
, http://dbpedia.org/resource/Additive_combinatorics +
, http://dbpedia.org/resource/Spectral_graph_theory +
, http://dbpedia.org/resource/Directed_graph +
, http://dbpedia.org/resource/Error-correcting_code +
, http://dbpedia.org/resource/Vitali_Milman +
, http://dbpedia.org/resource/Spectral_theorem +
, http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/Random_regular_graph +
, http://dbpedia.org/resource/Laplacian_matrix +
, http://dbpedia.org/resource/Bipartite_graph +
, http://dbpedia.org/resource/Algebraic_connectivity +
, http://dbpedia.org/resource/American_Mathematical_Society +
, http://dbpedia.org/resource/Category:Graph_families +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Abs +
, http://dbpedia.org/resource/Template:Main_article +
, http://dbpedia.org/resource/Template:Cite_book +
, http://dbpedia.org/resource/Template:Overline +
, http://dbpedia.org/resource/Template:Mvar +
, http://dbpedia.org/resource/Template:Main_articles +
, http://dbpedia.org/resource/Template:Frac +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Sup +
, http://dbpedia.org/resource/Template:Sfn +
, http://dbpedia.org/resource/Template:Sub +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Sfrac +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Math +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_families +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Expander_graph?oldid=1121114256&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Expander_graph +
|
| owl:sameAs |
http://rdf.freebase.com/ns/m.02jwq +
, http://uk.dbpedia.org/resource/%D0%97%D0%B1%D1%96%D0%BB%D1%8C%D1%88%D1%83%D0%B2%D0%B0%D1%87_%28%D1%82%D0%B5%D0%BE%D1%80%D1%96%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D1%96%D0%B2%29 +
, http://de.dbpedia.org/resource/Expander-Graph +
, http://he.dbpedia.org/resource/%D7%92%D7%A8%D7%A3_%D7%9E%D7%A8%D7%97%D7%99%D7%91 +
, http://ru.dbpedia.org/resource/%D0%AD%D0%BA%D1%81%D0%BF%D0%B0%D0%BD%D0%B4%D0%B5%D1%80_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29 +
, http://cs.dbpedia.org/resource/Expander_%28graf%29 +
, https://global.dbpedia.org/id/4x1f6 +
, http://dbpedia.org/resource/Expander_graph +
, http://pl.dbpedia.org/resource/Ekspander +
, http://zh.dbpedia.org/resource/%E6%89%A9%E5%B1%95%E5%9B%BE +
, http://www.wikidata.org/entity/Q776602 +
, http://fr.dbpedia.org/resource/Taux_d%27expansion_%28th%C3%A9orie_des_graphes%29 +
, http://yago-knowledge.org/resource/Expander_graph +
, http://mn.dbpedia.org/resource/%D0%AD%D0%BA%D1%81%D0%BF%D0%B0%D0%BD%D0%B4%D0%B5%D1%80_%D0%B3%D1%80%D0%B0%D1%84 +
|
| rdf:type |
http://dbpedia.org/class/yago/WikicatGraphFamilies +
, http://dbpedia.org/class/yago/Organization108008335 +
, http://dbpedia.org/class/yago/Group100031264 +
, http://dbpedia.org/class/yago/YagoLegalActorGeo +
, http://dbpedia.org/class/yago/YagoLegalActor +
, http://dbpedia.org/class/yago/Family108078020 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
, http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/SocialGroup107950920 +
, http://dbpedia.org/class/yago/Unit108189659 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
|
| rdfs:comment |
Ekspander – graf o niewielkiej liczbie kra … 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.atów komunikacji w sieciach komputerowych.
, In der Mathematik sind Expander-Graphen Fa … 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.en eine relativ „große“ Nachbarschaft hat.
, 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|
, Збільшувач або експандер (від англ. expander graph — збільшувальний граф) — розріджений граф, при цьому зв'язність може визначатися за вершинами, дугами або спектром (див. нижче).
, In graph theory, an expander graph is a sp … 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. and the theory of error-correcting codes.
, 在组合数学中，扩展图（英語：Expander graph）是一种具有强连通性质的，可用边扩展性、顶点扩展性或图谱扩展性三种方式来量化。扩展图的构造问题引导了多个数学分支上的研究，并且在计算复杂性理论、计算机网络设计和编码理论上有诸多应用。
, En mathématiques, et plus particulièrement … 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.rouve notamment en informatique théorique.
, Экспандер (от англ. expander graph — расширяющий граф) — разреженный граф, при этом связность может определяться по вершинам, дугам или спектру (смотрите ниже).
|
| rdfs:label |
Збільшувач (теорія графів)
, Expander (graf)
, 扩展图
, Expander-Graph
, Taux d'expansion (théorie des graphes)
, Ekspander
, Expander graph
, Экспандер (теория графов)
|
