25-08-2017, 09:32 PM
19-09-2017, 01:38 PM
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 edge-vertex connectivity is preserved. Formally, an automorphism of a graph G = (V, E) is a permutation σ of the set of vertices V, so 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 graphic isomorphism of G itself. Automorphisms can be defined in this way for both directed graphics and non-directed graphics. The composition of two automorphisms is another automorphism, and the system of automorphisms of a given graph, under the operation of the composition, forms a group, the graph automorphism group. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph - in fact, of a cubic graph.
Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the problem of graph isomorphism, determining whether two given graphs correspond to vertex by vertex and edge to edge. For, G and H are isomorphic if and only if the disconnected graph formed by the disjoint union of the graphs G and H has an automorphism that exchanges the two components. In fact, the simple fact of counting automorphisms is a polynomial time equivalent to the isomorphism of the graphs.
The graph automorphism problem is the problem of testing whether a graph has a non-trivial automorphism. It belongs to the NP class of computational complexity. Similar to the graph isomorphism problem, it is unknown if it has a polynomial time algorithm or if it is NP-complete. There is a polynomial time algorithm to solve the graph automorphism problem for graphs where the vertex degrees are bounded by a constant. The graph automorphism problem is polynomial-many time-reducible to the graphic isomorphism problem, but the inverse reduction is unknown. On the contrary, hardness is known when automorphisms are restricted in a certain way; for example, to determine the existence of a free fixed-point automorphism (an automorphism that does not fix any vertex) is NP-complete, and the problem of counting such automorphisms is # P-complete.
Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the problem of graph isomorphism, determining whether two given graphs correspond to vertex by vertex and edge to edge. For, G and H are isomorphic if and only if the disconnected graph formed by the disjoint union of the graphs G and H has an automorphism that exchanges the two components. In fact, the simple fact of counting automorphisms is a polynomial time equivalent to the isomorphism of the graphs.
The graph automorphism problem is the problem of testing whether a graph has a non-trivial automorphism. It belongs to the NP class of computational complexity. Similar to the graph isomorphism problem, it is unknown if it has a polynomial time algorithm or if it is NP-complete. There is a polynomial time algorithm to solve the graph automorphism problem for graphs where the vertex degrees are bounded by a constant. The graph automorphism problem is polynomial-many time-reducible to the graphic isomorphism problem, but the inverse reduction is unknown. On the contrary, hardness is known when automorphisms are restricted in a certain way; for example, to determine the existence of a free fixed-point automorphism (an automorphism that does not fix any vertex) is NP-complete, and the problem of counting such automorphisms is # P-complete.