Labeled graph

From Wikipedia, the free encyclopedia

You have new messages (last change).

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.

Retrieved from "http://en.wikipedia.org../../../l/a/b/Labeled_graph.html"
In other languages