There are several types of graphs (🗺), among them:
- The most important one is the simple graph.
- A simple graph whose vertices have all the same degree is called a regular graph.
- A graph where every vertex can be reached from any other one is a connected graph.
Just like many other mathematical structures, graphs can be isomorphic.
Graphs contained within other graphs are called subgraphs.
- We can have edge-disjoint and vertex-disjoint subgraphs.
- We can also have expanded subgraphs.
- A proper subgraph is a subgraph whose set of edges or vertices is a proper subset of the corresponding supergraph’s set.
The complement of a given graph is a graph that shares the same vertices with such a graph, but has a disjoint set of edges.
An arc is an edge that has a direction.
A graph whose edges are all directed (i.e. arcs) is called a digraph.
There are many types of digraphs (🗺), among them:
- Similarly to a connected graph, a connected digraph is a digraph where a path (see below) exists between any two pair of vertices.
When we remove all the directions from a digraph that consists of all arcs, we get ’s subjacent graph.
Vertices and Edges
The amount of edges that incide on a vertex define its degree.
The length between two vertices is defined as the minimum amount of edges that must be traversed to reach one from the other. In the context of a connected graph, the eccentricity of a vertex is defined as the length between that vertex and the farthest one in the graph.
Edges with a direction are called arcs.
Edges can be of several types.
Operations with Graphs
Since graphs are essentially sets, we can define various operations on them:
We can additionally define graph fusion (), a special operation that is carried out within one same graph, relative to one of its edges.
Algorithms, Lemmas and Principles
By using the Havel-Hakimi algorithm, we can determine if a given non-increasing sequence of integers corresponds to the sequence of vertex degrees of a simple graph.
The Handshaking lemma tells us that given a graph with no edges, the sum of its vertices is always twice its number of edges.
The Pigeonhole principle tells us that, given , when we try to put objects in containers, then at least one container must be able to hold more than one object.
A path is an alternated finite sequence of vertices and degrees. Paths describe a “way” to traverse a graph.
There are various types of paths, the most important of them being:
A simple trajectory is an open path with no repeated vertices or edges.
A circuit is a closed path with no repeated edges, just one repeated vertex.
All these three, paths, trajectories and circuits, can be directed, which obey the direction of the arcs they go through.
A Eulerian path is a path that contains all the edges in a graph exactly once.
A block is a connected graph that remains connected even after deleting any of its vertices.