Graphs

Imagine a social network with 6 subscribers (A, B, C, D, E and F) where:

A is friends with B, C and D
B is friends with A and D
C is friends with A, E and D
D is friends with all other subscribers
E is friends with C, D and F
F is friends with E and D

The description of this social network, despite its small number of subscribers, is already somewhat tedious, so imagine this same description with a social network having millions of subscribers!

There is a more "visual" way to represent this social network: we can represent each subscriber by a circle (with the subscriber's name located in the circle) and each relationship "X is friends with Y" by a line segment connecting X and Y ("X is friends with Y" and "Y is friends with X" being represented by the same line segment).

Here's what it gives with the social network described above:

This kind of figure is called a graph. Graphs are mathematical objects widely used, especially in computer science. The circles are called vertices and the line segments edges.

Definitions applicable to graphs

Graphs have properties that must be known, understood, and their calculations mastered. These properties will be regularly used in computer science.

Let G be a graph.

path

A path connecting two vertices A and B in a graph is a finite sequence of edges that connects these two vertices. It is used to visualize how one can go from one vertex to another within the graph.

distance between 2 vertices

The distance between two vertices of a graph is the minimum number of edges needed to connect these two vertices via a path. This measure is crucial for evaluating the accessibility of a vertex from another.

eccentricity

The eccentricity of a vertex is the maximum distance that separates it from the other vertices of the graph. It indicates how far a vertex is from others in the graph structure.

center

The center(s) of a graph are the vertices with minimum eccentricity. In other words, the center consists of the most "centered" vertex(es), those for which the distance to other vertices is as small as possible.

radius

The radius of a graph is the smallest of the eccentricities of the vertices. It therefore corresponds to the minimum eccentricity in the graph, i.e., the shortest maximum distance from a vertex to all other vertices.

diameter

The diameter of a graph is the largest of the eccentricities of the vertices. It represents the greatest possible distance between any two vertices of the graph.

Application of definitions

In the graph above, the distance between vertex A and vertex F equals 2 (path A-D-F).
WARNING: we're talking about the minimum number of edges, A-D-E-F is also a path between A and F but in this case, we have 3 edges.

Still in the graph above:

distance (A-B) = 1;
distance (A-C) = 1;
distance (A-D) = 1;
distance (A-E) = 2;
distance (A-F) = 2;

We can therefore say that the maximum distance existing between vertex A and the other vertices of the graph is 2 (distance (A-E) and distance (A-F)). We can therefore say that the eccentricity of A is 2.

Another example:

distance (D-A) = 1;
distance (D-B) = 1;
distance (D-C) = 1;
distance (D-E) = 1;
distance (D-F) = 1;

We can therefore say that the eccentricity of D is 1.

In the graph above all vertices have an eccentricity of 2 except vertex D which has an eccentricity of 1, we can therefore affirm that the center of the graph is vertex D.

In the graph above the maximum distance between 2 vertices is 2, we can therefore say that the diameter of the graph is 2.

D has an eccentricity of 1, it is the center of graph 1, we can therefore say that the radius of the graph above is 1.