卷 307, 编号 Suppl 1 (2019)

We consider the ill-posed problem of localizing (finding the position of) the discontinuity lines of a function of two variables that is smooth outside the discontinuity lines and has a discontinuity of the first kind at each point of such lines. A uniform square grid with step τ is considered, and it is assumed that the mean values of a perturbed function over squares with side τ are known at each node of the grid. The perturbed function approximates the exact function in the space L₂(ℝ²). The perturbation level δ is known. To solve the problem under consideration, we design and study global discrete algorithms that are based on averaging procedures and approximate the discontinuity lines by a set of points of a uniform grid. The main result of the paper is the development of an approach to the global study of localization algorithms. We formulate conditions for the exact function, thus defining a class of correctness. Within this class, we perform a theoretical study of the proposed algorithms, introduce the characteristics to be estimated (the concept of approximating a set of discontinuity lines by a set of points of a uniform grid), and develop methods for deriving the estimates. To achieve this goal, we use a simplified statement: the discontinuity lines are straight line segments, and the proposed localization algorithm has the simplest thinning block. It is established that the localization error of the algorithm has order O(δ). Estimates of other important parameters characterizing the localization algorithm are given.

A Shilla graph is a distance-regular graph Γ of diameter 3 whose second eigenvalue is a = a₃. A Shilla graph has intersection array {ab, (a + 1)(b − 1), b₂; 1, c₂, a(b − 1)}. J. Koolen and J. Park showed that, for a given number b, there exist only finitely many Shilla graphs. They also found all possible admissible intersection arrays of Shilla graphs for b ∈ {2, 3}. Earlier the author together with A. A. Makhnev studied Shilla graphs with b₂ = c₂. In the present paper, Shilla graphs with b₂ = sc₂, where s is an integer greater than 1, are studied. For Shilla graphs satisfying this condition and such that their second nonprincipal eigenvalue is −1, five infinite series of admissible intersection arrays are found. It is shown that, in the case of Shilla graphs without triangles in which b₂ = sc₂ and b < 170, only six admissible intersection arrays are possible. For a Q-polynomial Shilla graph with b₂ = sc₂, admissible intersection arrays are found in the cases b = 4 and 5, and this result is used to obtain a list of admissible intersection arrays of Shilla graphs for b ∈ {4, 5} in the general case.

The capacitated vehicle routing problem with time windows (CVRPTW) is a well-known NP-hard combinatorial optimization problem. We present a further development of the approach first proposed by M. Haimovich and A. H. G. Rinnooy Kan and propose an algorithm that, for an arbitrary ε > 0, finds a (1 + ε)-approximate solution for the Euclidean CVRPTW in \(\text{TIME}\;(\text{TSP},\;\rho ,n)\; + \;O({n^2}) + O({e^{(q{{(\tfrac{q}{ \in })}^3}{{(p\rho )}^2}\log (p\rho ))}})\), where q is an upper bound for the capacities of the vehicles, p is the number of time windows, and TIME(TSP, ρ, n) is the complexity of finding a ρ-approximation solution of an auxiliary instance of the Euclidean TSP. Thus, the algorithm is a polynomial-time approximation scheme for the CVRPTW with p³q⁴ = O(log n) and an efficient polynomial-time approximation scheme for arbitrary fixed values of p and q.

For a distance-regular graph Γ of diameter 3, the graph Γ_i can be strongly regular for i = 2 or 3. Finding the parameters of Γ_i from the intersection array of Γ is a direct problem, and finding the intersection array of Γ from the parameters of Γ_i is the inverse problem. The direct and inverse problems were solved earlier by A. A. Makhnev and M. S. Nirova for i = 3. In the present paper, we solve the inverse problem for i = 2: given the parameters of a strongly regular graph Γ₂, we find the intersection array of a distance-regular graph Γ of diameter 3. It is proved that Γ₂ is not a graph in the half case. We also refine Nirova’s results on distance-regular graphs Γ of diameter 3 for which Γ₂ and Γ₃ are strongly regular. New infinite series of admissible intersection arrays are found: {r² + 3r +1, r(r +1), r + 2; 1, r + 1, r(r + 2)} for odd r divisible by 3 and {2r² + 5r + 2, r(2r + 2), 2r + 3; 1, 2r + 2, r(2r + 3)} for r indivisible by 3 and not congruent to ±1 modulo 5.

