A graph is a collection of nodes and edges. A node is a vertex (or point) in a graph and a connected graph contains connections between these nodes. These connections are called "edges" and they may have a specified direction to them. Graphs with edges that do not have a specified direction are called undirected graphs whereas those with edges that have directions are known as directed graphs.

A "path" involves a sequence of nodes that have a set of edges connecting them. A path between "a" and "d" for example, may go through nodes "b" and "c", therefore consisting of three edges. Using these paths between nodes, all the nodes within a graph can be visited by starting at a single node then exploring each node connected to it, then visiting each node connected to each of those nodes etc...

Graph theory is useful at representing real life structures such as the World Wide Web or Internet, small computer networks, or even the flow of a program. The World Wide Web is an exmaple of an undirected graph structure as the connections that make up the WWW are bi-directional i.e. information can flow both ways.

Reachability relates to whether a node within a graph can be reached by another node through a valid path. This applies to programming also as there may be pieces of code that can never be reached due to certain conditions. "Connectedness" describes how the nodes within a graph diagram are connected. If there are many arcs connecting many different nodes to other nodes, this is an example of strong connectedness. The opposite of this is weak connectedness.

The "out-degree" of a node is how many arcs are coming out of it, whereas the "in-degree" refers to the number of arcs going into it.

Planar graphs are graphs that can be drawn in a single plain without any edges crossing. Non-planar graphs would represent complex programs well as there are many nodes and many different ways to reach each node from other ones.

The Hamiltonian Cycle is where each node in a graph diagram is visited once and only once. Of course, not all structures would allow for this.

A subgraph is a smaller collection of connected nodes within the overall graph. Subgraphs allow a large system to be divided up into smaller, more manageable sections that can be maintained separately. This is a particularly applicable method for large computer systems owned by businesses for example.

Search for "Graph Theory" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Graph Theory" on the rest of Computing Students: Graph Theory