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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Satz von Frucht (de)
- Théorème de Frucht (fr)
- Frucht's theorem (en)
- Теорема Фрухта (ru)
- Теорема Фрухта (uk)
|
| 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)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
