The Little algorithm is used to find solutions to the traveling salesman problem in the form of a Hamiltonian contour . This algorithm is used to find the optimal Hamiltonian contour in a graph with N vertices, each vertex i being connected to any other vertex j by a bidirectional arc. Each arc is assigned a weight Сi, j, and the weights of the arcs are strictly positive (Сi, j ≥ 0). The weights of the arcs form a cost matrix. All elements along the diagonal of the matrix equate to infinity (Cj, j = ∞).

If the pair of vertices i and j is not interconnected (the graph is not fully connected), then we assign to the corresponding element of the cost matrix a weight equal to the length of the minimum path between the vertices i and j. If in the end the arc (i, j) enters the resulting contour, then it must be replaced by the corresponding path. The matrix of optimal paths between all vertices of the graph can be obtained by applying the Danzig or Floyd algorithm.

The Little’s algorithm is a special case of applying the branch and bound method to a specific problem. The general idea is trivial: you need to divide a huge number of enumerated variants into classes and get estimates (from below - in the minimization problem, from above - in the maximization problem) for these classes, in order to be able to discard the variants not by one, but by whole classes. The difficulty is to find such a division into classes (branches) and such assessments (boundaries) so that the procedure is effective.

Little algorithm

1. In each row of the cost matrix, we find the minimum element and subtract it from all the elements of the line. We will do this for non-zero columns. We obtain a cost matrix, each row and each column of which contains at least one zero element.
2. For each zero element of the matrix cij, we calculate the coefficient Гi, j, which is equal to the sum of the smallest element i of the row (excluding the element Сi, j = 0) and the smallest element j of the column. From all the coefficients Γi, j we choose one that is the maximum Γk, l = max {Γi, j}. The corresponding arc (k, l) is inserted into the Hamiltonian contour.
3. Remove the kth row and column l, change the value of the element Cl, k to infinity (since the arc (k, l) is included in the contour, the return path from l to k is invalid).
4. We repeat the algorithm of step 1 until the matrix order becomes equal to two.
5. Then, in the current directed graph, we introduce two missing arcs, which are determined uniquely by a matrix of order 2. We obtain a Hamiltonian contour.

During the solution, the current value of the lower limit is continuously calculated. The lower bound is the sum of all subtracted items in the rows and columns. The final value of the lower bound should coincide with the length of the resulting contour.

Algorithm Little - Example 1

It is necessary to find the best route for a traveling salesman in the graph presented in the figure:

Let us number the vertices of the original graph, and compose a matrix of lengths of shortest arcs between each pair of vertices D0, if there is no arc between the vertex i and j, the value ∞ is assigned to the matrix element di, j. The original graph with numbered vertices is shown in the figure below.

Matrix D0:

The matrix D0 contains elements with values ​​of ∞, which is not permissible. Replace the infinite arcs by the length of the shortest paths between the corresponding vertices (with the exception of the diagonal elements to which we assign infinity values). As a result, we obtain the following cost matrix:

Since its elements are no longer arcs but distances between vertices, we are freed from the need to check the triangle inequality (in this case, it is performed automatically).

We will find the minimum elements in each line and then subtract it from the remaining elements of the line (the minimum elements are written opposite the corresponding lines). We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G1,2 = 0, G1.4 = 14, G2.1 = 9, G2.3 = 0, G3.2 = 0, G3.5 = 8, G4.3 = 9, G5.6 = 2, G6, 7 = 14, G7.6 = 14,
As a result of the comparison, we obtained 3 identical maximal G = 14. This means that the algorithm forks and we must consider all the resulting options one by one. Consider option G1.4 = 14
We remove from the cost matrix row 1 and column 4. We enter an arc (1,4) into the current oriented graph

In line 4 and column 1 there is no element equal to ∞. Assign the infinity value to the element (4.1) to avoid premature loop closure.
Current Lower Bound = 87
The lower bound is the sum of all subtracted items in the rows and columns. The final value of the lower bound should coincide with the length of the resulting contour.
We will find the minimum elements in each line and then subtract it from the remaining elements of the line (the minimum elements are written opposite the corresponding lines). We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G2,1 = 10, G2.3 = 0, G3.2 = 10, G3.5 = 8, G4.3 = 10, G5.6 = 2, G6.7 = 14, G7.6 = 14,
As a result of the comparison, we obtained 2 identical maximal G = 14. This means that the algorithm forks and we must consider all the resulting options one by one. Consider option G6.7 = 14
Remove from the cost matrix row 6 and column 7. We enter in the current oriented graph an arc (6.7)

