Lobachevskii Journal of Mathematics

http://ljm.ksu.ru
ISSN 1818-9962

Vol. 22, 2006, 35–46 \begin{matrix}c \\ ◯ \end{matrix} A. V. Lapteva, E. I. Yakovlev

A. V. Lapteva and E. I. Yakovlev

INDEX VECTOR-FUNCTION AND MINIMAL CYCLES

(submitted by B. N. Shapukov)

Abstract. Let P be a closed triangulated manifold, dim P = n. We consider the group of simplicial 1-chains C_{1}(P) = C_{1}(P, ℤ_{2}) and the homology group H_{1}(P) = H_{1}(P, ℤ_{2}). We also use some nonnegative weighting function L : C_{1}(P) → ℝ. For any homological class [x] ∈ H_{1}(P) the method proposed in article builds a cycle z ∈ [x] with minimal weight L(z). The main idea is in using a simplicial scheme of space of the regular covering p : P̂ → P with automorphism group G ≅ H_{1}(P). We construct this covering applying the index vector-function J : C_{1}(P) → ℤ_{2}^{r} relative to any basis of group H_{n−1}(P), r = rank H_{n−1}(P).

1. Index Vector-Function

Consider a triangulated closed manifold P, dim P = n, and a basis [z_{1}^{n−1}], …, [z_{r}^{n−1}] of homology group H_{n−1}(P) = H_{n−1}(P, ℤ_{2}). Let Ind : H_{1}(P) × H_{n−1}(P) → ℤ_{2} be the intersection index.

Definition 1. Define the homomorphism J_{0} : Z_{1}(P) → ℤ_{2}^{r} by J_{0}^{k}(y) = Ind([y], [z_{k}^{n−1}]), k = 1, …, r, J_{0} = (J_{0}^{1}, …, J_{0}^{r}). We call its arbitrary extension J : C_{1}(P) → ℤ_{2}^{r} the index vector-function. For any chain x ∈ C_{1}(P) the value J(x) is called its index relative to the basis [z_{1}^{n−1}], …, [z_{r}^{n−1}].

2000 Mathematical Subject Classification. 57Q15, 57N65, 65D18. Key words and phrases. Triangulated manifold, homology group, minimal

cycle, intersection index, regular covering.

Remark 1. The index vector-function J : C_{1}(P) → ℤ_{2}^{r} is not uniquely defined, however we can use this function for solve our problems.

Proposition 1. If J : C_{1}(P) → ℤ_{2}^{r} is the index vector-function relative to the basis {[z_{1}^{n−1}], …, [z_{r}^{n−1}]} of group H_{n−1}(P), x, y ∈ C_{1}(P) and ∂x = ∂y, then J(x) = J(y) if and only if x ∼ y.

Proof. Let {[z_{1}^{1}], …, [z_{r}^{1}]} be a basis of group H_{1}(P) = H_{1}(P, ℤ_{2}), that is dual to the given basis {[z_{1}^{n−1}], …, [z_{r}^{n−1}]}. Assume now that z = x + y. Then z ∈ Z_{1}(P) and [z] = ∑_{i=1}^{r} l^{i}[z_{i}^{1}], where l_{i} ∈ ℤ_{2}. This implies that J^{k}(z) = Ind([z], [z_{k}^{n−1}]) = l^{k} for all k = 1, …, r. So J(x) = J(y) if and only if l^{1} = ⋯ = l^{r} = 0. And this latter expression is equivalent to the equality [z] = 0. □

ALGORITHM 1. Construction of index vector-function relative to the basis of group H_{n−1}(P). Input:

1) simple basis cycles z_{1}^{n−1}, z_{2}^{n−1}, …, z_{r}^{n−1} which are lists of (n − 1)- dimensional simplices;

2) list K^{1}(P) of edges for polyhedron P;

3) lists K_{1}^{n}(P, z_{1}^{n−1}), …, K_{r}^{n}(P, z_{r}^{n−1}) consisting of n-dimensional simplices from neighborhoods of cycles z_{1}^{n−1}, …, z_{r}^{n−1} respectively; Output:

1) vectors J(a) = (J^{1}(a), …, J^{r}(a)) ∈ ℤ_{2}^{r} for all edges a ∈ K^{1}(P);

2) chains M_{1}, …, M_{r} of edges indexed relative to cycles z_{1}^{n−1}, …, z_{r}^{n−1} respectively;

3) lists M_{k}(u), k = 1, …, r of edges, that we add to M_{k} when considering vertex u of cycle z_{k}^{n−1};

4) sets Σ_{k}(u), k = 1, …, r of n-simplices incident to edges from M_{k}(u).

