Graph theory

Graph theory is a branch of mathematics that examines the properties of graphs. The development of algorithms to compute certain properties of graphs is also of major interest in computer science, where such algorithms are applied to many problems of practical interest, often in fields that on first inspection would seem to have little to do with graphs.

In graph theory, a graph is defined to be a set of dots (called vertices or nodes) connected by links (called arcs or edges). A more formal definition is:

A simple graph is a set of nodes N and a set E of unordered pairs of distinct elements of N called edges.

 1 _____ 2 _____ 3
       /       /
      /       /  an example of graph with 6 vertices and 7 edges
     /       /
     5 _____ 4_____6

Here, N = {1, 2, 3, 4, 5, 6} and E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}.

• valency

The valency of a vertex number of edges incident upon in. In the above graph vertices 1 and 3 have a valency of 2, vertice 2,4 and 5 have a valency of 3 and vertex 6 has a valency of 1. The total valency of the vertices is twice the number of edges.

• adjacent

Two nodes are considered adjacent if an edge exists between them. In the above graph, nodes 1 and 2 are adjacent, but nodes 2 and 4 are not.

• neighbor

The set of neighbors for a node contains each node adjacent to it. In the above graph, node 1 has two neighbors: node 2 and node 5.

• path

A path is a series of nodes in that each node is adjacent to both the preceding and succeding node. A path is considered simple if none of the nodes in the path are repeated. In the above graph, {1, 2, 5, 1, 2, 3} is a path, and {5, 2, 1} is a simple path.

If it is possible to establish a path from any vertex to any other vertex of a graph, the graph is said to be connected.

• cycle

A cycle (or circuit) is a path that begins and ends with the same node. In the above graph, {1, 5, 2, 1} is a cycle. A path is acyclic if it is not a cycle. A simple cycle is one in which the beginning node only appears once more, as the ending node and other nodes appear only once. In the above graph (1,2,3,4,5,2,1) is a cycle but not not a simple cycle.

• tree

A connected graph without cycles is said a tree; equivalently, a tree on n vertices is a connected graph with exactly n-1 edges. Trees are largely used as data structures in computer science (see tree data structure).

• complete

A complete graph is one in which every node is adjacent to every other node. The above graph is not complete. The complete graph on n vertices is often denoted by K_n. It has n(n-1)/2 edges (corresponding to all possible choices of pairs of vertices).

• planar

A planar graph is one which can be drawn in the plane without any two edges intersecting. The above graph is planar; the complete graph on n vertices, for n> 4, is not planar.

• weighted

A weighted graph is one in whcih every edge has a number associated with it, as with graphs in optimal route problems.

• traversability

A graph (network of nodes) is traversable if every edge on the graph can be traced once and only once without taking pen from paper. There are two types of trail, eulerian trails and semi-eulerian trails. If a graph is traversable with a eulerian trail, this means that you finish at the point you started. Semi-eulerian trails draw every edge only once but end in a different place to which they start.

Graph Problems

• Coloring graphs: the four color theorem

• Route problems:
  • Minimum spanning tree
  • Shortest path problem
  • Route inspection problem (aka "Chinese Postman Problem")
  • Traveling salesman problem

Important Algorithms

• Dijkstras Algorithm
• Kruskal's algorithm
• Nearest neighbour algorithm
• Prim's algorithm