In line 7 and column 6 there is no element equal to ∞. Assign the infinity value to the element (7,6) to avoid premature loop closure.
Current Lower Bound = 87
We will find the minimum elements in each line and then subtract it from the remaining elements of the line (the minimum elements are written opposite the corresponding lines). We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G2,1 = 10, G2.3 = 0, G3.2 = 10, G3.5 = 0, G4.3 = 10, G5.6 = 10, G7.5 = 10,
As a result of the comparison, we obtained 5 identical maximal G = 10. This means that the algorithm forks and we must consider all the resulting options one by one. Consider the option G2.1 = 10
Remove from the cost matrix row 2 and column 1. We enter in the current oriented graph an arc (2.1)

In line 4 and column 2 there is no element equal to ∞. Assign the infinity value to the element (4.2) to avoid premature loop closure.
Current Lower Bound = 101
We will find the minimum elements in each line and then subtract it from the remaining elements of the line (the minimum elements are written opposite the corresponding lines). We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G3,2 = 12, G3.5 = 0, G4.3 = 12, G5.6 = 10, G7.5 = 10,
As a result of the comparison, we obtained 2 identical maximal G = 12. This means that the algorithm forks and we must consider all the resulting variants in turn. Consider the variant G3.2 = 12
Remove from the cost matrix row 3 and column 2. We enter in the current oriented graph an arc (3.2)

In line 4 and column 3 there is no element equal to ∞. Assign the infinity value to the element (4.3) to avoid premature loop closure.
Current Lower Bound = 101
We will find the minimum elements in each line and then subtract it from the remaining elements of the line (the minimum elements are written opposite the corresponding lines). We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G4.5 = 8, G5.3 = 8, G5.6 = 8, G7.5 = 8,
As a result of the comparison, we obtained 4 identical maximal G = 8. This means that the algorithm forks and we must consider all the resulting options one by one. Consider option G4.5 = 8
We remove from the cost matrix row 4 and column 5. We enter an arc (4,5) into the current oriented graph

In line 5 and column 3 there is no element equal to ∞. Assign the infinity value to the element (5.3) to avoid premature loop closure.
Current Lower Limit = 113
After the rank of the matrix becomes equal to two, we get zeros in each of its rows and columns (adding the matrix elements to the lower border as previously subtracted), and add zero elements to the route of the comivagent of the arc.
NGr = 121
The traveling salesman route includes arcs :, (1, 4), (6, 7), (2, 1), (3, 2), (4, 5), (5, 6), (7, 3)
-------------------------------------------------- -----------------------
Let us return to the branching that has arisen in us and consider the case in which the maximum value is G7.5. We remove from the cost matrix row 5 and column 7. We enter an arc (7.5) into the current oriented graph

In line 5 and column 6 there is no element equal to ∞. Assign the infinity value to the element (5.6) to avoid premature loop closure.
After the rank of the matrix becomes equal to two, we get zeros in each of its rows and columns (adding the matrix elements to the lower boundary as previously subtracted), and add arcs to the route of the comivator that correspond to zero elements.
NGr = 121
The traveling salesman route includes arcs :, (1, 4), (6, 7), (2, 1), (3, 2), (7, 5), (4, 6), (5, 3)
-------------------------------------------------- -----------------------
Let us return to the branching that has arisen in us and consider the case in which the maximum value is G5.6. Remove from the cost matrix row 6 and column 5. We enter in the current oriented graph an arc (5,6)

In line 7 and column 5 there is no element equal to ∞. Assign the infinity value to the element (7.5) to avoid premature loop closure.
After the rank of the matrix becomes equal to two, we get zeros in each of its rows and columns (adding the matrix elements to the lower boundary as previously subtracted), and add arcs to the route of the comivator that correspond to zero elements.
NGr = 121
The traveling salesman route includes arcs :, (1, 4), (6, 7), (2, 1), (3, 2), (5, 6), (4, 5), (7, 3)
-------------------------------------------------- -----------------------
Let us return to the branching that has arisen in us and consider the case in which the maximum value is G5.3. Remove from the cost matrix row 3 and column 5. We enter an arc (5.3) into the current oriented graph

In line 4 and column 5 there is no element equal to ∞. Assign the infinity value to the element (4,5) to avoid premature loop closure.
After the rank of the matrix becomes equal to two, we get zeros in each of its rows and columns (adding the matrix elements to the lower boundary as previously subtracted), and add arcs to the route of the comivator that correspond to zero elements.
NGr = 121
The traveling salesman route includes arcs :, (1, 4), (6, 7), (2, 1), (3, 2), (5, 3), (4, 6), (7, 5)
-------------------------------------------------- --------------------

