Asymmetric graph (original) (raw)
In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries. Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent.The identity mapping of a graph onto itself is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries. Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent.The identity mapping of a graph onto itself is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms. (en) En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d'automorphismes est trivial. C'est donc un graphe n'admettant aucun automorphisme autre que l'identité. Le plus petit graphe asymétrique est le graphe singleton, qui est également un graphe symétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets. Il existe 8 graphes asymétriques distincts à isomorphisme près à l'ordre 6, 152 à l'ordre 7, 3 696 à l'ordre 8, 135 004 à l'ordre 9, 7 971 848 à l'ordre 10 et 805 364 776 à l'ordre 11. Parmi les graphes cubiques, le plus petit graphe asymétrique est le graphe de Frucht. Il a 12 sommets. Sont également asymétriques le graphe de Kittell, le graphe 4-chromatique de Heawood et le graphe de Walther. (fr) No campo da matemática da teoria dos grafos, um grafo não direcionado é chamado um grafo assimétrico se não tiver simetrias não triviais. Formalmente, um automorfismo de um grafo é uma permutação p de seus vértices com a propriedade que quaisquer dois vértices u e v são adjacentes se e somente se p(u) e p(v) são adjacentes. O mapeamento identidade de um grafo em si é sempre um automorfismo, e é chamado de automorfismo trivial do grafo. Um grafo assimétrico é um grafo para os quais não existem outros automorfismos. (pt) У теорії графів, розділі математики, неорієнтований граф називається асиметричним графом, якщо він не має нетривіальних симетрій. Формально, автоморфізм графу є перестановкою р його вершин з тією властивістю, що будь-які дві вершини U і V суміжні тоді і тільки тоді, коли p(U) і p(V) є суміжними. Тотожне відображення графу на себе завжди автоморфізм, і називається тривіальним автоморфізмом графу. Асиметричний граф — це граф, для якого не існує ніяких інших автоморфізмів. (uk) Тожде́ственный граф (асимметри́чный граф) — граф, группа автоморфизмов которого состоит из одного единственного тождественного автоморфизма. Образно говоря, роль каждой вершины в тождественном графе уникальна. Тождественный граф из одной вершины есть просто одна отдельная вершина. Тождественных графов из 2, 3, 4 и 5 вершин не существует. Тождественных графов из шести вершин восемь штук и они изображены ниже. Количество тождественных графов на 7, 8, 9,... вершинах соответственно равно 152, 3696, 135004, ... (последовательность в OEIS) (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Asym-graph.png?width=300 |
| dbo:wikiPageID | 20249418 (xsd:integer) |
| dbo:wikiPageLength | 4927 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094193772 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbr:Permutation dbr:Regular_graph dbr:Cubic_graph dbr:Undirected_graph dbr:Rado_graph dbr:Erdős–Rényi_model dbr:Symmetries dbr:Complement_graph dbr:Frucht's_theorem dbr:Frucht_graph dbr:Tree_(graph_theory) dbr:Trivial_automorphism dbr:Countable dbr:Almost_all dbr:Graph_automorphism dbr:Graph_theory dbc:Asymmetry dbr:Vertex_(graph_theory) dbr:Random_graph dbr:Identity_mapping dbr:Trivial_graph dbr:File:Asym-graph.PNG dbr:File:Frucht_graph.dot.svg |
| dbp:wikiPageUsesTemplate | dbt:Commons_category dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Graph_families_defined_by_their_automorphisms |
| dct:subject | dbc:Graph_families dbc:Asymmetry |
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries. Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent.The identity mapping of a graph onto itself is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms. (en) No campo da matemática da teoria dos grafos, um grafo não direcionado é chamado um grafo assimétrico se não tiver simetrias não triviais. Formalmente, um automorfismo de um grafo é uma permutação p de seus vértices com a propriedade que quaisquer dois vértices u e v são adjacentes se e somente se p(u) e p(v) são adjacentes. O mapeamento identidade de um grafo em si é sempre um automorfismo, e é chamado de automorfismo trivial do grafo. Um grafo assimétrico é um grafo para os quais não existem outros automorfismos. (pt) У теорії графів, розділі математики, неорієнтований граф називається асиметричним графом, якщо він не має нетривіальних симетрій. Формально, автоморфізм графу є перестановкою р його вершин з тією властивістю, що будь-які дві вершини U і V суміжні тоді і тільки тоді, коли p(U) і p(V) є суміжними. Тотожне відображення графу на себе завжди автоморфізм, і називається тривіальним автоморфізмом графу. Асиметричний граф — це граф, для якого не існує ніяких інших автоморфізмів. (uk) Тожде́ственный граф (асимметри́чный граф) — граф, группа автоморфизмов которого состоит из одного единственного тождественного автоморфизма. Образно говоря, роль каждой вершины в тождественном графе уникальна. Тождественный граф из одной вершины есть просто одна отдельная вершина. Тождественных графов из 2, 3, 4 и 5 вершин не существует. Тождественных графов из шести вершин восемь штук и они изображены ниже. Количество тождественных графов на 7, 8, 9,... вершинах соответственно равно 152, 3696, 135004, ... (последовательность в OEIS) (ru) En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d'automorphismes est trivial. C'est donc un graphe n'admettant aucun automorphisme autre que l'identité. Le plus petit graphe asymétrique est le graphe singleton, qui est également un graphe symétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets. Il existe 8 graphes asymétriques distincts à isomorphisme près à l'ordre 6, 152 à l'ordre 7, 3 696 à l'ordre 8, 135 004 à l'ordre 9, 7 971 848 à l'ordre 10 et 805 364 776 à l'ordre 11. (fr) |
| rdfs:label | Asymmetric graph (en) Graphe asymétrique (fr) Grafo assimétrico (pt) Тождественный граф (ru) Асиметричний граф (uk) |
| owl:sameAs | freebase:Asymmetric graph yago-res:Asymmetric graph wikidata:Asymmetric graph dbpedia-fr:Asymmetric graph dbpedia-hu:Asymmetric graph dbpedia-pt:Asymmetric graph dbpedia-ru:Asymmetric graph dbpedia-uk:Asymmetric graph https://global.dbpedia.org/id/2p62S |
| prov:wasDerivedFrom | wikipedia-en:Asymmetric_graph?oldid=1094193772&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Asym-graph.png wiki-commons:Special:FilePath/Frucht_graph.dot.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Asymmetric_graph |
| is dbo:wikiPageWikiLink of | dbr:Frucht_graph dbr:Distinguishing_coloring dbr:Almost_all dbr:Graph_automorphism |
| is foaf:primaryTopic of | wikipedia-en:Asymmetric_graph |
