Frucht's theorem (original) (raw)
Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G.
| Property | Value |
|---|---|
| dbo:abstract | Der Satz von Frucht (nach Roberto Frucht) ist ein Satz aus dem mathematischen Teilgebiet der Graphentheorie. Er besagt, dass bis auf Isomorphie jede Gruppe als Automorphismengruppe eines Graphen auftritt. Ein Automorphismus eines ungerichteten Graphen , wobei die Knotenmenge und die Kantenmenge ist, ist eine bijektive Abbildung mit der Eigenschaft, dass zwei Knoten genau dann durch eine Kante verbunden sind, wenn und durch eine Kante verbunden sind.Die Menge aller Automorphismen von ist offenbar eine Gruppe und heißt die Automorphismengruppe von . Für einen kantenlosen Graphen oder für einen vollständigen Graphen ist offenbar gleich der symmetrischen Gruppe von von . Für alle anderen Graphen ist eine echte Untergruppe von . Im Extremfall ist , solche Graphen nennt man asymmetrisch. Die kleinste Knotenzahl eines asymmetrischen Graphen ist 6. Da nach dem Satz von Cayley jede Gruppe isomorph zu einer Untergruppe einer symmetrischen Gruppe ist, stellt sich die Frage, ob jede Gruppe als Automorphismengruppe eines Graphen auftritt. Diese Frage wird durch den Satz von Frucht positiv beantwortet: * Satz von Frucht: Zu jeder Gruppe gibt es einen Graphen, dessen Automorphismengruppe isomorph zu dieser Gruppe ist. Dieser Satz wurde 1938 von Roberto Frucht für endliche Gruppen formuliert und bewiesen. Der Fall unendlicher Gruppen wurde unabhängig voneinander von J. de Groot (1959) und G. Sabidussi (1960) bewiesen. (de) Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G. (en) Le théorème de Frucht est un résultat de théorie algébrique des graphes conjecturé en 1936 par Dénes Kőnig et prouvé en 1939 par Robert Frucht. Il affirme que tout groupe fini est le groupe des automorphismes d'un certain graphe non orienté. (fr) Теорема Фрухта — утверждение об изоморфизме каждой конечной группы группе автоморфизмов конечного неориентированного графа. Была сформулирована в 1936 году Бабаи и доказана в 1939 году Фрухтом. (ru) Теорема Фрухта є теоремою в алгебричній теорії графів, висловленої в 1936 році Денешем Кенігом і доведеною в 1939 році. Вона стверджує, що будь-яку скінченну групу можна представити, як групу симетрій скінченного неорієнтованого графу. Більше того, для будь-якої скінченної групи G існує нескінченно багато неізоморфних простих зв'язних графів, для яких група автоморфізму кожного з них ізоморфна G. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Frucht_graph.dot.svg?width=300 |
| dbo:wikiPageExternalLink | http://cms.math.ca/cjm/v1/p365 http://www.numdam.org/item%3Fid=CM_1939__6__239_0 http://cms.math.ca/cjm/v9/p515 http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf |
| dbo:wikiPageID | 26259599 (xsd:integer) |
| dbo:wikiPageLength | 8567 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1070145261 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Camille_Jordan dbr:Algebraic_graph_theory dbr:Regular_graph dbr:Robert_Frucht dbr:Cubic_graph dbr:Undirected_graph dbr:Vertex-transitive_graph dbr:Trivial_group dbr:Robertson–Seymour_theorem dbr:Connected_graph dbr:Median_graph dbr:Graph_coloring dbr:Theorem dbr:Leipzig dbr:László_Babai dbr:Compositio_Mathematica dbr:Frucht_graph dbr:Mathematische_Annalen dbc:Algebraic_graph_theory dbr:Tree_(graph_theory) dbr:Distinguishing_number dbr:Distributive_lattice dbr:K-vertex-connected_graph dbr:Akademische_Verlagsgesellschaft dbr:Alternating_group dbr:Cyclic_group dbr:Dénes_Kőnig dbr:Cayley_graph dbr:Gert_Sabidussi dbr:Graph_automorphism dbr:Graph_isomorphism dbr:Wreath_product dbc:Theorems_in_graph_theory dbr:Group_(mathematics) dbr:Isomorphic dbr:Johannes_de_Groot dbr:Birkhoff's_representation_theorem dbr:Direct_product_of_groups dbr:Planar_graph dbr:Orbit_(group_theory) dbr:Canadian_Journal_of_Mathematics dbr:Strongly_regular_graph dbr:Symmetric_group dbr:Monatshefte_für_Mathematik dbr:Partial_order dbr:Uncountably_many dbr:Simple_graph dbr:Finite_simple_group dbr:File:Frucht_graph.dot.svg |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist |
| dct:subject | dbc:Algebraic_graph_theory dbc:Theorems_in_graph_theory |
| gold:hypernym | dbr:Theorem |
| rdf:type | yago:WikicatTheoremsInGraphTheory yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G. (en) Le théorème de Frucht est un résultat de théorie algébrique des graphes conjecturé en 1936 par Dénes Kőnig et prouvé en 1939 par Robert Frucht. Il affirme que tout groupe fini est le groupe des automorphismes d'un certain graphe non orienté. (fr) Теорема Фрухта — утверждение об изоморфизме каждой конечной группы группе автоморфизмов конечного неориентированного графа. Была сформулирована в 1936 году Бабаи и доказана в 1939 году Фрухтом. (ru) Теорема Фрухта є теоремою в алгебричній теорії графів, висловленої в 1936 році Денешем Кенігом і доведеною в 1939 році. Вона стверджує, що будь-яку скінченну групу можна представити, як групу симетрій скінченного неорієнтованого графу. Більше того, для будь-якої скінченної групи G існує нескінченно багато неізоморфних простих зв'язних графів, для яких група автоморфізму кожного з них ізоморфна G. (uk) Der Satz von Frucht (nach Roberto Frucht) ist ein Satz aus dem mathematischen Teilgebiet der Graphentheorie. Er besagt, dass bis auf Isomorphie jede Gruppe als Automorphismengruppe eines Graphen auftritt. Ein Automorphismus eines ungerichteten Graphen , wobei die Knotenmenge und die Kantenmenge ist, ist eine bijektive Abbildung mit der Eigenschaft, dass zwei Knoten genau dann durch eine Kante verbunden sind, wenn und durch eine Kante verbunden sind.Die Menge aller Automorphismen von ist offenbar eine Gruppe und heißt die Automorphismengruppe von . (de) |
| rdfs:label | Satz von Frucht (de) Théorème de Frucht (fr) Frucht's theorem (en) Теорема Фрухта (ru) Теорема Фрухта (uk) |
| owl:sameAs | freebase:Frucht's theorem yago-res:Frucht's theorem wikidata:Frucht's theorem dbpedia-de:Frucht's theorem dbpedia-fr:Frucht's theorem dbpedia-ru:Frucht's theorem dbpedia-uk:Frucht's theorem https://global.dbpedia.org/id/RmtC |
| prov:wasDerivedFrom | wikipedia-en:Frucht's_theorem?oldid=1070145261&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Frucht_graph.dot.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Frucht's_theorem |
| is dbo:wikiPageDisambiguates of | dbr:Frucht |
| is dbo:wikiPageWikiLink of | dbr:Algebraic_graph_theory dbr:List_of_graph_theory_topics dbr:Robert_Frucht dbr:Glossary_of_graph_theory dbr:Frucht dbr:Frucht_graph dbr:Distinguishing_coloring dbr:Federico_Santa_María_Technical_University dbr:Cayley's_theorem dbr:Gert_Sabidussi dbr:Graph_automorphism dbr:Group_(mathematics) dbr:Asymmetric_graph dbr:Group_theory dbr:List_of_theorems |
| is foaf:primaryTopic of | wikipedia-en:Frucht's_theorem |
