Labeled graph

Labeled graph

In graph theory (which is an area in mathematics and computer science) a "labeled graph" is a graph with "labels" assigned to its nodes and edges. These assignments do not have to be unique, i.e. different nodes or edges can have the same label. Mathematically a labeled graph can be defined as follows:

Given two alphabets Sigma_V and Sigma_E a labeled graph is a triple G = (V,E,ell_V) where
*V is a finite set of nodes,
*Esubseteq V imesSigma_E imes V is a ternary relation describing the edges (including the labeling of the edges) and
*ell_Vcolon V ightarrowSigma_V is a function describing the labeling of the nodes.If E is symmetric, i.e. for all edges (v,l,w)in E it is also (w,l,v)in E, then the Graph G is called undirected and directed otherwise.

Note that this notion of a labeled graph is different from the notion given in the article graph labeling.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • 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

  • Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… …   Wikipedia

  • Graph labeling — In the mathematical discipline of graph theory, a graph labeling is the assignment of labels traditionally represented with integers to the edges or vertices, or both, of a graph. The labeling strategy depends on the category of the labeling.… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   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 cuts in computer vision — As applied in the field of computer vision, graph cuts can be employed to efficiently solve a wide variety of low level computer vision problems ( early vision ), such as image smoothing, the stereo correspondence problem, and many other computer …   Wikipedia

  • Molecular graph — In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory. A chemical graph is a labeled graph whose vertices… …   Wikipedia

  • Conceptual graph — Conceptual graphs (CGs) are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa (Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied… …   Wikipedia

  • Configuration graph — Configuration graphs are a theoretical tool used in computational complexity theory to prove a relation between graph reachability and complexity classes. Contents 1 Definition 2 Useful property 3 Use of this object …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

Share the article and excerpts

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