Graph automorphism (original) (raw)
En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph G = (V, E) is a permutation σ of the vertex set V, such that the pair of vertices (u, v) form an edge if and only if the pair (σ(u), σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph. (en) En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe. (fr) No campo da matemática da teoria dos grafos, um automorfismo de um grafo é uma forma de simetria em que o grafo é mapeado em si, preservando a conectividade vértice-aresta.Formalmente, um automorfismo de um grafo G = (V,E) é uma permutação σ do conjunto de vértices V, tal que para qualquer aresta e = (u,v), σ(e) = (σ(u),σ(v)) é também uma aresta. Ou seja, ele é um isomorfismo de grafos de G para ele mesmo. Automorfismos podem ser definidos dessa maneira, tanto para grafos direcionados quando para grafos não-direcionados. A composição de dois automorfismos é outro automorfismo, e o conjunto de automorfismos de um grafo dado, sob a operação de composição, forma uma grupo, o grupo de automorfismo do grafo. No sentido inverso, pelo , todos os grupos pode ser representados como o grupo de automorfismo de um grafo conexo. - Na verdade, de um grafo cúbico. (pt) Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной: Реберная и вершинная группы графа изоморфны тогда и только тогда, когда имеется не более одной изолированной вершины, и нет компонент связности состоящих из единственного ребра. Граф, для которого единственный возможный автоморфизм это тождественное отображение, называется асимметрическим. Наименьшее асимметрическое дерево имеет семь вершин, а наименьший асимметрический граф шесть вершин и столько же ребер. Для любой конечной группы найдётся такой конечный неориентированный граф, что его группа автоморфизмов изоморфна данной. Результат получен Р. Фрухтом, в основе доказательства — преобразование цветного графа группы, обобщения графа Кэли. (ru) 在图论中，图自同构（graph automorphism）是保持自身的顶点与边的连接关系的对称。 正式地说，图的自同构是顶点集的置换，使得顶点对组成一条边当且仅当也组成一条边。也就是说，是到自身的图同构。自同构的这个定义对有向图和无向图都适用。两个自同构的复合仍是自同构，并且给定一个图，其所有自同构的集合在复合运算下构成群，称为这个图的自同构群。反过来，根据Frucht定理，所有群都可以表示成连通图的自同构群。 (zh) В математичному напрямку теорії графів, автоморфізм графу це форма симетрії за якої граф відображається на себе зі збереженням реберно-вершинних зв'язків. Формально, автоморфізм графу G = (V,E) це перестановка σ множини вершин V така, що для будь-якого ребра e = (u,v), σ(e) = (σ(u),σ(v)) також ребро. Тобто, це ізоморфізм G на себе. Автоморфізм може бути визначеним таким чином і для орієнтованих, і для неорієнтованих графів. Композиція двох автоморфізмів це знов автоморфізм, і множина автоморфізмів даного графу, із операцією композиція, формує групу, групу автоморфізмів графу. В зворотному напрямку, за теоремою Фрухта, всі групи можуть бути представлені як група автоморфізмів зв'язного графу — насправді, кубічного графу. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen1_tiny.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.tcs.hut.fi/Software/bliss/ http://cs.anu.edu.au/people/bdm/nauty/ http://vlsicad.eecs.umich.edu/BK/SAUCY/ |
| dbo:wikiPageID | 15094186 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Automorphismus |
| dbo:wikiPageLength | 13822 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094200069 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algebraic_graph_theory dbr:Permutation dbr:Regular_graph dbr:Cubic_graph dbr:Undirected_graph dbr:Vertex-transitive_graph dbr:♯P-complete dbr:Function_composition dbr:Graph_(discrete_mathematics) dbr:NP-complete dbr:Skew-symmetric_graph dbr:Computational_complexity_theory dbr:Frucht's_theorem dbr:Half-transitive_graph dbr:Molecular_symmetry dbr:Symmetry dbc:Algebraic_graph_theory dbr:Disjoint_union_of_graphs dbr:Distance-regular_graph dbr:Distance-transitive_graph dbr:Distinguishing_coloring dbr:Edge-transitive_graph dbr:Formal_verification dbr:Cayley_graph dbr:Directed_graph dbr:Graph_canonization dbr:Graph_drawing dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Graph_theory dbr:Group_(mathematics) dbr:Asymmetric_graph dbr:Involution_(mathematics) dbr:Symmetric_graph dbr:Automorphism_group dbr:Polynomial_time dbr:If_and_only_if dbr:Supply_chain dbr:Map_(mathematics) dbr:Strongly_regular_graph dbr:Vertex_(graph_theory) dbr:Many-one_reducible dbr:Semi-symmetric_graph dbr:Boolean_Satisfiability dbr:Class_NP dbr:File:Petersen1_tiny.svg dbr:File:Arrow_west.svg dbr:File:F26A_graph.svg dbr:File:Biclique_K_3_5.svg dbr:File:Arrow_east.svg dbr:File:Arrow_north.svg dbr:File:Arrow_south.svg dbr:File:Dodecahedral_graph.neato.svg dbr:File:Folkman_Lombardi.svg dbr:File:Frucht_graph.neato.svg dbr:File:Holt_graph.svg dbr:File:Nauru_graph.svg dbr:File:Paley13_no_label.svg dbr:File:Shrikhande_graph_square.svg dbr:File:Truncated_tetrahedral_graph.circo.svg dbr:File:Z_2xZ_3.svg |
| dbp:title | Graph automorphism (en) |
| dbp:urlname | GraphAutomorphism (en) |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mathworld dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Algebraic_graph_theory |
| gold:hypernym | dbr:Form |
| rdfs:comment | En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe. (fr) 在图论中，图自同构（graph automorphism）是保持自身的顶点与边的连接关系的对称。 正式地说，图的自同构是顶点集的置换，使得顶点对组成一条边当且仅当也组成一条边。也就是说，是到自身的图同构。自同构的这个定义对有向图和无向图都适用。两个自同构的复合仍是自同构，并且给定一个图，其所有自同构的集合在复合运算下构成群，称为这个图的自同构群。反过来，根据Frucht定理，所有群都可以表示成连通图的自同构群。 (zh) В математичному напрямку теорії графів, автоморфізм графу це форма симетрії за якої граф відображається на себе зі збереженням реберно-вершинних зв'язків. Формально, автоморфізм графу G = (V,E) це перестановка σ множини вершин V така, що для будь-якого ребра e = (u,v), σ(e) = (σ(u),σ(v)) також ребро. Тобто, це ізоморфізм G на себе. Автоморфізм може бути визначеним таким чином і для орієнтованих, і для неорієнтованих графів. Композиція двох автоморфізмів це знов автоморфізм, і множина автоморфізмів даного графу, із операцією композиція, формує групу, групу автоморфізмів графу. В зворотному напрямку, за теоремою Фрухта, всі групи можуть бути представлені як група автоморфізмів зв'язного графу — насправді, кубічного графу. (uk) In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity. Formally, an automorphism of a graph G = (V, E) is a permutation σ of the vertex set V, such that the pair of vertices (u, v) form an edge if and only if the pair (σ(u), σ(v)) also form an edge. That is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the (en) No campo da matemática da teoria dos grafos, um automorfismo de um grafo é uma forma de simetria em que o grafo é mapeado em si, preservando a conectividade vértice-aresta.Formalmente, um automorfismo de um grafo G = (V,E) é uma permutação σ do conjunto de vértices V, tal que para qualquer aresta e = (u,v), σ(e) = (σ(u),σ(v)) é também uma aresta. Ou seja, ele é um isomorfismo de grafos de G para ele mesmo. Automorfismos podem ser definidos dessa maneira, tanto para grafos direcionados quando para grafos não-direcionados. (pt) Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной: Реберная и вершинная группы графа изоморфны тогда и только тогда, когда имеется не более одной изолированной вершины, и нет компонент связности состоящих из единственного ребра. (ru) |
| rdfs:label | Graph automorphism (en) Automorphisme de graphe (fr) Automorfismo de grafos (pt) Автоморфизм графа (ru) 图自同构 (zh) Автоморфізм графів (uk) |
| owl:sameAs | freebase:Graph automorphism wikidata:Graph automorphism dbpedia-fr:Graph automorphism dbpedia-hr:Graph automorphism dbpedia-hu:Graph automorphism dbpedia-pt:Graph automorphism dbpedia-ru:Graph automorphism dbpedia-sl:Graph automorphism dbpedia-uk:Graph automorphism dbpedia-zh:Graph automorphism https://global.dbpedia.org/id/4zCiH |
| prov:wasDerivedFrom | wikipedia-en:Graph_automorphism?oldid=1094200069&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Petersen1_tiny.svg wiki-commons:Special:FilePath/Truncated_tetrahedral_graph.circo.svg wiki-commons:Special:FilePath/F26A_graph.svg wiki-commons:Special:FilePath/Biclique_K_3_5.svg wiki-commons:Special:FilePath/Dodecahedral_graph.neato.svg wiki-commons:Special:FilePath/Folkman_Lombardi.svg wiki-commons:Special:FilePath/Holt_graph.svg wiki-commons:Special:FilePath/Nauru_graph.svg wiki-commons:Special:FilePath/Paley13_no_label.svg wiki-commons:Special:FilePath/Arrow_south.svg wiki-commons:Special:FilePath/Shrikhande_graph_square.svg wiki-commons:Special:FilePath/Arrow_east.svg wiki-commons:Special:FilePath/Arrow_north.svg wiki-commons:Special:FilePath/Arrow_west.svg wiki-commons:Special:FilePath/Frucht_graph.neato.svg wiki-commons:Special:FilePath/Z_2xZ_3.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_automorphism |
| is dbo:wikiPageRedirects of | dbr:Graph_Automorphism dbr:Graph_automorphism_problem |
| is dbo:wikiPageWikiLink of | dbr:Beckman–Quarles_theorem dbr:Rook's_graph dbr:Bipartite_double_cover dbr:Algebraic_graph_theory dbr:Jordan–Pólya_number dbr:Periodic_graph_(crystallography) dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Robert_Frucht dbr:Cubic_graph dbr:Unit_distance_graph dbr:Vertex-transitive_graph dbr:Pearls_in_Graph_Theory dbr:Chemical_graph_generator dbr:Petersen_graph dbr:Rado_graph dbr:Chromatic_polynomial dbr:Cluster_graph dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Line_graph dbr:Complement_graph dbr:Franklin_graph dbr:Frucht's_theorem dbr:Frucht_graph dbr:Halin_graph dbr:Hall–Janko_graph dbr:Horton_graph dbr:Steinitz's_theorem dbr:Automorphism dbr:6-j_symbol dbr:Distance-regular_graph dbr:Distance-transitive_graph dbr:Distinguishing_coloring dbr:Gallery_of_named_graphs dbr:Cyclic_graph dbr:Ljubljana_graph dbr:Graph_Automorphism dbr:Graph_automorphism_problem dbr:Shrikhande_graph dbr:Cyclic_group dbr:Edge-transitive_graph dbr:Cayley_graph dbr:Goldner–Harary_graph dbr:Gosset_graph dbr:Graph_drawing dbr:Graph_isomorphism dbr:Graph_theory dbr:Gray_graph dbr:Gap dbr:2-satisfiability dbr:Group_action dbr:Asymmetric_graph dbr:Symmetric_graph dbr:Coherent_algebra dbr:Hereditarily_finite_set dbr:Holt_graph dbr:Homogeneous_graph dbr:Circulant_graph dbr:Klein_four-group dbr:F26A_graph dbr:Schläfli_graph dbr:Planar_cover dbr:Tutte–Coxeter_graph dbr:Semi-symmetric_graph dbr:The_Petersen_Graph dbr:Zero-symmetric_graph |
| is foaf:primaryTopic of | wikipedia-en:Graph_automorphism |