Algorithm Description.

Step 0. For all k = 1, …, r execute steps 1 – 3.

Step 1. Start operations. Assume M_{k} = ∅, J^{k}(a) := 0 for all a ∈ K^{1}(P). We denote z_{k}^{n−1} by X and K_{k}^{n}(P, z_{k}^{n−1}) by K^{n}(P, X). We create then lists of vertices and edges for all simplices of cycle X, K^{0}(X) and K^{1}(X) respectively.

Step 2. Indexing edges that do not belong to the cycle. For each vertex u ∈ K^{0}(X) execute steps 2.1 – 2.4.

Step 2.1. Initializing vertex neighborhood. Let us create a list K^{n}(P, u) ⊂ K^{n}(P, X) of n-dimensional simplices of the polyhedron P, that contain u, and a list K^{n−1}(P, u) of all (n − 1)-dimensional faces of simplices from K^{n}(P, u). At the same time, for each simplex σ^{n−1} ∈ K^{n−1}(P, u) we get a list ∂^{n−1}(σ^{n−1}, u) of n-dimensional simplices from K^{n}(P, u) those are incident to σ^{n−1}, and assume μ(σ^{n−1}) := 0. Then we create empty lists M_{k}(u) := ∅ and Σ_{k}(u) := ∅.

Step 2.2. Creating the queue to keep n-simplices. We chose a simplex σ_{0}^{n} ∈ K^{n}(P, u), create a queue R := {σ_{0}^{n}} and remove σ_{0}^{n} from K^{n}(P, u).

Step 2.3. Main procedure of Algorithm. While the queue R is not empty we will do the following actions. Take the first simplex σ^{n} ∈ R and remove it from the queue R. For each (n−1)-dimensional face σ^{n−1} of the simplex σ^{n} we check the following: whether it belongs to the cycle X, whether μ(σ^{n−1}) is equal to zero, whether the list ∂^{n−1}(σ^{n−1}, u) contains any simplices different from σ^{n}. If all above conditions are satisfied we will execute steps 2.3.1 – 2.3.2.

Step 2.3.1. Take the simplex σ_{∗}^{n} ∈ ∂^{n−1}(σ^{n−1}, u) \ {σ^{n}}, remove it from K^{n}(P, u) and enqueue to R; set μ(σ^{n−1}) := 1 and Σ_{k}(u) = Σ_{k}(u) ∪ {σ_{∗}^{n}}.

Step 2.3.2. For all vertices w ≠ u of the simplex σ^{n−1} we check whether the edge a = [uw] is in the list K^{1}(X); having a ∉ K^{1}(X) set J^{k}(a) := J^{k}(a)+1 mod 2, M_{k}(u) = M_{k}(u)∪{a}, M_{k} := M_{k} +a mod 2.

Step 2.4. Main procedure repeated. If the list M_{k}(u) is empty then go back to step 2.2.

Step 3. Indexing the edges of cycle. For each edge a = [uv] ∈ K^{1}(X) we search any edges b ∈ M_{k}(u) and c ∈ M_{k}(v) such that b ∩ c ≠ ∅ and that a, b and c are sides of some triangle of polyhedron P. If the edges b and c do not exist then we set J^{k}(a) := 1 and M_{k} = M_{k} + a mod 2. End of algorithm.

Theorem 1. If P is a closed n-dimensional manifold, z_{1}^{n−1}, …, z_{r}^{n−1} are simple cycles, x = a_{1} + ⋯ + a_{l} ∈ C_{1}(P) and J(x) = ∑_{i=1}^{l} J(a_{i}), then the vector J(x) = (J^{1}(x), …, J^{r}(x)) ∈ ℤ_{2}^{r} is the index of the chain x ∈ C_{1}(P) relative to the basis [z_{1}^{n−1}], …, [z_{r}^{n−1}] of group H_{n−1}(P).

Proof. Let x ∈ Z_{1}(P). We will prove that J^{k}(x) = Ind([x], [z_{k}^{n−1}]) for all k = 1, …, r. Set z_{0}^{∗} = z_{k}^{n−1}. For all p = 1, …, N we will make the following constructions; here N is the power of the set K^{0}(z_{k}^{n−1}). Consider a vertex u_{p} ∈ K^{0}(z_{k}^{n−1}) and its barycentric star bst(u_{p}, P).

Let Σ_{k}^{∗}(u_{p}) be the set of all n-simplices from the barycentric subdivision of Σ_{k}(u_{p}). Construct the chain c(u_{p}) of simplices σ_{1} ∈ bst(u_{p}, P)∩Σ_{k}^{∗}(u_{p}).

