Graph operations

Graph operations

Operations on graphs produce new graphs from old ones. They may be separated into the following major categories.

Contents

Unary operations

Unary operations create a new graph from the old one.

Elementary operations

These are sometimes called "editing operations" on graphs. They create a new graph from the original one by a simple, local change, such as addition or deletion of a vertex or an edge, merging and splitting of vertices, edge contraction, etc.

Advanced operations

Binary operations

Binary operations create a new graph from two initial graphs G1(V1, E1) and G2(V2, E2):

  • The disjoint union of graphs, sometimes referred to as simply graph union is defined as follows. For two graphs with disjoint vertex sets V1 and V2 (and hence disjoint edge sets), their disjoint union is the graph U(V1V2, E1E2).[1] It is a commutative and associative operation (for unlabelled graphs).
  • The graph join of two graphs is their graph union with all the edges that connect the vertices of the first graph with the vertices of the second graph.[1] It is a commutative operation (for unlabelled graphs)
  • Graph products based on the Cartesian product of the vertex sets:
    • Cartesian product of graphs [1] It is a commutative and associative operation (for unlabelled graphs).
    • Lexicographic product of graphs (also called graph composition) [1] It is noncommutative, non-associative
    • Strong product of graphs
    • Tensor product of graphs, also called direct product, categorical product, cardinal product, or Kronecker product. It is a commutative operation (for unlabelled graphs)
    • Zig-zag product of graphs [2] Let [N] denote the set of integers from 1 to N. It is supposed that k-regular graphs used in the definition below are k-edge colored, i.e., their edge sets are partitioned into k perfect matchings. For each color i and a vertex v let v[i] denote the neighbor of v along the edge colored with color i. Let G1 be a D1-regular graph on [N1] and let G2 be a D2-regular graph on [D1]. Then the zig-zag product H is a graph with vertex set [N1] × [D1], where for all n in [N1], d in [D1], and i,j, in [D2], the vertex (n, d) is connected to (n[d[i]], d[i][j]). This definition is used in construction of expander graphs.
  • Other graph operations called "products"
    • Rooted product of graphs. It is noncommutative, non-associative
    • Corona product or simply corona of G1 and G2, defined by Frucht and Harary[3] is the graph which is the disjoint union of one copy of G1 and |V1| copies of G2 (|V1| is the number of vertices of G1) in which each vertex of the copy of G1 is connected to all vertices of a separate copy of G2.
  • Series-parallel graph creation:
    • Series composition. It is a commutative operation (for unlabelled graphs)
    • Parallel composition. Non-commutative
    • Source composition (source merge). It is a commutative operation (for unlabelled graphs)
  • The Hajós construction

Notes

  1. ^ a b c d Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
  2. ^ Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders". Annals of Mathematics 155 (1): 157–187. doi:10.2307/3062153. JSTOR 3062153. MR1888797. 
  3. ^ Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Graph (data structure) — In computer science, a graph is a kind of data structure, specifically an abstract data type (ADT), that consists of a set of nodes (also called vertices) and a set of edges that establish relationships (connections) between the nodes. The graph… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • operations research — the analysis, usually involving mathematical treatment, of a process, problem, or operation to determine its purpose and effectiveness and to gain maximum efficiency. [1940 45, Amer.] * * * Application of scientific methods to management and… …   Universalium

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Graph rewriting — In graph theory, graph rewriting is a system of rewriting for graphs, i.e. a set of graph rewrite rules of the form p: L ightarrow R, with L being called pattern graph (or left hand side) and R being called replacement graph (or right hand side… …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • Graph product — A graph product is a binary operation on graphs. There are several similarly defined operations on graphs, called product . Given two graphs G1 and G2 , their product H is a graph such that * the vertex set of H is the Cartesian product V(G 1)… …   Wikipedia

  • Operations research — For the academic journal, see Operations Research: A Journal of the Institute for Operations Research and the Management Sciences. Operations research (also referred to as decision science, or management science) is an interdisciplinary… …   Wikipedia

  • Graph — I. Mathematik:Graphische Darstellung einer ⇡ Funktion im ⇡ Koordinatensystem. II. Operations Research:1. Begriff: Ein G. besteht aus einer nichtleeren Menge von V und einer Menge E mit V ∩ E = 0 sowie einer auf E definierten Abbildung w, die… …   Lexikon der Economics

  • Scene graph — A scene graph is a general data structure commonly used by vector based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.The scene… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”