We will not consider the remaining branches of the algorithm. Let us say at once that we have already obtained the optimal solution (all three circuits obtained by us have the same value of the lower limit equal to 121, therefore each of them sets the best route for the traveling salesman). Consider the first variant we obtained: (1, 4), (6, 7), (2, 1), (3, 2), (7, 5), (4, 6), (5, 3).

Recall that in the process of solving we replaced some elements of the cost matrix (which by default are arcs of the graph) with paths between the corresponding vertices. Now, if such arcs are present in the composition of the obtained optimal contour, it is necessary to replace them with these paths (for this, the shortest path table, previously obtained using the Floyd or Danzig algorithm, is used). The arc (1, 4) corresponds to the path (1, 4); arc (6, 7) - the path (6, 7); arc (2, 1) corresponds to the path (2, 1); arc (3, 2) - the path (3,2); arc (5, 3) corresponds to the path (5, 3); arc (7, 5) - path 7-6-5; the arc (4, 6) - the path 4-3-5-6. That is the optimal contour for our graph: 1-4-3-5-6-7-6-5-3-2-1 with a length of 121 units.

Algorithm Little - Example 2

There is a layout of N subscribers of a local computer network. Physical topology is a ring.
It is necessary to choose the route of organization of subscribers to the network, taking into account the selection criteria - the minimum cable spent (figures are given in meters).
The number of subscribers is N = 10. The matrix of distances between subscribers is presented below.

Let us move from the distance matrix to the cost matrix, assigning the values ​​of infinity to the diagonal element. Since the problem is geometric, the triangle inequality holds for it, and we can search for a solution in the form of a Hamiltonian contour.

Find the minimum elements in each row and then subtract it from the remaining elements of the line. We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G1.8 = 4.2, G2.5 = 13.8, G2.6 = 4.2, G3.4 = 27.5, G4.3 = 40.4, G5.2 = 6.9, G5.7 = 19.2, G5.8 = 0, G6, 1 = 18.1, G7.9 = 0, G7.10 = 0, G8.9 = 0, G8.10 = 0, G9.10 = 18, G10.9 = 18,
The maximum value is G4.3 = 40.4
Remove the row 4 and column 3 from the cost matrix, and assign the infinity value to the element (3.4). Fill in the current oriented graph arc (4,3)

Current Lower Bound = 282.9
The lower bound is the sum of all subtracted items in the rows and columns. The final value of the lower bound should coincide with the length of the resulting contour.
Find the minimum elements in each row and then subtract it from the remaining elements of the line. We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G1.4 = 19, G1.8 = 0, G2.5 = 13.8, G2.6 = 4.2, G3.9 = 0, G3.10 = 0, G5.2 = 6.9, G5.7 = 10.2, G5, 8 = 0, G6.1 = 18.1, G7.9 = 0, G7.10 = 0, G8.9 = 0, G8.10 = 0, G9.10 = 18, G10.9 = 18,
The maximum value is G1,4 = 19
We remove from the cost matrix row 1 and column 4. We enter an arc (1,4) into the current oriented graph

In line 3 and column 1 there is no element equal to ∞. Assign the infinity value to the element (3.1) to avoid premature loop closure.
Current Lower Bound = 310.4
Find the minimum elements in each row and then subtract it from the remaining elements of the line. We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G2.5 = 13.8, G2.6 = 26.6, G3.9 = 0, G3.10 = 0, G5.2 = 6.9, G5.7 = 10.2, G5.8 = 10.7, G6.1 = 18.1, G7, 9 = 0, G7.10 = 0, G8.9 = 0, G8.10 = 0, G9.10 = 18, G10.9 = 18,
The maximum value is G2,6 = 26.6
Remove from the cost matrix row 2 and column 6. Fill in the current oriented graph arc (2.6)

In line 6 and column 2 there is no element equal to ∞. Assign the infinity value to the element (6.2) to avoid premature loop closure.
Current Lower Bound = 310.4
Find the minimum elements in each row and then subtract it from the remaining elements of the line. We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

For each zero element, we calculate the value Гij equal to the sum of the smallest element i of the row (excluding the element Сij = 0) and the smallest element j of the column.
G3.9 = 0, G3.10 = 0, G5.2 = 39, G5.7 = 10.2, G5.8 = 10.7, G6.1 = 30.9, G7.5 = 8.5, G7.9 = 0, G7, 10 = 0, G8.9 = 0, G8.10 = 0, G9.10 = 18, G10.9 = 18,
The maximum value is G5,2 = 39
Remove the row 5 and column 2 from the cost matrix. Introduce an arc (5.2) into the current oriented graph