Then we write the chain boundary c(u_{p}) as a sum Y_{1} + Y_{2}, where Y_{1} is the sum of all its (n − 1)-dimensional simplices, that belong to the cycle z_{k}^{n−1} and Y_{2} is the sum of all remaining simplices from the chain ∂c(u_{p}). Set z_{p}^{∗} = z_{p−1}^{∗} + Y_{1} + Y_{2} mod 2.

By construction z_{p}^{∗} ∼ z_{p−1}^{∗} for all p = 1, …, N. Hence, the cycle z^{∗} = z_{N}^{∗} is homologous to the cycle z_{k}^{n−1} = z_{0}^{∗}.

Let now prove that for any edge a = [uv] ∈ K^{1}(P) and σ_{b} ∈ bst(a) the simplex σ_{b} belongs to z^{∗} if and only if a ∈ M_{k}.

Let view all possible positions of the edge a. At the same time we also agree to think that M_{k}(u) = ∅ and that Σ_{k}(u) = ∅ for all u ∉ K^{0}(z_{k}^{n−1}).

0. If a ∉ M_{k}(u) ∪ M_{k}(v) and a ∉ K^{1}(z_{k}^{n−1}), then, according to the algorithm, a ∉ M_{k}. On the other hand, the edge a can not be incident to simplices from the lists Σ_{k}(u) and Σ_{k}(v) and hence σ_{b} ∉ z^{∗}.

1. Let u ∈ K^{0}(z_{k}^{n−1}), a ∈ M_{k}(u) and v ∉ K^{0}(z_{k}^{n−1}). Then the edge a will be still in the chain M_{k} when algorithm 1 is completed. At the same time the barycentric star bst(a) belongs to the boundary of the chain c(u) and does not belong to the cycle z_{k}^{n−1}. Thus in this case a ∈ M_{k} and the chain bst(a) belongs to the cycle z^{∗}.

2. Further, assume that u, v ∈ K^{0}(z_{k}^{n−1}) and a ∈ M_{k}(u). At that, a ∉ K^{1}(z_{k}^{n−1}).

2.1. If a ∈ M_{k}(v), then a ∉ M_{k}, and simplices of its barycentric star will be added twice to the initial cycle z_{k}^{n−1} and will not be in the resulting cycle z^{∗}.

2.2. If a ∉ M_{k}(v), then a ∈ M_{k} and any simplex σ_{b} ∈ bst(a) is added to the cycle z^{∗} exactly once. So σ_{b} ∈ z^{∗}.

3. Finally, let a ∈ K^{1}(z_{k}^{n−1}).

3.1. Let assume that the condition from step 3 of algorithm 1 is satisfied, i.e.:

(∗) there exist edges b ∈ M_{k}(u) and c ∈ M_{k}(v) such that b ∩ c ≠ ∅ and that a, b and c are sides of some triangle σ′ ∈ K^{2}(P).

In this case, according to the algorithm a ∉ M_{k}.

Let view all triangles σ′ from (∗), and all n-dimensional simplices incident to them. The such n-simplices belong both to Σ_{k}(u) and Σ_{k}(v). Consider an n-dimensional simplex σ, σ_{b} ∈ σ. If σ_{b} ∈ bst(a), then σ either belongs to the both sets Σ_{k}(u) and Σ_{k}(v) or does not belong to them. Hence, the simplex σ_{b} either is not added to the cycle z^{∗} or is added twice. Therefore σ_{b} ∉ z^{∗}.

3.2. Assume now that condition (∗) is not satisfied. Then according to step 3 of algorithm 1, a ∈ M_{k}.

Barycentric star bst(a) of the edge a = [uv] belongs to the union D(a) of all n-simplices that contain the edge a. We will prove that the subpolyhedron D(a) belongs to the union of simplices from the sets Σ_{k}(u) and Σ_{k}(v).

The cycle z_{k}^{n−1} divides D(a) into two components of strong connectivity D^{+}(a) and D^{−}(a).

By construction the set Σ_{k}(u) can not be empty. Moreover, if the simplex σ ∈ z_{k}^{n−1} is incident to the vertex u, then σ is a face of some nsimplex from Σ_{k}(u). So there exists a simplex σ^{n} ∈ Σ_{k}(u) that contains the edge a.

Let the simplex σ^{n} belong to D^{+}(a). Then under the strong connectivity D^{+}(a) and according to algorithm 1, all n-simplices from D^{+}(a) also belong to Σ_{k}(u).

This implies, in accordance with our assumption, that no n-simplex from D^{+}(a) can belong to the set Σ_{k}(v).

