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.

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

- being sorted or ordered
- not allowing duplicate values
- immutability

- 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.

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).

EditText of this page (last edited May 28, 2013) or FindPage with title or text search