Rado graph (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (de) 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. (fr) 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. (en) 그래프 이론에서 라도 그래프(영어: Rado graph)는 사실상 유일한 가산 무한 무작위 그래프이다. (ko) Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф R, такий, що для будь-якого скінченного графу G і його вершини v будь-яке вкладення G − v в R як породженого підграфу можна розширити до вкладення G в R. Як наслідок, граф Радо містить усі скінченні і зліченні нескінченні графи як підграфи. Граф Радо відомий також під назвами випадковий граф і граф Ердеша — Реньї. (uk) Граф Радо — единственный (с точностью до изоморфизма) счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов.Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Rado_graph.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.euro-math-soc.eu/ECM/ECM2000.1/Main/ECM2000.1.0267.0274.pdf https://www.mathunion.org/fileadmin/ICM/Proceedings/ICM2002.2/ICM2002.2.ocr.pdf http://matwbn.icm.edu.pl/ksiazki/aa/aa9/aa9133.pdf%7Ctitle=Universal http://researcher.ibm.com/researcher/files/us-fagin/jsl76.pdf |
| dbo:wikiPageID | 7785594 (xsd:integer) |
| dbo:wikiPageLength | 35469 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111229963 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cardinality_of_the_continuum dbr:Model_theory dbr:Omega-categorical_theory dbr:Universal_quantification dbr:Binary_numeral_system dbr:Binary_sequence dbr:Definite_article dbr:Almost_surely dbr:Paul_Erdős dbr:Richard_Rado dbr:Robert_Lawson_Vaught dbr:Indagationes_Mathematicae dbr:Index_of_a_subgroup dbr:Induced_subgraph dbr:PSPACE-complete dbr:Isolated_vertex dbr:Zero–one_law dbc:Individual_graphs dbr:Complete_graph dbr:Countable_set dbr:Countably_infinite dbr:Matching_(graph_theory) dbr:Mathematics dbr:Simple_group dbr:Quadratic_residue dbr:Łoś–Vaught_test dbr:Fraïssé_limit dbr:Continuum_hypothesis dbc:Infinite_graphs dbr:Erdős–Rényi_model dbr:Logic_of_graphs dbr:Clique_(graph_theory) dbr:Combinatorica dbr:Compactness_theorem dbr:Complement_graph dbr:Complete_theory dbr:Mathematische_Annalen dbr:Subgroup dbr:Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society dbr:Acta_Mathematica_Hungarica dbc:Random_graphs dbr:Morley's_categoricity_theorem dbr:Absolute_value dbr:Aleph_number dbr:Alfréd_Rényi dbr:Almost_all dbr:Edge_coloring dbr:European_Congress_of_Mathematics dbr:First-order_logic dbr:Forcing_(mathematics) dbr:Cardinality dbr:Diameter_(graph_theory) dbr:Directed_graph dbr:Dirichlet's_theorem_on_arithmetic_progressions dbr:Graph_automorphism dbr:Graph_isomorphism dbr:Graph_theory dbr:Israel_Journal_of_Mathematics dbr:Logical_connective dbr:Predicate_(mathematical_logic) dbr:Quadratic_reciprocity dbr:Hamiltonian_path dbr:Intersection_graph dbr:Isometry dbr:Back-and-forth_method dbr:Prime_number dbr:Chinese_remainder_theorem dbr:Jerzy_Łoś dbr:Block_design dbr:Symmetric_graph dbr:Symmetric_relation dbr:Henson_graph dbr:Hereditarily_finite_set dbr:Homogeneous_graph dbr:Distance_(graph_theory) dbr:Automorphism_group dbr:BIT_predicate dbr:Circulant_graph dbr:Greedy_algorithm dbr:Empty_graph dbr:Indicator_function dbr:Infinite_cyclic_group dbr:Natural_number dbr:Canadian_Mathematical_Bulletin dbr:Reflexive_relation dbr:Self-complementary_graph dbr:Sentence_(mathematical_logic) dbr:Type_(model_theory) dbr:Saturated_model dbr:Existential_quantification dbr:Universal_graph dbr:Pacific_Journal_of_Mathematics dbr:Paley_graph dbr:Skolem's_paradox dbr:Transactions_of_the_American_Mathematical_Society dbr:Proof_by_induction dbr:Almost_always dbr:Probability_one dbr:Binary_representation dbr:File:Rado_extension.svg dbr:File:Rado_graph.svg |
| dbp:author1Link | Paul Erdős (en) |
| dbp:author2Link | Alfréd Rényi (en) |
| dbp:authorlink | Richard Rado (en) Wilhelm Ackermann (en) |
| dbp:first | Paul (en) Richard (en) Wilhelm (en) Alfréd (en) |
| dbp:last | Rado (en) Ackermann (en) Erdős (en) Rényi (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Good_article dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Harvs |
| dbp:year | 1937 (xsd:integer) 1963 (xsd:integer) 1964 (xsd:integer) |
| dcterms:subject | dbc:Individual_graphs dbc:Infinite_graphs dbc:Random_graphs |
| rdf:type | yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:WikicatIndividualGraphs yago:WikicatInfiniteGraphs yago:VisualCommunication106873252 yago:WikicatRandomGraphs |
| rdfs:comment | 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. (de) 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. (fr) 그래프 이론에서 라도 그래프(영어: Rado graph)는 사실상 유일한 가산 무한 무작위 그래프이다. (ko) Граф Радо — єдиний (з точністю до ізоморфізму) зліченний граф R, такий, що для будь-якого скінченного графу G і його вершини v будь-яке вкладення G − v в R як породженого підграфу можна розширити до вкладення G в R. Як наслідок, граф Радо містить усі скінченні і зліченні нескінченні графи як підграфи. Граф Радо відомий також під назвами випадковий граф і граф Ердеша — Реньї. (uk) Граф Радо — единственный (с точностью до изоморфизма) счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов.Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи. (ru) 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 (en) |
| rdfs:label | Rado-Graph (de) Graphe de Rado (fr) 라도 그래프 (ko) Rado graph (en) Граф Радо (ru) Граф Радо (uk) |
| owl:sameAs | freebase:Rado graph yago-res:Rado graph wikidata:Rado graph dbpedia-de:Rado graph dbpedia-fr:Rado graph dbpedia-ko:Rado graph dbpedia-ru:Rado graph dbpedia-uk:Rado graph https://global.dbpedia.org/id/4tQjx |
| prov:wasDerivedFrom | wikipedia-en:Rado_graph?oldid=1111229963&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Rado_graph.svg wiki-commons:Special:FilePath/Rado_extension.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Rado_graph |
| is dbo:wikiPageRedirects of | dbr:The_random_graph dbr:Countable_random_graph |
| is dbo:wikiPageWikiLink of | dbr:List_of_first-order_theories dbr:Omega-categorical_theory dbr:Richard_Rado dbr:Vertex-transitive_graph dbr:Fraïssé_limit dbr:Logic_of_graphs dbr:Gallery_of_named_graphs dbr:Asymmetric_graph dbr:Back-and-forth_method dbr:Symmetric_graph dbr:Henson_graph dbr:Hereditarily_finite_set dbr:Homogeneous_graph dbr:BIT_predicate dbr:The_random_graph dbr:Self-complementary_graph dbr:Schläfli_graph dbr:Universal_graph dbr:The_Strange_Logic_of_Random_Graphs dbr:Random_graph dbr:Countable_random_graph |
| is foaf:primaryTopic of | wikipedia-en:Rado_graph |
