SU1658172A1 - Graph problem solver - Google Patents

Abstract

The invention relates to computing and can be used to analyze the connectivity of an upper graph. The aim of the invention is to expand the functionality of the device by checking the presence of cycles in the graph. The device contains a block 1 for setting the adjacency matrix, a block 2 for determining semi-degrees of approach, a block 3 for comparison, an input 4 for polling the device and an output 5 for the absence of device cycles with the corresponding connections. 4 il.

Description

The invention relates to computing and can be used to analyze the connectivity of an upper graph.

The aim of the invention is to expand the functionality of the device by checking the presence of cycles in the graph.

FIG. 1 shows a functional diagram of the device; in fig. 2 is a functional diagram of an embodiment of the device; in fig. 3 is a functional block diagram of the approach degree determination; in fig. 4 is a functional block diagram of the removal of outgoing arcs.

The device contains a block 1 specifying the adjacency matrix, a block 2 determining half-degrees of approach, a block 3 of comparison, an input 4 of the interrogation and an output 5 of the sign of the absence of cycles.

The device works as follows.

Before starting work, information on the topology of the graph is entered in block 1 of the assignment of the adjacency matrix.

At the input 4 of the survey device serves the potential level of logical units. In this case, unit 2 outputs the potentials of a logic unit to those outputs, the half-degrees of entry of the corresponding vertices of which are zero (i.e., the potentials of the logic unit level appear on those outputs of block 2, whose numbers are equal to the numbers of the vertices one arc). In this case, block 1 removes selected rows from the graph adjacency matrix (thereby, arcs from all vertices with zero are removed from the topology of the graph).

degree of entry). In this case, the topology of the graph is changed, block 2 selects new vertices with zero approach degree, and so on, until all arcs are completely removed. not included in the cycles of the graph. After a time sufficient to terminate the indicated processes.

ABOUT

about

(X

V n

If there are no cycles in the graph at all outputs of block 2, the potential levels of the logical unit are in cc. At that, the comparison unit 3 will form at its output a potential level potential of the logical unit (a sign of the absence of cycles). If there are cycles in the graph at one or several outputs of block 2, the potentials of the logic zero level are saved, and at the output of the comparison block 3 (it can be made as an element I) the potential of logic zero remains (a sign of the presence of cycles in the graph)

FIG. 2 shows an embodiment of the device, which is characterized in that, in order to preserve the original topology of the graph, a block for removing outgoing arcs is entered into it, with the output of the (K, M) th element of block 1 of the adjacency matrix setting 1 (K, M) -th arc of the outgoing arc removal unit (K 1 V, M 1 V, where B is the number of vertices in the graph), whose output of the same name is connected to the input of the same name of block 2 for determining half-degrees, approach, sign of equality of zero the extent of the approach of the K-th peak is connected to the K-info The memory input of block 3 is compared to the arc removal input emanating from the K-th vertex of block 6.

Unit 2 for determining the half-degrees of entry contains a group of B elements OR — NOT 7 and a group of B elements — AND 8, and input 9 is a sign of presence (K.My arc is connected to the M th input of the Kth element OR — NOT 7, the output of which is connected to the first input of the K-th element And 8, the output of which is the output 10 of the sign of equality

the zero degree of the K-th vertex of block 2, the input 11 of the poll of which is connected to the second inputs of all elements AND groups,

The outgoing arc removal unit 6 contains a matrix of IxB keys 12, and the input 13 of the presence sign (K, M) -1 of the arc of block 6 is connected to the information input of the Mth key 12 of the Kth row of the matrix, the information output of which is the same output 14 of block 6, the input 15 for removing arcs from the kth vertex of which is connected to the disconnecting inputs of all keys of the 12th row of the matrix.

The invention is a device for solving problems on graphs containing a block for setting an adjacency matrix and a block for determining half-degrees of approach, and the output value (KM) of the element of the block for specifying an adjacency matrix (K is 1B, M is 1B, where B is the number of vertices in the graph ) connected to the input of the presence sign (K, M) of the arc of the step-step detection unit, characterized in that, in order to expand the functionality of the device by checking the presence of cycles in the graph, a comparison block was entered into it, and the device's polling input is connected to in do the polling of the stepback degree determination unit, the output of the sign of equality of the half degree of entry of the Kth peak of which is connected to the delete input of the Kth row of the block of the adjacency matrix and the Kth information input of the comparison block, the sign of the absence of zero information of which is the output of the sign no device cycles.

1

one

2

I

П 18% 2В

Fig.Z

but

. . P0

% /

// g

Claims (1)

15 claims A device for solving problems on graphs containing a block for specifying an adjacency matrix and a block for determining the semi-degrees of approach, and the output of the value (K, M) of the element of a block for specifying an adjacency matrix (K = 1 ..... B, M = 1 ... ..B, where B is the number of vertices in the graph) is connected to the input of the sign of the presence (K, M) of the arc of the block for determining the semi-degrees of approach, characterized in that, in order to expand the functionality of the device by checking for cycles in the graph, a comparison block has been introduced, and the polling input of the device is connected to the polling input of the block EFINITIONS indegree, sign equality output zero indegree K-th vertex of which is connected to the input of removing K-th row of the matrix setting unit adjacency to K-th data input of the comparator, the output characteristic of absence of zero information which is the output characteristic lack of device cycles. Figure 1