A branch of mathematics involving the study of graphs, collections of points (commonly called vertices or nodes; this is the sense of node used on Everything) which are connected by edges (the equivalent of links on Everything).

A directed graph is one in which the edges are assigned directions, like one-way streets; that is, an edge may go from A to B but not from B to A. Directed graphs may have some bidirectional edges as well.

A graph is simple if there is only one edge between any two nodes. Otherwise the graph is nonsimple. A nonsimple graph may have some special edges called loops which go from one node back to the same node.

There are many other types of graphs with special names, but I will only describe one more here. A planar graph is one which can be drawn or embedded in a plane without any of the edges crossing, other than at nodes. For such graphs, Euler's formula holds, as is the case with convex polyhedra.

In much of the study of graph theory, only the nodes and the connections made by the edges matter, so the graph can be arbitrarily twisted and still remain the same graph; thus graph theory borders on topology.

-- This node saved by The Nodeshell Rescue Team

A contemporary application of this seemingly esoteric branch of mathematics is, of course, the Internet. Routers located throughout the World Wide Web need to constantly and instantly compute the fastest possible route for the data packets that make up your e-mail, telnet sessions, and pr0n downloads through an incredibly complex network of wires and fiber optics. The formulas they use are part of a classic graph theory problem: finding the shortest route from point A to point B across a graph.

Part of the "Math is good for more than just balancing your checkbook" project

Another fairly interesting application of graph theory in networking is with bridges. When you have a collection of arbitrarily linked bridges, it is really bad to have loops.
That is why the spanning tree algorithm is so important: it does the miracle of pruning an arbitrary (possibly non-simple) connected graph into a tree. And it can be proven right !

Graph theory is also relevant to the study of queues, which are again very important in operating systems research.

Johnathan Gross, graph theory professor at Columbia University (and holder of graphtheory.com), has composed the following graph theory song:

My Favorite Graphs
by Jonathan Gross

Labeled, bipartite, complete and directed;
transitive, rigid, and strongly connected.
Tournaments, trees; null and empty for laughs;
These are a few of my favorite graphs ...

Colors and voltages, brightly adorning,
new special cases that greet each new morning.
Hamilton circuits thru each vertex go,
Minimum cut equals maximum flow ...

Think of Polya, Kuratowski --
Heawood, Cayley, and Euler before.
Inspiring us now to work hard to derive
graph theorems evermore.

Log in or register to write something here or to contact authors.