HOME

TheInfoList




Graph operations produce new
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
s from initial ones. They may be separated into the following major categories.


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 In graph theory In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ...

edge contraction
, etc. The
graph edit distanceIn mathematics and computer science, graph edit distance (GED) is a Similarity measure, measure of similarity (or dissimilarity) between two Graph (discrete mathematics), graphs. The concept of graph edit distance was first formalized mathematically ...
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 ''G'' is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of ...
; *
complement graph In graph theory, the complement or inverse of a graph is a graph on the same Vertex (graph theory), vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a graph ...

complement graph
; *
line graph In the mathematical Mathematics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its populatio ...

line graph
; *
graph minor In graph theory, an undirected graph ''H'' is called a minor of the graph ''G'' if ''H'' can be formed from ''G'' by deleting edges and vertices and by edge contraction, contracting edges. The theory of graph minors began with Wagner's theorem that ...
; *
graph rewriting In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of compu ...
; *
power of graph In graph theory, a branch of mathematics, the ''k''th power ''G'k'' of an undirected graph ''G'' is another graph that has the same set of vertex (graph theory), vertices, but in which two vertices are adjacent when their Distance (graph theory), ...
; *
dual graph In the mathematics, mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each pa ...
; *
medial graph In the mathematical Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

medial graph
; *
quotient graph In graph theory, a quotient graph ''Q'' of a graph ''G'' is a graph whose vertices are blocks of a partition of a set, partition of the vertices of ''G'' and where block ''B'' is adjacent to block ''C'' if some vertex in ''B'' is adjacent to some ve ...
; *
Y-Δ transform The Y-Δ transform, also written wye-delta and also known by many other names, is a mathematical technique to simplify the analysis of an electrical network An electrical network is an interconnection of electronic component, electrical compo ...
; *
MycielskianIn the mathematics, 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 graph, triangle-fr ...
.


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 (set theory), 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 product of graphs, cartesian graph product: it is a commutative and associative operation (for unlabelled graphs),Frank Harary, Harary, F. ''Graph Theory''. Reading, MA: Addison-Wesley, 1994. ** Lexicographic product of graphs, lexicographic graph product (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation, ** Strong product of graphs, strong graph product: it is a commutative and associative operation (for unlabelled graphs), ** Tensor product of 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 product of graphs, zig-zag graph product; * graph product based on other products: ** Rooted product of graphs, rooted graph product: it is an associative operation (for unlabelled but rooted graphs), ** Corona product of graphs, corona graph product: it is a non-commutative operation; * Series–parallel graph, series–parallel graph composition: ** parallel graph composition: it is a commutative operation (for unlabelled graphs), ** series graph composition: it is a non-commutative operation, ** source graph composition: it is a commutative operation (for unlabelled graphs); * Hajós construction.


Notes

{{DEFAULTSORT:Graph Operations Graph operations,