Rado graph

http://dbpedia.org/resource/Rado_graph an entity of type: Abstraction100002137

Der Rado-Graph (auch als Erdős-Rényi-Graph oder Zufallsgraph bezeichnet) ist ein spezieller abzählbar unendlicher Graph, der fast sicher entsteht, wenn jedes Knotenpaar unabhängig und mit Wahrscheinlichkeit durch eine Kante verbunden wird. Eine wichtige Erkenntnis ist, dass ein Satz in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn vom Rado-Graphen erfüllt wird. Er ist aufgrund von Arbeiten in den 1960er-Jahren nach Richard Rado bzw. Rado, Paul Erdős und Alfréd Rényi benannt, taucht aber schon 1937 bei Wilhelm Ackermann auf. rdf:langString
En mathématiques, et plus précisément en théorie des graphes, le graphe de Rado, appelé également graphe d'Erdős–Rényi ou graphe aléatoire, est un graphe infini dénombrable étudié au début des années 1960 par Richard Rado, Paul Erdős et Alfréd Rényi, caractérisé par la , qui implique qu’il contient (en tant que sous-graphe) n'importe quel graphe fini ou dénombrable. Il en existe plusieurs constructions ; c'est en particulier (presque sûrement) le graphe aléatoire obtenu en choisissant au hasard pour chaque paire de sommets s'ils sont connectés ou non. rdf:langString
그래프 이론에서 라도 그래프(영어: Rado graph)는 사실상 유일한 가산 무한 무작위 그래프이다. rdf:langString
Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф R, такий, що для будь-якого скінченного графу G і його вершини v будь-яке вкладення G − v в R як породженого підграфу можна розширити до вкладення G в R. Як наслідок, граф Радо містить усі скінченні і зліченні нескінченні графи як підграфи. Граф Радо відомий також під назвами випадковий граф і граф Ердеша — Реньї. rdf:langString
Граф Радо — единственный (с точностью до изоморфизма) счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов.Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи. rdf:langString
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic resid rdf:langString
rdf:langString Rado-Graph
rdf:langString Graphe de Rado
rdf:langString 라도 그래프
rdf:langString Rado graph
rdf:langString Граф Радо
rdf:langString Граф Радо
xsd:integer 7785594
xsd:integer 1111229963
rdf:langString Richard Rado
rdf:langString Wilhelm Ackermann
rdf:langString Paul
rdf:langString Richard
rdf:langString Wilhelm
rdf:langString Alfréd
rdf:langString Rado
rdf:langString Ackermann
rdf:langString Erdős
rdf:langString Rényi
xsd:integer 1937 1963 1964
rdf:langString Der Rado-Graph (auch als Erdős-Rényi-Graph oder Zufallsgraph bezeichnet) ist ein spezieller abzählbar unendlicher Graph, der fast sicher entsteht, wenn jedes Knotenpaar unabhängig und mit Wahrscheinlichkeit durch eine Kante verbunden wird. Eine wichtige Erkenntnis ist, dass ein Satz in der Prädikatenlogik erster Stufe genau dann für fast alle endlichen Graphen gilt, wenn vom Rado-Graphen erfüllt wird. Er ist aufgrund von Arbeiten in den 1960er-Jahren nach Richard Rado bzw. Rado, Paul Erdős und Alfréd Rényi benannt, taucht aber schon 1937 bei Wilhelm Ackermann auf.
rdf:langString En mathématiques, et plus précisément en théorie des graphes, le graphe de Rado, appelé également graphe d'Erdős–Rényi ou graphe aléatoire, est un graphe infini dénombrable étudié au début des années 1960 par Richard Rado, Paul Erdős et Alfréd Rényi, caractérisé par la , qui implique qu’il contient (en tant que sous-graphe) n'importe quel graphe fini ou dénombrable. Il en existe plusieurs constructions ; c'est en particulier (presque sûrement) le graphe aléatoire obtenu en choisissant au hasard pour chaque paire de sommets s'ils sont connectés ou non.
rdf:langString In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other. Every finite or countably infinite graph is an induced subgraph of the Rado graph, and can be found as an induced subgraph by a greedy algorithm that builds up the subgraph one vertex at a time. The Rado graph is uniquely defined, among countable graphs, by an extension property that guarantees the correctness of this algorithm: no matter which vertices have already been chosen to form part of the induced subgraph, and no matter what pattern of adjacencies is needed to extend the subgraph by one more vertex, there will always exist another vertex with that pattern of adjacencies that the greedy algorithm can choose. The Rado graph is highly symmetric: any isomorphism of its induced subgraphs can be extended to a symmetry of the whole graph.The first-order logic sentences that are true of the Rado graph are also true of almost all random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In model theory, the Rado graph forms an example of a saturated model of an ω-categorical and complete theory.
rdf:langString 그래프 이론에서 라도 그래프(영어: Rado graph)는 사실상 유일한 가산 무한 무작위 그래프이다.
rdf:langString Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф R, такий, що для будь-якого скінченного графу G і його вершини v будь-яке вкладення G − v в R як породженого підграфу можна розширити до вкладення G в R. Як наслідок, граф Радо містить усі скінченні і зліченні нескінченні графи як підграфи. Граф Радо відомий також під назвами випадковий граф і граф Ердеша — Реньї.
rdf:langString Граф Радо — единственный (с точностью до изоморфизма) счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов.Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.
rdf:langString Paul Erdős
rdf:langString Alfréd Rényi
xsd:nonNegativeInteger 35469

data from the linked data cloud