偏心率、半径、直径、中心和外围

1. Introduction

In this tutorial, we’ll explain five concepts from graph theory: eccentricity, radius, diameter, center, and periphery.

We’ll begin by defining the shortest path distance since the definitions of these concepts depend on it.

2. Graphs and Distances

Let’s say we have a graph G = (V, E, w) , where denotes the nodes, the edges, and their weights (or lengths).

The length $\boldsymbol{d(u, v)}$ of the shortest simple path between any two nodes $\boldsymbol{u, v \in V}$ is a distance metric defined on the graph . Thus, the triangle inequality holds:

$[d(u, v) + d (v, w) \leq d(u, w) \qquad (\forall u,v,w \in V)]$

The triangle inequality

That’s because d(u, w) is the length of the shortest path from to , so any path between them is at least as long.

3. Eccentricity

The eccentricity of a node is the maximum of its distances to other nodes:

$[e(u) = \max \{d(u, v) \mid v \in V \}]$

For example, the eccentricity of the node in the following graph is 8:

Node eccentricity

This is the length of the path $A \rightarrow B \rightarrow D \rightarrow E \rightarrow F$ .

4. Radius and Diameter

The diameter of a graph is the maximum eccentricity of its nodes:

$[diameter(G) = \max \{ e(u) \mid u \in V\}]$

We define the radius as the minimum eccentricity:

$[radius(G) = \min \{ e(u) \mid u \in V \}]$

It’s worth noting that these two terms have multiple meanings. Diameters can also denote the longest paths in a graph, just as a radius can be any path whose length is equal to the graph’s minimum eccentricity.

In our example, the diameter is 8 = d(A, F)=d(C, F) , and the radius is 5 = d(D, F) :

Diameter and radius

4.1. The Relationship Between Radius and Diameter

We can prove that the diameter is bounded from above by twice the radius:

$[diameter(G) \leq 2 \times radius(G)]$

This follows from the triangle inequality. Let and be two distinct nodes whose distance is equal to the diameter:

[d(u, w) = diameter(G)]

Let be a central node of . The triangle inequality tells us that:

$[diameter(G) = d(u, w) \leq d(u, v) + d(v, w)]$

Since is a central node, it holds that $d(u, v), d(v, w) \leq radius(G)$ . Therefore:

$[diameter(G) \leq 2 \times radius(G)]$

5. Center and Periphery

A node is peripheral if its eccentricity is equal to the graph’s diameter. All the nodes with that property constitute the graph’s periphery:

$[periphery(G) = \{u \in V \mid e(u) = diameter(G)\}]$

On the other hand, the center of a graph is comprised of the nodes whose eccentricity is equal to the graph’s radius:

$[center(G) = \{u \in V \mid e(u) = radius(G)\}]$

In our example, the periphery contains , , and , while the only central node is :

Center and Periphery

So, the peripheral nodes are at the opposite ends of the graph, while the central nodes are in between.

An example of when these concepts may be useful in determining the optimal placement of facilities on a graph. If we model a city map as a graph, it makes sense to build a facility at a central node because that will minimize the longest distance a citizen will have to travel to reach the facility.

Conversely, if the goal is to maximize the distance between two objects, we’d place them on the locations of two peripheral nodes on opposite sides of the town.

6. Conclusion

In this article, we explained several concepts from graph theory: eccentricity, radius, diameter, center, and periphery.

The diameter is always smaller than twice the radius, and the center minimizes the worst-case distances to other nodes in a graph.

Persistence

REST

Security