of allowed transitions (see the additional window at right bottom side).

However in common the direct use of this algorithm does not allow to solve the problem of -compatible path with maximal number of edges constructing. Actually the matching of maximal cardinality for graph cannot contain the pairs of edges forming forbidden transition because these edges are incident to one common vertex of graph. At the same time, in common there may exist -compatible path containing such a pair of edges.

For example, for graph G presented on figure 2 the path

in principle cannot be received by constructing the matching of maximal weight for graph. This path begins from edge and ends by edge. These edges form forbidden transition, , consequently, graph does not contain the alternate path with both of these edges.

Thus, the question of multipartite graph recognition is still open as well as the problem of allowed path constructing or finding the set of paths covering all the edges of initial graph G.

3. Algorithm for Constructing of Compatible Eulerian Trails

In the previous section the restrictions for paths were stated in the terms of allowed transitions system [7]. It’s shown that the problem of constructing the allowed path in graph G can be solved by polynomial time if a system of transitions consists only of matchings and full multipartite graphs. It’s trivial to recognize if graph of allowed transitions belongs to the class of matchings. If we want recognize if transitions graph belongs to class of full multipartite graphs it’s expedient to use the definition of partition system [3-5,8].

The conception of partition system is used for definition of allowed trail in terms of forbidden transitions.

Definition 4. Let be a graph. Let be some partition of set. Then the partition system of graph G be the system of sets .

Definition 5. Let,. A trail not containing the transitions and can be called -compatible, and transitions and are forbidden.

Let's admit that graph of allowed transitions unambiguously defines the graph of forbidden transitions which is the complement of allowed transitions graph to full graph. Thus, using definitions 1-3 the problem either with use of allowed transitions or forbidden transitions can be stated.

So the partition system is defined on the set of (the set of vertices incident to v). If edges and belong to one subset then edge cannot be placed after the edge in a trail. Let graph be defined by the adjacency list. Its elements are the structures. Each element of this structure consists of two fields: vertex number (this vertex is adjacent to the current one); the number of partition element. To define the degree of the current vertex it is enough to count the number of elements of adjacency list.

Let’s admit that each edge e belongs to two adjacency lists of vertices and (the ends of an edge). But for each vertex edge e belongs to different partition systems.

Input data are represented by the following list vector < list < pair > > Graph;

All data are represented by a vector of vertices, each element of this vector is a list of pairs. The first pair of each list is a vertex number, the second one is its degree. The other pairs represent the numbers of adjacent vertices and number of corresponding partition set.

On the other side, graph of allowed transitions defined by partition system cannot be arbitrary, and belongs to class M of full multipartite graphs: the elements of partition define the parts of graph, and set of its edges

.s Graph of forbidden transitions in this case will consist of cliques, this fact can be used for recognition if using algorithm [9].

As it was considered earlier, algorithm of S. Szeider in common does not allow constructing of allowed trails having maximal length. The most interesting are allowed Eulerian trails. The necessary and sufficient condition for -compatible trails existence is proved by the following theorem [8].

Theorem 2 [A. Kotzig]. Connected Eulerian graph G has -compatible Eulerian trail if and only if

.

Obviously, complexity of checking the condition of existence of -compatible Eulerian trail is not more than.

Let’s list the algorithm for construction of compatible trail.

Algorithm P_G-Compatible Eulerian Trail

• Input data:

• Eulerian graph• Transitions system .

• Output data:

• Allowed Eulerian cycle.

Step 1. Let,.

Step 2. Find a vertex v for which.

Step 3. Find element of partition system containing maximal number of edges. It’s enough to look through the adjacency list of current vertex v and count how many times each element of partition meets at this list. Choosing this element we get a class

.

Step 4. Find any edges and . If it’s possible choose edges and incident to vertices of degree more than 2. If set then stop: there is no -compatible Eulerian trail. Otherwise go to step 5.

Step 5. Construct graph by detaching vertex, to which only edges and are incident, from vertex v. The other edges are kept incident to vertex v.

Step 6. Let class contains the edge. Exclude vertices and from partition system. Define.

For further modification of partition system define the following.

Step 6.1. All partition systems not containing vertex v are taken to the modified system without any changes.

Step 6.2. If systems and had been consisted of one edge then.

Step 6.3. If then

.

Step 6.4. If then

.

Step 6.5. Construct

.

Step 7. Define the value

.

Let’s admit that the number of edges is a constant value and the number of vertices is increased by 1.

Step 8. If, let and go to step 2 for graph. Otherwise go to step 9.

Step 9. Choose any vertex v and mark all achievable vertices. If there are unmarked vertices go to step 10 otherwise stop the received graph is Eulerian trail without forbidden transitions.

Step 10. Get vertices and from a list of marked and unmarked vertices of graph. These vertices are split from vertex v of graph. Unite them to one vertex. There we get a modified graph. Let.

Step 11. Choose edges and

so thatand

. If set then stop: there is no -compatible Eulerian trail. Otherwise construct graph by splitting vertex from vertex Only edges and are incident to vertex. All other edges are incident to vertex and go to step 9.

The following theorem is proved in [9].

Theorem 3. Algorithm -compatible Eulerian trail correctly solves the problem of constructing the - compatible Eulerian trail.

That paper also shows that computing complexity of this algorithm is

.

Thus, the constructed algorithms are resolved by the polynomial time and can be simply realized using standard computing facilities.

Let’s consider the allowed trail construction for a graph on figure 5. Let its transitions system is as shown in a table below. The numbers in white circles show the number of partition system the edge belongs for each vertex.

Let’s construct allowed Eulerian cycle beginning and ending at vertex 1. At the first iteration the first vertex is split. To simplify the illustration let’s consider the “short version” of vertex splitting (the example of “full version” is presented on figure 3). Figure 6 and table show graph with split vertex 1 and a list of connectivity where

new or modified elements are colored by gray.

Figures 7-12 and tables under them represent all other iterations of algorithm.

In result graph is split into a simple cycle. It’s possible to construct allowed Eulerian cycle beginning at any its vertex. For example, the following cycle beginning at vertex 1 can be constructed:

It’s possible to recognize the system of transitions and to solve the problem of constructing the allowable path by linear time. It’s also possible to find -allowable Eulerian cycle for Eulerian graph or to proclaim that such a cycle does not exist. This problem can be solved by the time using algorithm - compatible Eulerian trail.

4. Acknowledgements

The research is supported by the Ministry of Education and Science of Russian Federation, contract 14.B37.21. 0395.

REFERENCES