Abstract
In this paper, we study undirected multiple graphs of any natural multiplicity \(k > 1\) . There are edges of three types: ordinary edges, multiple edges, and multi-edges. Each edge of the last two types is a union of \(k\) linked edges, which connect 2 or \((k + 1)\) vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of \(k\) linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in a graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by \(k\) indices of the ordinary edges reachability sets, which are incident to some multi-edge.
