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:

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

Much of GraphTheory is isomorphic to MatrixTheory? and where they join is now known as MatroidTheory, see, e.g.,

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?

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

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

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