UDC 389.001

ON THE RATIONAL DESIGN OF METROLOGICAL LABORATORIES

PART I

E. I. Tsimbalist

(Presented by the scientific seminar of the Department of Radio Engineering)

A system of metrological support is represented in the form of a König graph. Algorithms are developed for identifying connected components, articulation points, and blocks of the graph. The algorithms are illustrated by examples.

4 illustrations, 2 references.

The choice of the structure of metrological support (MS) in the verification of working measuring instruments and the staffing, on this basis, of metrological laboratories is a complex problem; its solution requires taking into account a number of interrelated factors.

We shall consider the totality of working measuring instruments in an MS that are subject to verification, and the reference measures and measuring instruments that form verification schemes for measuring the \(i\)-th (electrical) parameter, as a certain complex system based on a functional-target approach. As a rule, in order to minimize the objective function in synthesizing an optimal MS, a large amount of a priori information is needed that quantitatively describes the connections in the system. The absence of such information in full* forces designers to use particular criteria of the quality of system functioning, leading to the adoption of quasi-optimal (rational) decisions that use, along with others, expert assessments.

Let us consider the problem of partitioning an MS into a finite number of metrological laboratories; its solution is illustrated by examples of the adoption of rational decisions for various types of objective function.

Representation of an MS by a König graph. Suppose there is a finite set of working measuring instruments (WMI)
\(X' = \{x_1, x_2, \ldots, x_n\}\), entering verification (Fig. 1). Each \(x \in X'\) is characterized by a number of (electrical) parameters, monitored in the verification process, which form sets of verified parameters
\(A = \{\alpha, \beta \ldots \varepsilon\}\),
\(B = \{\alpha_1, \alpha_2 \ldots \alpha_n; \beta_1, \beta_2 \ldots \beta_m; \ldots \varepsilon_1, \varepsilon_2 \ldots \varepsilon_k\}\),

where
\(\alpha = \alpha_1 \cup \alpha_2 \ldots \cup \alpha_n;\quad \alpha_1 \cap \alpha_2 \ldots \cap \alpha_n = \varnothing\), etc. To determine the elements of the set
\(X'' = \{y_1, y_2, \ldots, y_m\}\)
of reference measuring instruments (RMI), we shall analyze the normative-technical documentation

* In practically all normative-technical documentation of the State system of measurements, data on the verification time of a single measuring instrument (a single parameter of a measuring instrument), the productivity and cost of reference means and measuring instruments, etc., are absent or only implicitly expressed.

of the State measurement system, including the verification schemes given in the recommendations on standardization of the CMEA.

Considering the elements of the sets \(X'\) and \(X''\) as the first aggregate of objects, and the interrelations between the elements of \(X'\) and \(X''\) as the second aggregate of objects, defined by a certain incidence relation, we construct a König graph \(L(X,U)\) (Fig. 2) for which, as is known [1],

Fig. 1

\[ \forall x,\ y \in X\,[\,\overline{xy}\in U \to (x\in X' \,\&\, y\in X'') \vee (x\in X'' \,\&\, y\in X')\,], \tag{1} \]

