Английская Википедия:Havel–Hakimi algorithm

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description Шаблон:No footnotes The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence exists, or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algorithm was published by Шаблон:Harvtxt, and later by Шаблон:Harvtxt.

The algorithm

The Havel-Hakimi algorithm is based on the following theorem.

Let <math>A = (s, t_{1},..., t_{s}, d_{1},..., d_{n})</math> be a finite list of nonnegative integers that is nonincreasing. Let <math>A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n})</math> be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List <math>A</math> is graphic if and only if list <math>A'</math> is graphic.

If the given list <math>A</math> is graphic, then the theorem will be applied at most <math>n-1</math> times setting in each further step <math>A:=A'</math>. Note that it can be necessary to sort this list again. This process ends when the whole list <math>A'</math> consists of zeros. Let <math>G</math> be a simple graph with the degree sequence <math>A</math>: Let the vertex <math>S</math> have degree <math>s</math>; let the vertices <math>T_{1},..., T_{s}</math> have respective degrees <math>t_{1},..., t_{s}</math>; let the vertices <math>D_{1},..., D_{n}</math> have respective degrees <math>d_{1},..., d_{n}</math>. In each step of the algorithm, one constructs the edges of a graph with vertices <math>T_{1},..., T_{s}</math>—i.e., if it is possible to reduce the list <math>A</math> to <math>A'</math>, then we add edges <math>\{S,T_1\},\{S,T_2\},\cdots,\{S,T_{s}\}</math>. When the list <math>A</math> cannot be reduced to a list <math>A'</math> of nonnegative integers in any step of this approach, the theorem proves that the list <math>A</math> from the beginning is not graphic.

Proof

The following is a summary based on the proof of the Havel-Hakimi algorithm in Invitation to Combinatorics (Shahriari 2022).

To prove the Havel-Hakimi algorithm always works, assume that <math>A'</math> is graphic, and there exists a simple graph <math>G'</math> with the degree sequence <math>A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n})</math>. Then we add a new vertex <math>v</math> adjacent to the <math>s</math> vertices with degrees <math>t_{1}-1,..., t_{s}-1</math> to obtain the degree sequence <math>A</math>.

To prove the other direction, assume that <math>A</math> is graphic, and there exists a simple graph <math>G</math> with the degree sequence <math>A = (s, t_{1},..., t_{s}, d_{1},..., d_{n})</math> and vertices <math>S, T_{1},..., T_{s}, D_{1},..., D_{n}</math>. We do not know which <math>s</math> vertices are adjacent to <math>S</math>, so we have two possible cases.

In the first case, <math>S</math> is adjacent to the vertices <math>T_{1},..., T_{s}</math> in <math>G</math>. In this case, we remove <math>S</math> with all its incident edges to obtain the degree sequence <math>A'</math>.

In the second case, <math>S</math> is not adjacent to some vertex <math>T_{i}</math> for some <math>1 \leq i \leq s</math> in <math>G</math>. Then we can change the graph <math>G</math> so that <math>S</math> is adjacent to <math>T_{i}</math> while maintaining the same degree sequence <math>A</math>. Since <math>S</math> has degree <math>s</math>, the vertex <math>S</math> must be adjacent to some vertex <math>D_{j}</math> in <math>G</math> for <math>1 \leq j \leq n</math>: Let the degree of <math>D_{j}</math> be <math>d_{j}</math>. We know <math>t_i \geq d_j</math>, as the degree sequence <math>A</math> is in non-increasing order.

Since <math>t_i \geq d_j</math>, we have two possibilities: Either <math>t_i = d_j</math>, or <math>t_i > d_j</math>. If <math>t_i = d_j</math>, then by switching the places of the vertices <math>T_{i}</math> and <math>D_{j}</math>, we can adjust <math>G</math> so that <math>S</math> is adjacent to <math>T_{i}</math> instead of <math>D_{j}.</math> If <math>t_i > d_j</math>, then since <math>T_{i}</math> is adjacent to more vertices than <math>D_{j}</math>, let another vertex <math>W</math> be adjacent to <math>T_{i}</math> and not <math>D_{j}</math>. Then we can adjust <math>G</math> by removing the edges <math>\left \{ S, D_j \right \}</math> and <math>\left \{ T_i, W \right \}</math>, and adding the edges <math>\left \{ S, T_i \right \}</math> and <math>\left \{ W, D_j\right \}</math>. This modification preserves the degree sequence of <math>G</math>, but the vertex <math>S</math> is now adjacent to <math>T_{i}</math> instead of <math>D_{j}</math>. In this way, any vertex not connected to <math>S</math> can be adjusted accordingly so that <math>S</math> is adjacent to <math>T_{i}</math> while maintaining the original degree sequence <math>A</math> of <math>G</math>. Thus any vertex not connected to <math>S</math> can be connected to <math>S</math> using the above method, and then we have the first case once more, through which we can obtain the degree sequence <math>A'</math>. Hence, <math>A</math> is graphic if and only if <math>A'</math> is also graphic.

Examples

Let <math>6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1</math> be a nonincreasing, finite degree sequence of nonnegative integers. To test whether this degree sequence is graphic, we apply the Havel-Hakimi algorithm:

First, we remove the vertex with the highest degree — in this case, <math>6</math> —  and all its incident edges to get <math>2, 2, 2, 2, 1, 1, 2, 2, 1, 1</math> (assuming the vertex with highest degree is adjacent to the <math>6</math> vertices with next highest degree). We rearrange this sequence in nonincreasing order to get <math>2, 2, 2, 2, 2, 2, 1, 1, 1, 1</math>. We repeat the process, removing the vertex with the next highest degree to get <math>1, 1, 2, 2, 2, 1, 1, 1, 1</math> and rearranging to get <math>2, 2, 2, 1, 1, 1, 1, 1, 1</math>. We continue this removal to get <math>1, 1, 1, 1, 1, 1, 1, 1</math>, and then <math>0, 0, 0, 0, 0, 0, 0, 0</math>. This sequence is clearly graphic, as it is the simple graph of <math>8</math> isolated vertices.

To show an example of a non-graphic sequence, let <math>6, 5, 5, 4, 3, 2, 1</math> be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree <math>6</math> vertex and all its incident edges to get <math>4, 4, 3, 2, 1, 0</math>. Already, we know this degree sequence is not graphic, since it claims to have <math>6</math> vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is <math>4</math>. This means that two of the vertices are connected to all the other vertices with the exception of the isolated one, so the minimum degree of each vertex should be <math>2</math>; however, the sequence claims to have a vertex with degree <math>1</math>. Thus, the sequence is not graphic.

For the sake of the algorithm, if we were to reiterate the process, we would get <math>3, 2, 1, 0, 0</math> which is yet more clearly not graphic. One vertex claims to have a degree of <math>3</math>, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

See also

• Erdős–Gallai theorem

References

• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation
• West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.