Overview

# graph

## Quick Reference

**vertices** (or **nodes**) together with a set of **edges** that join pairs of distinct vertices. If an edge *e* joins vertices *v*_{1} and *v** _{2}*, then

*v*

_{1}and

*v*

*are said to be*

_{2}**incident**with

*e*and the vertices are said to be

**adjacent**;

*e*is the unordered pair (

*v*

_{1},

*v*

_{2}).

A graph is usually depicted in a pictorial form in which the vertices appear as dots or other shapes, perhaps labeled for identification purposes, and the edges are shown as lines joining the appropriate points. If direction is added to each edge of a graph, a directed graph or **digraph** is obtained. The edges then form a finite set of ordered pairs of distinct vertices, and are often called **arcs**. In the pictorial representation, arrows can be placed on each edge. With no direction specified, the graph is said to be **undirected**.

Although helpful visually these representations are not suitable for manipulation by computer. More useful representations use an incidence matrix or an adjacency matrix.

Graphs are used in a wide variety of ways in computing: the vertices will usually represent objects of some kind and the edges will represent connections of a physical or logical nature between the vertices. So graphs can be used to model in a mathematical fashion such diverse items as a computer and all its attached peripherals, a network of computers, parse trees, logical dependencies between subroutines or nonterminals in a grammar, VLSI diagrams, related items in databases for molecules and reaction networks (for chemoinformatics and bioinformatics). Trees and lists are special kinds of graphs.

Variations exist in the definition of a graph. There is some dispute about whether one edge can join a vertex to itself, whether empty sets are involved, whether an infinite number of vertices and edges are permitted, and so on.

See also connected graph, network, weighted graph.

*f*. The set of all ordered pairs (*x,y*) with the property that

*y* = *f*(*x*)

. Often such a graph is represented by a curve.

**From:**
graph
in
A Dictionary of Computing »