Analysis of graphs and adjacency matrices question

A step-by-step solution to a computer science exam question: how to determine the number of populated areas in a graph diagram using an adjacency table and arrive at the correct answer.

This article explains a computer science problem involving graph analysis and adjacency matrices to determine the number of settlements on a road map. It describes both a brief algorithm for solving similar problems and a detailed solution to a specific problem from the various exams.

Questions (on graphs) in Computer Science test students’ skills in analyzing and interpreting information presented in the form of diagrams, tables, or adjacency matrices. These tasks may include:

• determining the correspondence between vertices and numbers in the table;
• calculating the sum of road lengths between points;
• Finding the number of edges, vertex degrees, routes, or other properties of a graph.

Problem statement: The figure shows a diagram of roads between settlements (a graph), and the table shows an adjacency matrix, where the rows and columns correspond to each settlement. An asterisk (*) or a numeric value in a table cell indicates the presence of a road or its length between two settlements.

Specified graph properties are required —for example, vertex numbers, road length, the sum of distances between points, or the number of connections. The result is written as a number, a set of numbers, or another format specified in the problem.

Key concepts needed for solution:

• Scheme (graph) – vertices denote points, edges denote roads between them.
• Table (adjacency matrix) – N × N table where a cell indicates the presence of a road or its length.
• Undirected graph – the road can be used in any direction; sometimes there are directed graphs where the direction matters.

For a successful solution, it is important to be able to:

• analyze relationships on a graph;
• compare the data in the diagram and table;
• perform calculations with numbers if road lengths are given.

How to solve such problems?

The approach to solving such problems can be divided into several steps:

1. Graph analysis:

• Determine the degree of each vertex – the number of connections to other points.
• If road lengths are given, write them down separately for each pair of vertices.
• Find unique peaks or roads – they will help you quickly compare the diagram and the table.

2. Comparison of the data in the diagram and the table:

• Compare the connections between the nodes in the diagram and the data in the adjacency table.
• For vertices connected to known points, determine the missing properties (vertex numbers in the table, length of roads, number of connections or routes).

3. Calculation of the required values:

• If you need the sum of the lengths, add up the lengths of the required edges.
• If you need to count routes, connections, or vertex degrees, mark all the edges you count to avoid mistakes.
• Use the adjacency table to check the correctness of your calculations.

4. Recording the answer. Record the result in the format specified in the problem statement:

• an integer (for example, the sum of road lengths);
• a set of numbers in ascending order (for example, vertex numbers);
• other formats, if specified in the task.

Tips for beginners:

• Start with unique vertices or edges to quickly identify mappings.
• Always double-check the data in the diagram and table to avoid errors.
• For problems with long paths or sums, use notes or a table to ensure you don’t miss any edges.
• This algorithm is universal: it is suitable for all graph tasks on the Unified State Exam, including matching vertices, calculating the sum of road lengths, and counting connections.

Graph and Diagram

Problem Description: The figure shows a road map between settlements, and the table shows an adjacency matrix, where the rows and columns correspond to each point. An asterisk (*) in a table cell indicates the presence of a road between two points. The task is to determine which numbers in the table correspond to points B and E on the map and write them as two numbers in ascending order, without spaces or punctuation.

The problems in this Computer Science question use undirected graphs, meaning graphs without directions on their edges. This allows students to navigate between vertices in any direction. The key skill for solving the problem is analyzing relationships in the graph and matching them with an adjacency table.

Solution algorithm. Problems of this type are solved in sequential steps, where the step numbers are determined based on the number of connections (vertex degrees) and their interrelations.

Step 1. Identify unique vertices based on their number of edges. First, let’s carefully examine the diagram and count the number of connections for each vertex. Vertices with a unique number of edges allow us to uniquely match them with their numbers in the table.

Vertex A is connected to three points. Since there are no other vertices with this number of edges, A corresponds to number 3 in the table.

Vertex D is connected to five points. Since there are no other vertices with this degree, D corresponds to the number 7.

Step 2. Determine the numbers for vertices C and G. Once the numbers of vertices A and D have been determined, let’s turn our attention to vertices C and G, which are connected to these two points:

• Each of them has two connections: one leads to A (with three edges), the other to D (with five edges).
• There are only two numbers left in the table that meet these conditions: 1 and 4.
• The mutual distribution between C and G is irrelevant, since it does not affect the solution.

Step 3. Determine the number for vertex F. Vertex F has two connections, but is not connected to D.

Since vertex D is already associated with number 7, we need to find among the remaining numbers one that has two connections but is not connected to D . The only number that fits these conditions is 5. Thus, vertex F corresponds to number 5.

Step 4. Determine the numbers for vertices B and E. After matching all the remaining vertices, the numbers remaining are 2 and 6 :

Since all other vertices already have numbers, the remaining numbers are 2 and 6, which correspond to vertices B and E. The order in which the numbers are assigned to B and E is irrelevant, as the problem only requires them to be listed in ascending order.

In your answer, write the numbers of vertices B and E in ascending order, without spaces or punctuation. Therefore, the correct answer is 26 .

A variant from the demo version

Solution:

We are given a road map (graph), where the vertices are labeled with letters (A, B, C, D, E, F, G), and an adjacency table, where the vertices are numbered from 1 to 7. We need to figure out which letter corresponds to which number, and then determine what numbers vertices B and C might have.

Step 1. Determine the degrees of the vertices. The degree of a vertex is the number of roads that exit it. On the graph:

• peaks A, B, C have 2 roads each;
• peaks D, E, F, G have 3 roads each.

In the adjacency table:

• vertices 3, 6, 7 are connected to exactly two others → degree 2;
• vertices 1, 2, 4, 5 are connected to three others → degree 3.

Hence:

• A, B, C ⇔ {3, 6, 7}
• D, E, F, G ⇔ {1, 2, 4, 5}

Step 2. Analyze vertices of degree 3. Now we look not only at the number of roads, but also at the neighbors of each vertex.

• Vertex 1 is connected to 2, 3, and 4. Among its neighbors, two have 3 roads (2 and 4), and one has 2 roads (3). In the graph, this corresponds to vertices F and G. Therefore, 1 is either F or G.
• Vertex 2 is connected to 1 (3 roads), 3 (2 roads), and 6 (2 roads). Two neighbors have 2 roads each, corresponding to vertices D or E. Therefore, 2 is either D or E.
• Vertex 4 is connected to 1 (3 roads), 5 (3 roads), and 7 (2 roads). Two neighbors have 3 roads, and one has 2 roads. Therefore, again, F or G.
• Vertex 5 is connected to 4 (3 roads), 6 (2 roads), and 7 (2 roads). Two neighbors with 2 roads and one with 3 are either D or E.

Step 3. Analyze vertices of degree 2. Now let’s analyze vertices {3, 6, 7}.

• Vertex 3 is connected to 1 and 2, so it fits either B or C.
• Vertex 6 is connected to 2 and 5 (both in {D, E}). Therefore, it is A.
• Vertex 7 is connected to 4 (F or G) and 5 (D or E). Therefore, it fits B or C.

Step 4. Final comparison:

• A → 6;
• B, C → 3 and 7.

Since the problem asks about vertices B and C, they correspond to numbers 3 and 7. In ascending order: 37.

Answer: 37.

Explore More IT Terms