The set Σ_{k}(v) cannot be empty also. Since each simplex of z_{k}^{n−1} incident to the vertex v is a face of some n-simplex from Σ_{k}(v), it follows that there exists a simplex σ_{∗}^{n} ∈ Σ_{k}(v) that contains the edge a. By the above proof, σ_{∗}^{n} belongs to D^{−}(a). Then all n-simplices from D^{−}(a) belong to the set Σ_{k}(v), too. Consequently all n-simplices of the polyhedron D(a) = D^{+}(a) ∪ D^{−}(a) belong either to the set Σ_{k}(u) or to Σ_{k}(v).

Consider σ_{b} ∈ bst(a). If there exists a simplex σ ∈ Σ_{k}(u) containing σ_{b}, then σ ∉ Σ_{k}(v). Otherwise, in accordance to the above proof, there is a simplex σ̃ ∈ Σ_{k}(v) such that σ_{b} ⊂ σ̃. It follows that σ_{b} is involved in the cycle z^{∗} exactly once, so σ_{b} ∈ z^{∗}.

Thus we have proved that the cycle z^{∗} ∼ z_{k}^{n−1} consists of barycentric stars of the edges from chain M_{k}. That means that this cycle intersects transversally only the edges of the cycle x, that are in the list M_{k}. According to algorithm 1 J^{k}(a) = 1 for all a ∈ M_{k} and J^{k}(b) = 0 for all edges b ∉ M_{k}. So

Ind([x], [z_{k}^{n−1}]) = Ind([x], [z^{∗}]) = ∑_{a∈x} J^{k}(a) mod 2 = J^{k}(x).
□

Remark 2. The fact that [z_{1}^{n−1}], …, [z_{r}^{n−1}] is a basis of group H_{n−1}(P) has no impact on the behavior of algorithm 1. So we can apply this algorithm to an arbitrary set of simple (n − 1)-dimensional cycles of the manifold P. In particular this set may consist of only one cycle z^{n−1}. Then we will get a function J : C_{1}(P) → ℤ_{2} such that ∑_{i=1}^{l} J(a_{i}) = Ind([x], [z^{n−1}]) for x = a_{1} + ⋯ + a_{l} ∈ Z_{1}(P). So we can use algorithm 1 to compute the intersection index of a given (n − 1)-cycle z^{n−1} ∈ Z_{n−1}(P) with any one-dimensional cycle of the manifold P.

Remark 3. We can find any basis [z_{1}^{n−1}], …, [z_{r}^{n−1}] of group H_{n−1}(P) using standard matrix algorithm (see, for example, [1], chapter III, section 21). If n = 2, we also can apply algorithms that do not use incidence matrices (see [2, 3]).

2. Regular Covering with the Automorphism Group H_{1}(P)

Let P be an n-dimensional triangulated closed manifold and S = (V, K) be its simplicial scheme. We will construct an abstract simplicial scheme Ŝ = (V̂ , K̂) as follows.

Set V̂ = V × G, where G = ℤ_{2}^{r}. Let v̂_{0}, v̂_{1}, …, v̂_{m} ∈ V̂, where v̂_{i} = (v_{i}, b_{i}) for all i = 0, 1, …, m. We will think that {v̂_{0}, v̂_{1}, …, v̂_{m}} ∈ K̂ if the below conditions are satisfied: (U1) {v_{0}, v_{1}, …, v_{m}} ∈ K; (U2) g_{0} + g_{i} = J([v_{0}v_{i}]) for any i = 1, …, m; here J([v_{0}v_{i}]) is the index

of the edge [v_{0}v_{i}].

Remark 4. When the conditions (U1) and (U2) are satisfied the equalities g_{i} + g_{j} = J([v_{i}v_{j}]) are also true for all i, j = 1, …, m. In fact, according to (U1), the cycle z = [v_{j}v_{i}] + [v_{i}v_{0}] + [v_{0}v_{j}] is homologous to zero. So J([v_{i}v_{j}]) = J([v_{i}v_{0}]) + J([v_{0}v_{j}]). By invoking (U2) we can have these equalities J([v_{i}v_{j}]) = g_{i} + g_{0} + g_{0} + g_{j} = g_{i} + g_{j}.

Let define now a mapping p^{0} : V̂ → V and a left action λ^{0} : G×V̂ → V̂ of group G on V̂, assuming

(1) p^{0}((v, g)) = v and λ^{0}(g′, (v, g)) = g′ · (v, g) = (v, g′ + g)

for all (v, g) ∈ V̂ and g′ ∈ G.

Let P̂ define some realization of the scheme Ŝ = (V̂ , K̂). At that we identify the set of vertices of the polyhedron P̂ with V̂.