\[ X = X' \cup X''. \]

Thus, an MSO can be reduced to a König graph, which, in our view, is the most natural representation of the links between reference and working measuring instruments. Owing to the fact that in \(X'\) (or \(X''\)) the elements are not adjacent to one another, the problem of partitioning an MSO into a finite number of metrological laboratories is a variant of the well-known assignment problem and reduces to partitioning \(L(X,U)\) by duplicating certain reference measuring instruments while preserving all edges of the original graph.

Boundary cases of partitioning. Let the initial graph (1), isomorphic to a certain MMS, have \(n(L)=n_{0}(L)+n_{p}(L)\) vertices, \(m(L)\) edges, and \(\chi(L)\) connected components, where \(n_{0}(L)\) and \(n_{p}(L)\) are, respectively, the numbers of standard measuring instruments (SMI) and working measuring instruments (WMI). Let us estimate the minimum and maximum number of standard instruments \(n_{0}^{\Sigma}\) required for partitioning the system into \(k\) parts.

Fig. 2

The minimum number of SMI is equal to \(n_{0}(L)\), if the graph is partitioned according to its connected components, with \(\chi(L)\geq k\), that is

\[ (n_{0}^{\Sigma})_{\min}=\sum_{i=1}^{k}(n_{0})_{i}=n_{0}(L). \tag{2} \]

When (2) is satisfied—which in the general case is unlikely—the input flow of WMI will be divided into \(k\) unequal parts; within each of the \(k\) laboratories either a sequential or a parallel-sequential verification method can be provided.

The maximum number of SMI preserving the initial connectedness of the graph is equal to \(m(L)\), i.e.,

\[ (n_{0}^{\Sigma})_{\max}=\sum_{i=1}^{k}(n_{0})_{i}=m(L). \tag{3} \]

Having implemented (3), we obtain a new graph \(L_{1}=(X_{1},U)\), in which the cardinality of \(X_{1}\) has increased by \(m(L)-n_{0}(L)\) standard instruments; in this case it is possible to organize \(k\) laboratories \([k\leq \chi(L_{1})]\), in which a parallel verification method will be provided. Thus, the actual number of SMI lies within the limits

\[ n_{0}(L)\leq n_{0}^{\Sigma}\leq m(L) \]

and depends on the structure (1) and on the adopted verification method, while the first step in partitioning an MMS into laboratories is the determination of the connected components and the identification of the set of vertices generating these components.

Algorithm for identifying connected components. The search for \(\chi(L)\) and for the sets of vertices corresponding to them can be carried out by known methods, for example, using the procedure of raising

adjacency matrix of the graph to the degree required to obtain the “established matrix,” or by applying a vertex-labeling algorithm. Described below is an algorithm based on the use of the set-theoretic method of analysis and suitable both for manual calculations and for a digital computer [2].

In the initial graph (1), vertices of degree \(S=1\) are removed and recorded (the index of the removed vertex is assigned to the adjacent one). For the remaining vertices, from the graph or from its adjacency matrix, the table \(\beta(j/l_j)\) is compiled:

\[ \begin{aligned} 1&\underline{\hspace{1.8cm}}\,l_1\\ 2&\underline{\hspace{1.8cm}}\,l_2\\ &\ldots\\ j&\underline{\hspace{1.8cm}}\,l_j\\ &\ldots\\ n&\underline{\hspace{1.8cm}}\,l_n, \end{aligned} \]

where \(l_j\) is the set of indices of the vertices incident with the \(j\)-th one; \(n=n(L)\). We find \(p\)-step paths \((p=1,2,\ldots,n-1)\) from any chosen \(j\)-th vertex, performing the vector product with symbols over the field modulo 2. After each subsequent step of the algorithm, the sets of indices of vertices adjacent to the initial vertex through paths of length \(1,2,\ldots,n-1\) are combined. If \(p\le n-1\) and the set formed is equal to the initial one, then the algorithm terminates and \(\chi(L)=1\). Otherwise, part of the vertices of the graph is unreachable from the chosen \(j\)-th one, and \(\chi(L)>1\). From the remaining vertices any one is again chosen, and the algorithm is repeated, terminating when the sets \(C_i\) and \(C_{i+1}\), obtained at the \(i\)-th and \(i+1\)-st steps, are identical.

Example 1. Find \(\chi(L)\) and the sets of vertices of the graph generating each component (Fig. 3).

Fig. 3

1. We compile \(\beta(j/l_j)\):

\[ \begin{array}{ll} 1\text{—}48 & 2\text{—}37\\ 3\text{—}260 & 4\text{—}159\\ 5\text{—}48 & 6\text{—}37\\ 7\text{—}260 & 8\text{—}159\\ 9\text{—}48 & 10\text{—}37 \end{array} \]

1. Let \(j=1\); then in \((4')\) we have one-step paths 14 and 18, and

\[ C_1=\{1,4,8\}. \]

1. We find two-step paths

\[ \left[\,1\ \frac{1}{159}\,\right]_2=145;\ 149;\qquad \left[\,1\ \frac{8}{159}\,\right]_2= \]

\[ =185;\ 189;\qquad C_2=\{1,4,5,8,9\}. \]

1. For \(p=3\) we have

\[ \left[\,14\ \frac{5}{48}\,\right]_2=1458;\ \ldots\qquad \left[\,18\ \frac{9}{48}\,\right]_2=1894. \]

In this case \(C_3 = C_2 = \{1, 4, 5, 8, 9\}\) and \(\chi(L) > 1\), with \(\chi_1(L)\) formed by vertices 1, 4, 5, 8, 9. Performing analogous operations, we find that \(\chi_2(L)\) includes vertices 2, 3, 6, 7, 0 (Fig. 3b). In conclusion, we note that for simple graphs the final information can be traced directly from (4′).

Determination of articulation points and blocks of a graph. If, after finding \(\chi(L)\), it turns out that the number of connected components is less than \(k\), then, in order to increase it, it is necessary to modify (1) by duplicating certain vertices corresponding to the MSI. In graph theory this problem is solved by finding the articulation points and blocks of a graph [1].

Fig. 4

Let us find among \(\chi(L)\) the connected component(s) with the greatest cardinality of the set of vertices generating it. Remove, one at a time, the elements \(y_i\) of the MSI set that are included in the component under study, and apply to the newly obtained subgraph the algorithm for detecting connected components. Upon completion of this procedure, the articulation points of the component under study will be determined, i.e., its vertices whose removal (one at a time) leads to an increase in the number of connected components*. Having determined the articulation points, one can determine the blocks of the graph, i.e., the maximal connected subgraphs that do not have their own articulation points.

Example 2. Determine the blocks of the largest connected component of the graph (Fig. 2). Upon successive removal of one vertex at a time, \(y_1 = C\), \(y_2 = Д \ldots\), \(y_7 = M\), and application of the algorithm for detecting \(\chi(L)\), we have:

1) \(\chi(L_C) > \chi_2(L)\) for \(L_C: \{3D(4)\}, \{5, 6, 7, 8, 9, 0, E, F, G, K, M\};\)

2) \(\chi(L_{D(4)}) = \chi_2(L);\)

3) \(\chi(L_E) > \chi_2(L)\) for \(L_E: \{3, 5, C, D(4)\}, \{6, 7, 8, 9, 0, F, G, K, M\};\)

4) \(\chi(L_F) > \chi_2(L)\) for \(L_F: \{3, 5, 6, C, D(4), E\}, \{7, 8, 9, 0, G, K, M\};\)

