Typically, graphs are simply defined as vertices connected by edges. Slight more formally, graphs are a set of vertices and a set of edges, which are sets that connect two or more vertices. Sometimes edges are called "arcs" or "arrows". Here I try to use "edges". Edges can be undirected (a reciprical relationship) or directed. In the directed case, there there is a head and a tail (sometimes called start and end). There are several rules that can be applied to constructing graphs. Here, I'll go over the way I've been thinking about graphs. The mathematical rules of how graphs are typically constructed are laid out in depth elsewhere.
We can see that each type of graph is really just a more restricted form of a general hypergraph (which allows all types of edges to coexist in any number):
- Regular multigraphs being 2-uniform hypergraphs (each edge of size 2).
- Edges must be size two.
- Regular graphs being being 2-uniform hypergraphs.
- Edges must be size two.
- Only undirected edges.
- Directed graphs (digraphs) being 2-uniform directed hypergraphs.
- Edges must be size two.
- Only directed edges.
- Oriented digraphs being 2-uniform directed hypergraphs.
- Edges must be size two.
- Only directed edges.
- Every edge must point the same direction.
- Only one edge per unique pair of vertices.
Additionally, we can define other restrictions, such as not allowing loops. Or, perhaps, other maps which define certain vertices as "roots".
Edges can be looked at like they are a set of sets, but they're really a special kind of object:
- A simple edge is a set two sets, one with two elements while the other sits empty. There are morphisms x, y which map back to one vertex each.
- A hyperedge has a set of two sets, one with as no restriction on elements while the other sits empty. There are two morphisms x, y which map back to those sets.
- A directed edge is a set of two sets with one element each, the tail and the head. The morphisms t, h map to each element.
- A directed hyperedge has a set of two sets (tail and head sets), with no restriction on size for either set. The morphisms t, h map to each set.
The underlying object I chose for this is a Dedekind completion which uses a Dedekind cut to devide a set S between the lower cut L and the upper cut U:
- L, U \subset S. L is the lower cut. U is the upper cut.
- L = { x | x < a }, U = { x | x > a }
- a \in S
Basically, this lets us devide the edge into two ordered sets that have an order with respect to eachother. Then we can impose the meaning on those two sets of one pointing to the other based on the concept of irrflexisive comparisons of the Cut. Technically, all the undirected edges will have one-sided Dedekind completions of either:
- (\empty, S)
- (S, \empty)
This will form the basis of the indexing system used to map from the set to the vertices. We can say that the lower cut of a Dedekind completion points to the upper cut of the Dedekind completion. However, if the completion is one-sided then all its elements are unordered (even if the underlying set imposes order, we are only comparing cuts that are non-empty).
The we can define a path similarly to a 1-chain of 1-simplcial sets, where it is an ordered set of edges (Dedekind completions) with the condition that the sets which follow each other must intersect in a particular fashion:
- A lower cut must map to vertices which intersect with the vertices mapped to by the preceeding edge's upper cut.
- If either of the sequential edges are one-sided, replace the lower or upper cut with the whole set (in order to ignore the empty set generated by the cut).
We can then define a boundary operator on this particular notion of a path, but I will worry about that later when the need arises.
If you would like to read a highly condensed set theory overview of graphs, see Set Theory Overview.
If you would like to learn more about the connections between graphs and linear algebra, see the page on Linear Algebra.