Question

The neighborhood of a vertex in a graph consists of the vertex itself, together with all vertices that are connected to it by an edge. Each graph has a variable xi associated with the i-th vertex, and the vertex has a known value that is equal to the sum of the variables for all neighborhood vertices. Start with a graph with 5 vertices forming a pentagon, with edges joining vertices 1 and 2, 2 and 3, 3 and 4, 4 and 5, and 5 and 1. Then draw an edge joining vertices 2 and 4, and an edge joining vertices 2 and 5. The known values at vertices 1 through 5 are, respectively, 2, 1, −1, 3, and 5.

(a) Find the augmented matrix for the system of equations satisfied by x₁, x₂, x₃, x₄, x_5.

Answer 1

Given the graph    with 5 vertices, say

Also given that the vertices are connected by the edges

Also the known values at vertices    are respectively.

By the given definition, we will get the neighborhood of each vertices as follows:

Each vertex has a variable associated to it, which is defined as the sum of variables for all neighborhood vertices.

We have

Also by definition,

Hence we get,

Now we obtain the matrix representation of this system of linear equations as,

So the augmented matrix is

NB: It is given in the question that, the value of variables at vertices 1 'through' 5 are respectively 2,1,-1,3,5. By this I understand, the vertices are taken from 1 through 5, i.e, 1,5,4,3,2. If you mean, vertices at 1 'to' 5, the answer will change.

The following is the change:

System of equations is then

And the matrix representation is

Hence the augmented matrix is given by