5) \(\chi(L_G) = \chi_2(L);\)

6) \(\chi(L_K) > \chi_2(L)\) for \(L_K: \{3, 5, 6, 7, 8, C, D(4), E, F, G\}, \{9, 0, M\};\)

7) \(\chi(L_M) = \chi_2(L)\)**.

Duplicating the articulation points \(C, E, F, K\), we obtain, together with \(\chi_1(L)\), six blocks (Fig. 4):

1) \(\{1, 2, A, B\}\), 2) \(\{3CD(4)\}\), 3) \(\{5, C, E\}\), 4) \(\{6, E, F\}\), 5) \(\{7, 8, F, G, K\}\), 6) \(\{9, 0, K, M\}\).

Thus, in the graph under consideration, six blocks are formed, obtained by increasing \(n_0(L)\) by 4 reference measuring instruments. If \(k \leqslant 6\), then, depending on the form of the objective function, a rational synthesis of the laboratory composition can be ensured on the basis of the initial blocks.

REFERENCES

1. A. A. Zykov. Theory of Finite Graphs. Novosibirsk, “Nauka,” 1969.

2. E. I. Tsimbalist, L. A. Naumov. Algorithms for the analysis of systems represented by a signal graph. Izvestiya Vuzov SSSR, “Radioelektronika,” 1973, No. 6.

* If there are no articulation points in the graph under study, double articulation points are found, etc.

** Let us recall that, in forming the blocks, the restriction was used that only vertices from the set \(X\) may be removed.