In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, graph operations are
operations
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
which produce new
graphs from initial ones. They include both
unary (one input) and
binary (two input) operations.
Unary operations
Unary operations create a new graph from a single initial graph.
Elementary operations
Elementary operations or editing operations, which are also known as graph edit 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 initial one by a complex changes, such as:
*
transpose graph
In the mathematical and algorithmic study of graph theory, the converse, transpose or reverse, entry 2.24 of a directed graph is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of ...
;
*
complement graph;
*
line graph;
*
graph minor;
*
graph rewriting;
*
power of graph;
*
dual graph;
*
medial graph;
*
quotient graph;
*
Y-Δ transform;
*
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chroma ...
.
Binary operations
Binary operations create a new graph from two initial graphs and , such as:
* graph union: . 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 .
* graph intersection: ;
* graph join: graph with all the edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation (for unlabelled graphs);
[
* graph products based on the cartesian product of the vertex sets:
** cartesian graph product: it is a commutative and associative operation (for unlabelled graphs),][ Harary, F. ''Graph Theory''. Reading, MA: Addison-Wesley, 1994.]
** lexicographic graph product (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation,[
** ]strong graph product
In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The str ...
: it is a commutative and associative operation (for unlabelled graphs),
** tensor graph product (or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product): it is a commutative and associative operation (for unlabelled graphs),
** zig-zag graph product;
* graph product based on other products:
** rooted graph product: it is an associative operation (for unlabelled but rooted graphs),
** corona graph product: it is a non-commutative operation;
Notes
{{DEFAULTSORT:Graph Operations