A system of equations for the motion of an ionized ideal gas is considered. An algorithm for the reduction of this system of nonlinear partial differential equations (PDEs) to systems of ordinary differential equations (ODEs) is presented. It is shown that the independent variable ψ in the systems of ODEs is determined from the relation ψ = t + xf₁(ψ) + yf₂(ψ) + zf₃(ψ) after choosing (setting or finding) the functions f_i(ψ), i = 1, 2, 3. These functions are either found from the conditions of the problem posed for the original system of PDEs or are given arbitrarily to obtain a specific system of ODEs. For the problem on the motion of an ionized gas near a body, we write a system of ODEs and discuss the issue of instability, which is observed in a number of cases. We also consider a problem of the motion of flows (particles) in a given direction, which is of significant interest in some areas of physics. We find the functions f_i(ψ), i = 1, 2, 3, that provide the motion of a flow of the ionized gas in a given direction and reduce the system of PDEs to a system of ODEs.

A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case where the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.

A linear control problem is considered in the presence of an uncontrolled disturbance. It is only known that the values of the disturbance belong to a given connected compact set. The terminal time of the control process is fixed. The terminal component of the payoff depends on the modulus of a linear function of the phase variables, and the integral component is given by an integral of a power of the control. We admit the possibility of one breakdown leading to a change in the dynamics of the control process. The time of the breakdown is not known in advance. The construction of the control is based on the principle of minimization of the guaranteed result. The opponents are the disturbance and the time of the breakdown. Necessary and sufficient conditions for the optimality of an admissible control are found.

Suppose that G is a finite group, π(G) is the set of prime divisors of its order, and ω(G) is the set of orders of its elements. A graph with the following adjacency relation is defined on π(G): different vertices r and s from π(G) are adjacent if and only if rs ∈ ω(G). This graph is called the Gruenberg—Kegel graph or the prime graph of G and is denoted by GK(G). In A. V. Vasil’ev’s Question 16.26 from the “Kourovka Notebook,” it is required to describe all pairs of nonisomorphic simple nonabelian groups with identical Gruenberg—Kegel graphs. M. Hagie and M. A. Zvezdina gave such a description in the case where one of the groups coincides with a sporadic group and an alternating group, respectively. The author solved this question for finite simple groups of Lie type over fields of the same characteristic. In the present paper, we prove the following theorem.

Theorem. Let\(G = A_{n - 1}^ \pm \left( q \right)\), where n ∈{3, 4, 5, 6}, and let G₁be a finite simple group of Lie type over a field of order q₁nonisomorphic to G, where q = p^f, \({q_1} = p_1^{{f_1}}\), and p and p₁are different primes. If the graphs GK(G) and GK(G₁) coincide, then one of the following statements holds

(1) {G, G₁} = {A₁(7), A₁(8)}

(2) {G, G₁} = {A₃(3), ²F₄(2)′}

(3) {G, G₁} = {²A₃(3), A₁(49)}

(4) {G, G₁} = {A₂(q), ³D₄(q₁)}, where (q − 1)₃ ≠ 3, q + 1 ≠ 2^k, and q₁ > 2

(5) \(\left\{G, G_{1}\right\}=\left\{A_{4}^{\varepsilon}(q), A_{4}^{\varepsilon_{1}}\left(q_{1}\right)\right\}\), where qq₁is odd

(6) \(\left\{ {G,{G_1}} \right\} = \left\{ {A_4^\varepsilon (q){,^3}{D_4}\left( {{q_1}} \right)} \right\}\), where (q − ϵ1)₅ ≠ 5 and q₁ > 2

(7) \({A_4^\varepsilon (q)}\) and G₁ ∈ {B₃(q₁), C₃(q₁), D₄(q₁)}.