Labeled graph

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (June 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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 ΣV and ΣE a labeled graph is a triple G = (V,E,\ell_V) where

  • V is a finite set of nodes,
  • E\subseteq V\times\Sigma_E\times V is a ternary relation describing the edges (including the labeling of the edges) and
  • \ell_V\colon V\rightarrow\Sigma_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.

Languages