Proposition 2. For the mapping p^{0} : V̂ → V there exists the unique continuation p : P̂ → P that is simplicial regular covering with a group of covering transformations G ≅ H_{1}(P).

Proof. Simplicial and surjective properties of the mapping p^{0} follow directly from its definition and from the construction of the complex K̂. If ŝ = {(v_{0}, g_{0}), (v_{1}, g_{1}), …, (v_{m}, g_{m})} ∈ K̂, then {v_{0}, v_{1}, …, v_{m}} ∈ K and g_{0} + g_{i} = J([v_{0}v_{i}]) for all i = 1, …, m. On the other hand, g · ŝ = {(v_{0}, g + g_{0}), (v_{1}, g + g_{1}), …, (v_{m}, g + g_{m})} for an arbitrary g ∈ G. Since g + g_{0} + g + g_{i} = g_{0} + g_{i} = J([v_{0}v_{i}]), then g · ŝ ∈ K̂. So the action λ^{0} is also simplicial.

Let s = {v_{0}, v_{1}, …, v_{m}} ∈ K and v̂_{0} ∈ (p^{0})^{−1}(v_{0}). Then v̂_{0} = (v_{0}, g_{0}), where g_{0} ∈ G. Set g_{i} = g_{0} +J([v_{0}v_{i}]) and v̂_{i} = (v_{i}, g_{i}) for all i = 1, …, m. At that ŝ = {v̂_{0}, v̂_{1}, …, v̂_{m}} ∈ K̂, v̂_{0} ∈ ŝ and p^{0}(ŝ) = s. Hence, the mapping p^{0} has the following property: (C1) for each abstract simplex s ∈ K and for any vertex v̂ ∈ (p^{0})^{−1}(s)

there is the unique abstract simplex ŝ ∈ K̂ containing the vertex v̂ and satisfying the equality p^{0}(ŝ) = s.

Let choose an abstract simplex ŝ = {v̂_{0}, v̂_{1}, …, v̂_{m}} ∈ K̂, and an element g of group G and assume that g · ŝ = ŝ. Then v̂_{i} = (v_{i}, g_{i}) and g · v̂_{i} = (v_{i}, g + g_{i}) for all i = 1, …, m. At the same time it follows from the equality g·ŝ = ŝ that (v_{0}, g+g_{0}) = (v_{k}, g_{k}) for some k ∈ {0, 1, …, m}. The latter is possible only if k = 0 and g = 0. Thus the action λ^{0} has the following property: (C2) if g · ŝ = ŝ for at least one non-empty simplex ŝ ∈ K̂, then g is

the neutral element of the group G. Let now consider the simplices ŝ = {(v_{0}, g_{0}), (v_{1}, g_{1}), …, (v_{m}, g_{m})} and

ŝ′ of the complex K̂.

First, if g ∈ G and ŝ′ = g·ŝ, then ŝ′ = {(v_{0}, g+g_{0}), (v_{1}, g+g_{1}), …, (v_{m}, g+ g_{m})}. At that p^{0}(ŝ′) = {v_{0}, v_{1}, …, v_{m}} = p^{0}(ŝ).

Further, assume that p^{0}(ŝ′) = p^{0}(ŝ) = {v_{0}, v_{1}, …, v_{m}}. Then according to (1), ŝ′ = {(v_{0}, g′_{0}), (v_{1}, g′_{1}), …, (v_{m}, g′_{m})}, where g′_{0}, g′_{1}, …, g′_{m} are some elements of group G, and g_{0} + g_{i} = J([v_{0}v_{i}]) = g′_{0} + g′_{i} for i = 1, …, m. Set g = g′_{0} + g_{0}. Then according to the above equalities g′_{i} = g + g_{i} for all i = 0, 1, …, m and hence ŝ′ = g · ŝ.

This proves that p^{0} and λ^{0} have the following property: (C3) for arbitrary abstract simplices ŝ, ŝ′ ∈ K̂ the equality p^{0}(ŝ) =

p^{0}(ŝ′) is equivalent to the existence of an element g ∈ G such that g · ŝ = ŝ′.

It is known that p^{0} and λ^{0} may have the unique continuation to the simplicial mapping p : P̂ → P and the simplicial action λ : G × P̂ → P̂ of group G on P̂. It also follows from (C1) – (C3) that p is a regular covering, and G is a corresponding group of covering transformations (see, for example, [4], chapter 2, section 6, theorem 7). □

