Teoría de Gráficas

Graphs §

A graph is a structure that has a set of vertices and a set of edges. Edges link together vertices. Graphs can be represented graphically:

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.

Digraphs §

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 $G$ that consists of all arcs, we get $G$’s subjacent graph.

Vertices and Edges §

Vertices §

Each vertex in a graph has an open and a closed neighbourhood. A vertex where several edges incide is called a multi-edge.

The amount of edges that incide on a vertex define its degree.

In the context of a digraph, we can define a vertex’s external and internal degrees. In this same context, we can have several types of vertices, one of them being the hanging vertex.

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 §

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:

• Union, $\cup$
• Intersection, $\cap$
• Sum, $+$
• Ring sum, $\oplus$

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 $n>m$, when we try to put $n$ objects in $m$ containers, then at least one container must be able to hold more than one object.

Paths §

A path is an alternated finite sequence of vertices and degrees. Paths describe a “way” to traverse a graph.

The length of a path is the number of edges in it. Path concatenation is the operation of joining two paths one after the other.

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.

Trees §

A tree is a connected graph with no circuits. A set of trees is called a forest. There are various types of trees.

In a tree, there can be various leaf and branch vertices, but there can only be just one root vertex and one centre vertex.

Connectedness §

An articulation point is a vertex that when deleted disconnects a given connected graph. A bridge is the equivalent concept for edges.

A block is a connected graph that remains connected even after deleting any of its vertices.