wikipedia Graph operations

Graph operations produce new graphs from initial ones. They may be separated into the following major categories.

Unary operations

Unary operations create a new graph from one initial one.

Elementary operations

Elementary operations or editing operations create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc. The graph edit distance between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.

Advanced operations

Advanced operations create a new graph from one initial one by a complex changes, such as:

• transpose graph;
• complement graph;
• line graph;
• graph minor;
• graph rewriting;
• power of graph;
• dual graph;
• medial graph;
• quotient graph;
• Y-Δ transform;
• Mycielskian.

Binary operations

Binary operations create a new graph from two initial ones *G*1 = (*V*1, *E*1) and *G*2 = (*V*2, *E*2), such as:

• graph union: *G*1 ∪ *G*2. There are two definitions. In the most common one, the disjoint union of graphs, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of union in mathematics) the union of two graphs is defined as the graph (*V*1 ∪ *V*2, *E*1 ∪ *E*2).

图操作：

• serialize/topological sorting，参见
• Topological sorting
• C3 linearization
• shortest path
• Spanning tree

see more: Computational problems in graph theory