Proposition 3. Let x = [v_{0}v_{1}] + [v_{1}v_{2}] + ⋯ + [v_{s−1}v_{s}] and y = [u_{0}u_{1}] + [u_{1}u_{2}] + ⋯ + [u_{t−1}u_{t}] be edge paths of the polyhedron P, that run from the vertex v_{0} = u_{0} to the vertex v_{s} = u_{t}, x̂ = [v̂_{0}v̂_{1}]+[v̂_{1}v̂_{2}]+⋯+[v̂_{s−1}v̂_{s}] and ŷ = [û_{0}û_{1}] + [û_{1}û_{2}] + ⋯ + [û_{t−1}û_{t}] paths of P̂, that cover the paths x and y respectively and have the same beginning v̂_{0} = û_{0}. Then v̂_{s} = û_{t} if and only if x ∼ y.

Proof. Let z = [w_{0}w_{1}]+[w_{1}w_{2}]+⋯+[w_{s−1}w_{s}] be a path in the polyhedron P and g_{0} ∈ G = ℤ_{2}^{r}. Then the unique path ẑ of the polyhedron P̂, starting in the vertex ŵ_{0} = (w_{0}, g_{0}) and covering the path z, is defined by the formulas

(2)  ŵ_{i} = (w_{i}, g_{0} + J(z_{i})) , i = 1, …, s,

where z_{i} = [w_{0}w_{1}] + [w_{1}w_{2}] + ⋯ + [w_{i−1}w_{i}], and

(3)  ẑ = [ŵ_{0}ŵ_{1}] + [ŵ_{1}ŵ_{2}] + ⋯ + [ŵ_{s−1}ŵ_{s}].

Set g_{i} = g_{0} + J(z_{i}) for i = 1, …, s and z_{0} = 0. Then J(z_{i}) = J(z_{i−1}) + J([w_{i−1}w_{i}]) for all i = 1, …, s. At the same time g_{i} = g_{i−1} + J([w_{i−1}w_{i}]) and the vertices ŵ_{i−1} and ŵ_{i} from V̂, defined by the formula (2), are connected by the edge [ŵ_{i−1}ŵ_{i}] ∈ K̂. Then in the polyhedron P̂ there is defined a path (3) starting at the vertex ŵ_{0} = (w_{0}, b_{0}). As p(ŵ_{i}) = p((w_{i}, g_{0} + J(z_{i}))) = w_{i} for all i = 0, 1, …, s, then ẑ covers the path z. Since p is a covering then the path ẑ is unique.

Assume now that v̂_{0} = (v_{0}, g_{0}), where g_{0} ∈ G. By the above proof, the equalities p(x̂) = x, p(ŷ) = y and v̂_{0} = û_{0} imply that v̂_{s} = (v_{s}, g_{0} + J(x)) and û_{t} = (u_{t}, g_{0} +J(y)). So v̂_{s} = û_{t} if and only if J(x) = J(y). According to proposition 1, the last equality is equivalent to the homology of the chains x and y. □

Remark 5. The definition of the simplicial scheme Ŝ = (V̂ , K̂) gives the algorithm for constructing the covering polyhedron P̂.

3. Minimal Cycles Searching

Let E(P) = K^{1}(P) be the set of edges of the polyhedron P, and L : E(P) → ℝ be a non-negative function. Using the formulas

(4)  L(0) = 0 and L({a_{1}, …, a_{s}}) = ∑_{i=1}^{s} L(a_{i}).

we can extend L to the function L : C_{1}(R) → (R). This function is often called weight function. And for an arbitrary chain x ∈ C_{1}(P) the value L(x) is called its weight (see, for example, [5], chapter 25).

Let define a weight function L̂ : C_{1}(P̂) → ℝ assuming that

(5)  L̂(x̂) = L(p(x̂))

for an arbitrary chain x̂ ∈ C_{1}(P̂).

ALGORITHM 2. Searching for the minimal path homologous to the given 1-chain.

Input:

1) list V (P) of vertices for polyhedron P;

2) lists U(v, P) of vertices incident to v for all vertices v ∈ V (P);

3) index vector-function J : C_{1}(P) → ℤ_{2}^{r} relative to some basis of group H_{n−1}(P);

4) weight function L : C_{1}(P) → ℝ;

5) vertices u_{1} ∈ V (P) and u_{2} ∈ V (P);

6) 1-chain x ∈ C_{1}(P), ∂x = {u_{1}, u_{2}}.

Output:

1-chain z ∈ C_{1}(P).

Algorithm Description.

Step 1. Determination of index of chain x. Calculate the vector i = J(x).

Step 2. Initializing chain z. Set z := ∅.

Step 3. Initializing sets T̂ ⊂ V (P) × G, P̂^{∗} ⊂ V (P) × G and a mapping D̂ : V (P) × G → ℝ. Let T̂ := {(u_{1}, 0)}, where 0 – null vector of space G = ℤ_{2}^{r}, P̂^{∗} := ∅ and D̂(u_{1}, 0) := 0.

