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 a set of dots (called vertices or nodes) connected by links (called arcs or edges). Depending on the applications, edges may or may not have a direction; edges joining a node to itself may or may not be allowed, nodes and/or edges may be assigned weights, and so on.
Formal definitions
A directed graph can be defined by
- a set E of edges,
- a set N of nodes, and
- maps s,t:E->N, where s is for source and t is for target.
A loop is an edge e in E such that s(e)=t(e).
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 is the number of edges incident upon it. 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. The number of neighbors that a vertex has is its valency.
- 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 Kn. 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 which every edge has a number associated with it, as with graphs in optimal route problems.
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