The graph consists of vertices and edges. The vertices are connected by edges according to a certain property - the incidence relation, which defines the set of edges. In this case, loops and isolated vertices can form.
Instructions
Step 1
Let a set of graph edges be given and a relation along which an edge can be drawn from one vertex to another is given. As an example, the set of vertices {1, 2, 3, 4, 5, 6, 7, 8}, two vertices x and y are in the ratio x + y <8.
Step 2
Build a vertex adjacency matrix. To do this, build a square table, the number of rows and columns in the table coincides with the number of vertices. Then put 1 at the intersection of the i-th row and j-th column if the vertices i and j satisfy the given ratio. Put 0 at the intersection of the i-th row and j-th column if the ratio for the corresponding elements is not satisfied.
In our example, the first line is filled in as follows:
1 + 1 <8, so there is 1 at the intersection of the 1st row and 1st column
1 + 2 <8, again 1
1 + 3 <8, again 1
1 + 7 <8, incorrect inequality, so this element of the table will be 0
1 + 8 <8, again 0
Step 3
To find out the number of edges, count the number of ones in the adjacency matrix without duplicating the edges.
In the example, a symmetric matrix was obtained, so we counted first the ones above the main diagonal of the matrix (marked in blue), and then the ones on the main diagonal (marked in red). The total number of ribs is 12.
Step 4
Build a matrix of incidents (edges). To do this, draw a table, the number of rows in it is equal to the number of vertices in the graph, and the number of columns is equal to the number of edges. Put units on those lines that will be connected by an edge. The edges leading from the vertex to it are called loops and are added to the end of the matrix. In the columns corresponding to the loops, there is only one unit, in contrast to the rest of the edges.
Step 5
Now draw a graph. Place the vertices on the paper in any way and connect them with edges using the constructed tables. Vertices that are not connected by edges are called isolated.