Step 4. First extension of P̂^{∗} and D̂. For each vertex v ∈ U(u_{1}, P) set j := J([u_{1}v]) and add the pair (v, j) into the list P̂^{∗}. At the same time set D̂(v, j) := L([u_{1}v]), F (v, j) := (u_{1}, 0).

Step 5. Choosing a next element to add to T̂. Find the pair

(w, k) ∈ (P̂^{∗} \ T̂) such that D̂(w, k) = min_{(v,j)∈(P̂^{∗}\T̂)} D̂(v, j).

Step 6. Stop criterion of T̂, P̂^{∗}, D̂ construction. If w = u_{2} k = i, then go to step 10.

Step 7. Extension of the set T̂. Add the pair (w, k) into the list T̂.

Step 8. Next extension of P̂^{∗} and D̂. For each vertex v ∈ U(w, P) set j := k+J([wv]). If the pair (v, j) ∉ P̂^{∗}, then set D̂(v, j) := D̂(w, k)+ L([wv]), F (v, j) := (w, k) and add the pair (v, j) into P̂^{∗}. If (v, j) ∈ (P̂^{∗}\ T̂) and D̂(w, k)+L([wv]) < D̂(v, j), then set D̂(v, j) = D̂(w, k)+L([wv]) and F (v, j) := (w, k).

Step 9. Continuation of T̂, P̂^{∗}, D̂ construction. Go back to step 5.

Step 10. Construction of chain z.

Step 10.1. Take a pair (v, j) = F (w, k) and set z := z + [vw].

Step 10.2. If (v, j) ≠ (u_{1}, 0), then set (w, k) equal to (v, j) and go back to step 10.1.

End of algorithm.

Theorem 2. The chain z ∈ C_{1}(P) computed by algorithm 2 has the following properties:

• ∂z = {u_{1}, u_{2}};

• z ∼ x;

• L(z) ≤ L(y) for all chains y ∈ C_{1}(P) that satisfy conditions ∂y = {u_{1}, u_{2}} and y ∼ x.

Proof. By construction J(z) = i = J(x), so, according to statement 1, z ∼ x.

Let T^{∗} be the result set of Dijkstra’s algorithm for a one-dimensional skeleton P̂^{1} of the polyhedron P̂ if we choose the pair (u_{1}, 0) as the start point, and the pair (u_{2}, i) as the end point (see, for example, [6], chapter 6, section 6.3).

According to the definition of the complex K̂, the pairs v̂ = (v, j) and û_{1} = (u_{1}, 0) in step 4, as well as the pairs v̂ = (v, j) and ŵ = (w, k) in step 8 are connected by the edges [v̂û_{1}] ∈ E(P̂) and [v̂ŵ] ∈ E(P̂) respectively. Also, according to (5), we have the equalities L̂([v̂û_{1}]) = L([vu_{1}]) in step 4 and L̂([v̂ŵ]) = L([vw]) in step 8. This implies that the set T̂ constructed by step 10 is the same that T^{∗}.

Let note that step 10 is not limited to compute z = [v_{0}v_{1}]+⋯+[v_{q−1}v_{q}] starting at v_{0} = u_{1} and ending at v_{q} = u_{2}, but it also gives us the possibility to construct the vector sequence j_{0}, j_{1}, …, j_{q} ∈ ℤ_{2}^{r}, that will satisfy the equalities j_{0} = 0, j_{q} = i and j_{s} = j_{s−1} + J([v_{s−1}v_{s}]).

Set v̂_{s} = (v_{s}, j_{s}) for all s = 0, 1, …, q. Then [v̂_{s−1}v̂_{s}] ∈ E(P̂) for the same s and ẑ = [v̂_{0}v̂_{1}] + [v̂_{1}v̂_{2}] + ⋯ + [v̂_{q−1}v̂_{q}] is a path in the skeleton P̂^{1}, starting at (u_{1}, 0) and ending at (u_{2}, i). Since it can be computed by Dijkstra’s algorithm, L̂(ẑ) is not over than weight of any other path in P̂^{1}, running from (u_{1}, 0) to (u_{2}, i).

By the construction of the path ẑ and according to (5), L(z) = L̂(ẑ). Now, in the polyhedron P, let consider another path z′ connecting the vertices u_{1}, u_{2} and homologous to x. Since p : P̂ → P is a covering, there exists the unique path ẑ′ in P̂, that covers z′ and starts at the vertex (u_{1}, 0). At the same time, by statement 3 the end points of these paths ẑ and ẑ′ coincide. But then according to the above proof, L(z) = L̂(ẑ) ≤ L̂(ẑ′) = L(z′). □

