The university asked to solve the problem of Chinese pochtalona.Vot algorithm to solve it.

1. We look whether we caught Euler graph. If yes go to step (5).

2. Building a distance matrix for graphs with vertices of odd degree.

3. Building a minimum matching.

4. I found the steam build our imaginary puti.Teper Euler graph.

5. Find the Euler cycle and it will be the answer to our problem.
   The problem with paragraph 5, if the graph was not originally Euler. Displays not clear the way for me. He tried to find the error did not work.
   Adjacency matrix is ​​given as
   0 1 1 0
   1 0 1 1
   1 1 0 2
   0 2 1 0
   Where the numbers greater than 0 means the number of ways, including mnimyh.Pri a matrix output values
   01133210

   private List & lt; Integer & gt; eilerPath (int [] [] matrixAdjacency) {
      Stack & lt; Integer & gt; stack = new Stack & lt; & gt; ();
      List & lt; Integer & gt; list = new ArrayList & lt; & gt; ();
      int v = 0;
      int u;
      int edge;
      stack.push (v);
      while (! stack.empty ()) {
        edge = findAdjacencyVertex (matrixAdjacency, stack.peek ());
        if (edge ​​== -1) {
          list.add (stack.pop ());
        } else {
          u = edge;
          matrixAdjacency [stack.peek ()] [u] -;
          matrixAdjacency [u] [stack.peek ()] -;
          stack.push (u);
        }
      }
    RETURN LIST;
    }
    private int findAdjacencyVertex (int [] [] matrixAdjacency, int edge) {
      for (int i = 0; i & lt; matrixAdjacency.length; i ++) {
        if (matrixAdjacency [edge] [i] & gt; 0) {
          return i;
        }
      }
      Return -1;
    }
   

Answer 1

The algorithm is fully working. I found at fault in another place in the code. Not quite right adjacency matrix was constructed with imaginary ways. In some places, they just did not add because of what occurred the way with an odd number of ribs.