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 may form.
Instruction manual
1
Let a set of edges of a graph be given and a relation given by which one can draw an edge from one vertex to another. 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.
2
Build a vertex adjacency matrix. To do this, build a square table, the number of rows and columns in the table matches the number of vertices. Then put 1 at the intersection of the i-th row and the j-th column, if the vertices i and j satisfy the given ratio. Put 0 at the intersection of the i-th row and the j-th column, if the ratio for the corresponding elements is not satisfied.
In our example, the first line is filled as follows:
1 + 1 <8, so at the intersection of the 1st row and 1st column is 1
1 + 2 <8, again 1
1 + 3 <8, again 1
…
1 + 7 <8, incorrect inequality, then this table element will be 0
1 + 8 <8, again 0
3
To find out the number of edges, count the number of units in the adjacency matrix, while not ripping the edges.
In the example, a symmetric matrix was obtained, therefore, first the units were calculated above the main diagonal of the matrix (marked in blue), and then the units on the main diagonal (marked in red). The total number of ribs is 12.
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 of the graph, and the number of columns is equal to the number of edges. Put the units in the lines that will be connected by an edge. The edges leading from the top to it are called loops and added to the end of the matrix. In the columns corresponding to the loops, there is only one unit, unlike the other edges.
5
Now draw a graph. Arrange the vertices on paper arbitrarily and connect them with edges using the constructed tables. Vertices not connected by edges are called isolated.
note
The figure shows the ribs for clarity. Usually, the weight of the rib is written over the rib.
