Graph Theory

GraphTheory is the study of graphs.

A graph is a bunch of vertices and edges (also known as nodes and arcs). Each edge joins two vertices. That's all a graph is. (We don't think of the vertices and edges as being located anywhere in space; a graph is completely specified once you've said that there are N vertices and M edges and these ones are joined to those ones. Although sometimes it's interesting to attach properties to the vertices and edges - colour them, or assign capacities to them and see how much stuff can flow through the network, or whatever.)

In different areas of study, there can be variation in the exact details of the definition of a graph. For example, should we allow multiple edges joining a single pair of vertices? Should we allow a vertex to be joined to itself? When such variations are allowed, the term "simple graph" is used for a graph without such features; when such variations are not allowed, one could specifically refer to a "multigraph with loops" for a graph that might have them. Another distinction is between "undirected" and "directed" graphs: do we think of edges as joining unordered or ordered pairs of vertices? Directed graphs are useful a little more often (at least in "real world" applications), but generally the unqualified word "graph" means "undirected graph".

GraphTheory is a branch of PureMathematics, yet has lots of applications. Some examples:

OptimizingCompilers will usually represent the structure of (part of) a program as a graph, whose vertices are individual operations or BasicBlock?s and where edges correspond to possible transfers of control. Graphs are also often used for register allocation, and in fact for lots of other things.
Any situation involving movement through channels of limited capacity. By representing channels as edges in a graph labeled with numbers representing channel capacities, one can use GraphTheory to find optimal paths of transport through the network. This includes:
- bits on the internet;
- trucks on roads;
- current and voltage in electrical networks;
- fluids in pipelines;
- goods being moved between places;
- money flowing through an economy;
- particles in a FeynmanDiagram?;
- transitions between derived expressions when TheoremProving
The WorldWideWeb, or any portion of it, can be thought of as a directed graph whose vertices are Web pages and whose edges are hyperlinks. The result seems to be a type of graph called a SmallWorld Graph.
VLSI, CAD applications, and CASE tools. (See GraphViz for a cool example.)
The behavior of objects can be shown with states as vertices and changes as edges. StartCharts? are an abbreviated form of these.

Contributors: DickBotting, JosephDale, AnonymousDonors

GraphTheory provides a rich language for talking about complex structures. I jotted down some formal definitions of the language of GraphTheory in http://www.csci.csusb.edu/dick/maths/math_22_graphs.html. -- DickBotting

Much of GraphTheory is isomorphic to MatrixTheory? and where they join is now known as MatroidTheory, see, e.g., http://members.aol.com/matroids/

There are quite a lot of simple-to-understand questions in graph theory that are unsolved. Here's one. Take a (simple, undirected) graph where every vertex has exactly four edges. Is it always possible to find a subset of the vertices and a subset of the edges so that every retained vertex has exactly three retained edges?

Like NumberTheory, it's a field full of simple questions without answers.

Could all aggregate data structures essentially be created from a graph?

UnorderedCollection? - graph composed of zero edges.
OrderedCollection - acyclic graph with one path
Hierarchy - directed acyclic graph
Graph - graph

It seems that other aggregate data structure properties such as...

being sorted or ordered
not allowing duplicate values
immutability

are almost like filters. For example: if I wanted a SortedCollection? the input values could be filtered so that they're inserted in the proper location of 'sorted-ness'. If I wanted immutability the operations that would change the state of the values, or even the number of values could be filtered so that they either passively do nothing or actively throw an error. Maybe filters could be wrapped around each other similar to some of Java IO classes?

Graphs, at least by themselves, don't allow you to describe or represent filters, and I can't begin to imagine how you'd go about guaranteeing that there are no duplicate values in a mutable graph (what's a duplicate value in a graph, anyway? do edges make a difference as to whether the value is the same?). I'm not convinced you can create these other data structures in terms of graphs, though you probably can represent or impose their data upon a graph.

There is something similar called CategoryTheory, and proponents claim that all mathematics can be restated in category-theoretic terms. You seem to be asking the same sort of question, and the answer is probably "Yes". I would add, though, does it help? The answer to that is definitely "Only sometimes."

Re: UnorderedCollection? - graph composed of zero edges.

A graph with a single vertex, the only way to have no edges, implies a single datum. This is not a collection. A better example would be a collection of vertices that are fully meshed (e.g., a vertex has an edge to every other vertex). This allows one the ability to enumerate the contents of the collection, but no discernable directivity or associativity exists.' --SamuelFalvo?

I believe you're thinking in terms of the 'connected' graph. It is quite possible to describe a graph with many vertices and no edges whatsoever. A complete graph, as you're suggesting, would also work (it being isomorphic to the completely disconnected graph)... but I'd steer clear of it if only because it too readily presents the possibility of attaching semantic information to each edge in the graph (e.g. a label or a number), at which point the presence of edges becomes significant and associativity becomes relevant. This would come naturally to mind because each vertex in the collection must already have semantic information (this being the 'value' or an identifier for an 'object' found within the collection).

CategoryJargon CategoryMath