Remark 6. If u_{1} = u_{2}, then algorithm 2 constructs containing u_{1} cycle z ∈ Z_{1}(P) homologous to the cycle x and having minimal weight L(z) in set of all cycles with the same properties.

ALGORITHM 3. Searching for the minimal cycle from fixed gomology class.

Input:

1) list V (P) of vertices for polyhedron P;

2) lists U(v, P) of vertices incident to v for all vertices v ∈ V (P);

3) simple basis cycles z_{1}^{n−1}, z_{2}^{n−1}, …, z_{r}^{n−1} of homology group H_{n−1}(P);

4) lists V (z_{1}^{n−1}), …, V (z_{r}^{n−1}) of vertices from cycles z_{1}^{n−1}, …, z_{r}^{n−1} respectively;

5) index vector-function J : C_{1}(P) → ℤ_{2}^{r} relative to basis [z_{1}^{n−1}], …, [z_{r}^{n−1}] of H_{n−1}(P);

6) weight function L : C_{1}(P) → ℝ;

7) cycle x ∈ Z_{1}(P).

Output:

1-cycle z ∈ Z_{1}(P).

Algorithm Description.

Step 1. Set Z := ∅. Step 2. Determine the vector i = J(x). Step 3. If i = 0, then set z = 0 and go to step 7. Step 4. Find a number k ∈ {1, …, r} such that coordinate i^{k} of the

vector i is equal 1.

Step 5. For each vertex v ∈ V (z_{k}^{n−1}) execute steps 5.1 – 5.3. Step 5.1. Using algorithm 2 we find containing v cycle z_{v} ∈ Z_{1}(P)

homologous to the cycle x and having minimal weight L(z_{v}) in set of all cycles with the same properties.

Step 5.2. Add the cycle z_{v} into the list Z. Step 5.3. Take the next vertex v ∈ V (z_{k}^{n−1}). Step 6. Choose the cycle z ∈ Z such that L(z) = min_{z′∈Z} L(z′). Step 7. Quit.

End of algorithm.

Theorem 3. Let z be the the cycle found by the algorithm 3. Then

• z ∼ x;

• L(z) = min_{y∈[x]} L(y).

Proof. First, if i = 0, then according to proposition 1, cycle x is homologous to zero. At the same time we assume in step 3 that z = 0. According to (4), L(0) = 0. Thus, in this case z ∼ x and L(z) = min_{y∈[x]} L(y).

Further, let i ≠ 0. Then according to step 4 i^{k} = 1 for k ∈ {1, …, r}. Let now consider an arbitrary element z_{v} in the list Z. It is chosen

in step 5.1, and according to this step z_{v} ∼ x. Since z = z_{v} for some v ∈ V (z_{s}^{n−1}) then z ∼ x too.

Let assume that some one-dimensional cycle y of the polyhedron P belongs to the class [x]. Then J(y) = J(x) = i. Hence, Ind([y], [z_{k}^{n−1}]) = J^{k}(y) = 1, and therefore the cycles y and z_{k}^{n−1} have at least one common vertex u ∈ V (z_{k}^{n−1}). In this case, according to the selection of cycle z_{u} in step 5.1 of algorithm 3, L(z_{u}) ≤ L(y)). This implies according to step 6, that L(z) ≤ L(z_{u}) ≤ L(y). □

For all algorithms we created program realization of C++ classes. Then we found cycles of minimal length on several computer models of closed 2-dimensional manifolds.

References

1. H. Seifert, W. Threlfall, Lenrbuch der Topologie, Teubner, Leipzig, 1934.

2. G. Vegter, C. K. Yap, Computational Complexity of Combinatorial Surfaces, Proc. 6th ACM Symp. on Computational Geometry, Berkeley, CA, 1990, pp. 102 – 111.

3. E. I. Yakovlev, P. A. Gordienko, Fast algorihtms for computing of homology groups and their bases, Proc. VII International Seminar ”Discrete Mathematics and its Applications”, MSU, Moscow, 2001, pp. 284 – 287 (Rus).

4. E. Spanier, Algebraic Topology, McGraw-Hill, New York, 1966.

5. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, The MIT Press/McGraw-Hill, 1990.

6. A. V. Aho, J. E. Hopcroft, J. D. Ulman, Data Structure and Algorithms, Addison-Wesley, Boston, 1983.

Nizhni Novgorod State University, Gagarina pr., 23, Nizhny Novgorod: 603950, Russia E-mail address: a.lapteva@ntek.nnov.ru E-mail address: yei@uic.nnov.ru

Received May 18, 2006