SU1683034A1 - Graph parameters analyzers - Google Patents

Abstract

The invention relates to computing and can be used to analyze the reliability of systems described by graphs. The aim of the invention is to expand the functionality of the device by analyzing the connectivity of the graph at the zero level of binary relations. The device contains a block 1 setting the adjacency matrix, registers 2,3, blocks 4.5 comparing groups, block 6 determining halfsteps of the run, block 7 determining halfsteps of the outcome, clock inputs 8 and 9 of the device, input 10 setting the allowable half degrees of entering the device, input 11 setting permissible semi-degrees of the device’s output, output 12 of the sign of connectivity of the graph at the zero level of binary relations. Before starting the work, the information about the topology of the graph is entered into the block 1 of the assignment matrix, and the permissible values of the local degrees of the graph are specified at the inputs 10.11. The inputs of the 8.9 sequentially served pulses of the level of logical units. At the same time, at the output 12 of the device, a sign of the connectivity of the graph is formed at the zero level of the binary relations. 3 il. & J

Description

t ± t

FIG I

About 00 WITH

about

with

J

The invention relates to computing and can be used to analyze the reliability of systems described by graphs.

The aim of the invention is to expand the functionality of the device by analyzing the graph at the zero level of binary relations.

FIG. 1 shows a functional diagram of the device; Fig. 2 is a functional block diagram of determining the degree of outcome; FIG. 3 is a functional diagram of the approach half-degree unit.

The device (Fig. 1) contains a block 1 specifying the adjacency matrix, registers 2 and 3, blocks 4 and 5 of group comparison, block 6 for determining half-degrees of entry, block 7 for determining half-degrees of outcome, the first 8 and second 9 clock inputs of the device, input 10 for setting valid half-degrees of approach of the device, input 11 specifying permissible semi-degrees of the device’s output, output 12 of the graph sign of connectivity at the zero level of binary relations.

Figure 2 denotes a group of B adders 13, where B is the number of vertices in the graph, inputs of 14 signs of the presence of arcs and outputs 15 semi-degrees of the outcome of the peaks, and the input 14 of the sign of the presence of (K, M) -th arc is connected to the input of K the term of the Mth summator of the group (K 1B; M 1B), the output

which is the output of 15 half-degrees of the outcome of the M-th vertex of the block 7 determining the half-degrees of the outcome.

In FIG. 3, a group of B adders 16 is designated, and the input 17 of the presence signs (K, M) of the arc of block 6 is connected to the input of the M-th term of the K-th adder 16 of the group, the output of which is output 18 of the half-degree approach K- th tops of block 6.

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. In this case, blocks 6 and 7 define local degrees of all its vertices. The inputs 10 and 11 define the permissible values of the local degrees of the graph. In this case, the comparison units 4 and 5, corresponding to the vertices of the graph, whose local degrees are not less than specified admissible values, form logic level 1 signals at their outputs. After a time sufficient to terminate these processes, a logic level 1 signal is sent to the device input 8. In this case, the numbers of the vertices, whose local degrees correspond to the specified requirements, are entered into registers 2 and 3. After a time sufficient for the termination of the recording procedures, the device input signal 9 is supplied with a pulse level signal 1. At the same time, the block 1 specifying the adjacency matrix removes arcs outgoing and entering into

vertices whose numbers are fixed in registers 2 and 3. If the removal results in a null graph (i.e., a graph consisting of one isolated vertices), a level signal appears at the output 11 of the device

logical 1, as a sign of graph connectivity at the zero level of binary relations.

Claims (1)

Claims device for analyzing parameters a graph containing a block specifying the adjacency matrix and two registers, characterized in that, in order to expand the functional relations of the device by analyzing the connectivity of the graph on zero level of binary relations, two groups of B units of comparison are entered into it, where B is the number of vertices in the graph, the unit for determining the degree of approach and the unit for determining the degree of outcome, and the output the sign of the presence of (K, M} -th arc of the block setting the adjacency matrix (, ..., E) connected to the same inputs of the unit for determining the semi-degrees of the outcome and the unit for determining the semi-degrees of approach, the output half-degree of approach of the K-th vertex of which is connected to the first information input of the K-th comparison unit of the first group, the output of the attribute Not less than which is connected to the K-th section of the information the input of the first register, the K-th bit of the information output of which is connected to the input of the attribute of deletion of arcs emanating from the K-th node of the block of setting the adjacency matrix, the output of the sign of the presence of the topology the null graph of which is the output of the graph connectivity attribute at the zero level of the binary relations of the device, the input of setting the permissible half-degree of entry of which is connected to the second information inputs of all comparison blocks of the first group, the output of the half-degree outcome of the M-th peak of the block determining the half-degrees of the output connected to the first information the input of the M-th block comparison the second group, the sign output is NOT less connected to the M-th bit of the information input of the second register, the M-th bit of the information output of which is connected to the input of the delete sign arcs that go into the M-vertex of the block of setting the adjacency matrix, the input of specifying the permissible semi-degree of the device’s output is connected to the second information inputs of all the comparison blocks of the second group, the first clock input of the device is connected To the inputs of the attributes of the record, and the second reading characters of the first and second register-clock input of the device to the inputs of the receiver. # 75, tS2 Pl P Pi pgv And M 7 You, $ 189 " FIG. 2 17 Aug M 1Vg fa J % Fig.Z