In line 6 and column 5 there is no element equal to ∞. Assign the infinity value to the element (6.5) to avoid premature loop closure.
Current Lower Bound = 324.2
Find the minimum elements in each row and then subtract it from the remaining elements of the line. We get the matrix presented below.

We will do the same for non-zero columns. We obtain a matrix containing zeros in each row and each column.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г3,7=9, Г3,9=0, Г3,10=0, Г6,1=20.4, Г7,5=8.5, Г7,8=4.4, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г6,1=20.4
Удалим из матрицы стоимости строку 6 и столбец 1. Внесем в текущий ориентированный граф дугу (6,1)

В строке 3 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (3,5) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=345.1
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки. Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г3,7=9, Г3,9=0, Г3,10=0, Г7,5=8.5, Г7,8=4.4, Г7,9=0, Г7,10=0, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г3,7=9
Удалим из матрицы стоимости строку 3 и столбец 7. Внесем в текущий ориентированный граф дугу (3,7)

В строке 7 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (7,5) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=345.1
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г7,8=7.3, Г7,9=0, Г7,10=0, Г8,5=28.7, Г8,9=0, Г8,10=0, Г9,10=7.3, Г10,9=7.3,
Максимальное значение имеет Г8,5=28.7
Удалим из матрицы стоимости строку 8 и столбец 5. Внесем в текущий ориентированный граф дугу (8,5)

В строке 7 и столбце 8 отсутствует элемент равный ∞. Присвоим элементу (7,8) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=353.6
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.

То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.

Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.
Г7,9=0, Г7,10=0, Г9,8=0, Г9,10=0, Г10,8=0, Г10,9=0,
В результате сравнения мы получили 6 одинаковых максимальных Г=0. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно.Рассмотрим вариант Г9,8=0
Удалим из матрицы стоимости строку 9 и столбец 8. Внесем в текущий ориентированный граф дугу (9,8)

В строке 7 и столбце 9 отсутствует элемент равный ∞. Присвоим элементу (7,9) значение бесконечности чтобы избежать преждевременногог замыкания контура.
Текущая Нижняя граница=360.9
После того, как ранг матрицы становится равным двум мы получае нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (9, 8), (7, 10), (10, 9)
-------------------------------------------------- -----------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г10,9. Удалим из матрицы стоимости строку 9 и столбец 10. Внесем в текущий ориентированный граф дугу (10,9)

В строке 7 и столбце 8 отсутствует элемент равный ∞. Присвоим элементу (7,8) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (10, 9), (7, 10), (9, 8)
-------------------------------------------------- -----------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г10,8. Удалим из матрицы стоимости строку 8 и столбец 10. Внесем в текущий ориентированный граф дугу (10,8)

В строке 7 и столбце 9 отсутствует элемент равный ∞. Присвоим элементу (7,9) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (10, 8), (7, 9), (9, 10)
-------------------------------------------------- -----------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г9,10. Удалим из матрицы стоимости строку 10 и столбец 9. Внесем в текущий ориентированный граф дугу (9,10)

В строке 7 и столбце 8 отсутствует элемент равный ∞. Присвоим элементу (7,8) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (9, 10), (7, 9), (10, 8)
-------------------------------------------------- -----------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,10. Удалим из матрицы стоимости строку 10 и столбец 7. Внесем в текущий ориентированный граф дугу (7,10)

В строке 9 и столбце 8 отсутствует элемент равный ∞. Присвоим элементу (9,8) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (7, 10), (9, 8), (10, 9)
-------------------------------------------------- -----------------------
Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,9. Удалим из матрицы стоимости строку 9 и столбец 7. Внесем в текущий ориентированный граф дугу (7,9)

В строке 9 и столбце 8 отсутствует элемент равный ∞. Присвоим элементу (9,8) значение бесконечности чтобы избежать преждевременногог замыкания контура.
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтеные элементы матрицы к нижней границе), и добавляем к маршруту комивояжера дуги которым соответствуют нулевые элементы.
НГр=360.9
Маршрут коммивояжера включает в себя дуги:, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (7, 9), (9, 10), (10, 8)
-------------------------------------------------- -----------------------


We have considered all possible branches of the algorithm, now it is necessary to choose from the values ​​obtained as a result of consideration of each branch of the values ​​of the lower boundary - the minimum. This will be the optimal length of the traveling salesman path.
The minimum value is NGr = 360.9. The
corresponding optimal contour includes arcs :, (4, 3), (1, 4), (2, 6), (5, 2), (6, 1), (3, 7), (8, 5), (9, 8), (7, 10), (10, 9)