Graph theory

MathProblemsBank banner

MathProblemsBank banner

Math Problems and solutions

Problem list Free problems

Attention! If a subsection is selected, then the search will be performed in it!

Problem: Find the spanning tree of the minimum weight of the graph. The edge weights are shown in the graph.

6.4.16 Graph theory

2.54 $

Problem: Find the main characteristics of the graph (vertex eccentricities, vertex degrees, adjacency matrix, vertex and edge connectivity numbers, radius, diameter and diametrical chain, density and looseness, chromatic number) represented by the figure. In the case of a disconnected graph, the characteristics should be found for the larger component.

6.4.17 Graph theory

3.82 $

Problem: Find three non-isomorphic spanning trees of the graph. In the case of a disconnected graph, spanning trees must be found for the larger component.

6.4.18 Graph theory

2.04 $

Problem: Find the spanning tree of the minimum weight of the graph. The edge weights are shown in the graph.

6.4.19 Graph theory

2.54 $

Problem: Prove that any \( k \)-connected graph \( G \), built on \( n \geq 2 \) vertices, \( k \geq 2 \), contains a cycle \( C \), length of which is greater than or equal to \( 2 k \).

6.4.20 Graph theory

5.09 $

Problem: Prove that graph \( G \) is edge biconnected if and only if it can be represented as \( G=G_{0} \cup G_{1} \cup \ldots \cup G_{k} \), where \( G_{0} \) is an arbitrary cycle in the graph \( G \), and \( G_{i}, i>0 \), is either a handle, or a closed handle for the subgraph \( G_{0} \cup G_{1} \cup \ldots \cup G_{i-1} \) of graph \( G \).

6.4.21 Graph theory

6.36 $

Problem: Let \( G k \)-vertex connected. We form a new graph \( G^{\prime} \) from \( \mathrm{G} \) by adding a new vertex \( y \) to \( \mathrm{G} \) and at least \( k \) edges from \( y \) in \( k \) different vertices of the graph \( G \). Prove that \( G^{\prime} \) is also \( k \)-connected.

6.4.22 Graph theory

3.82 $

Problem: Using the given weight matrix \( \Omega \) of graph \( G \) find the value of the minimum path and the path itself from vertex \( v_{1} \) to the vertex \( v_{7} \) applying the Bellman-Moore algorithm. \[ \Omega=\left(\begin{array}{ccccccc} - & 6 & \infty & \infty & 12 & \infty & \infty \\ \infty & - & 4 & 10 & \infty & 15 & \infty \\ \infty & \infty & - & 4 & \infty & \infty & \infty \\ \infty & \infty & \infty & - & \infty & \infty & 6 \\ \infty & -8 & 7 & 11 & - & -6 & \infty \\ \infty & \infty & -8 & 7 & 8 & - & 5 \\ \infty & \infty & \infty & \infty & \infty & \infty & - \end{array}\right) \]

6.4.23 Graph theory

5.09 $

Problem: Find the main characteristics of the graph (vertex eccentricities, vertex degrees, adjacency matrix, vertex and edge connectivity numbers, radius, diameter and diametrical chain, density and looseness, chromatic number), represented by the figure. In the case of a disconnected graph, the characteristics should be found for the larger component.

6.4.24 Graph theory

3.82 $

Problem: A weighted graph is defined by a matrix of arc lengths. Plot the graph. Find: a) the minimum weight spanning tree; b) the shortest distance from vertex \( v_{6} \) to the remaining vertices of the graph, using Dijkstra's algorithm. \[ \left[\begin{array}{cccccc} \infty & 2 & 3 & \infty & 1 & \infty \\ 2 & \infty & 1 & 1 & \infty & 4 \\ 3 & 1 & \infty & 5 & \infty & \infty \\ \infty & 1 & 5 & \infty & 4 & 2 \\ 1 & \infty & \infty & 4 & \infty & 3 \\ \infty & 4 & \infty & 2 & 3 & \infty \end{array}\right] \]

6.4.25 Graph theory

6.36 $

Problem: A digraph is defined by an adjacency matrix. It is necessary to: a) draw a graph; b) identify components of strong connectivity; c) replace all arcs with edges and find an Euler chain (or cycle) in the obtained undirected graph. \[ \left(\begin{array}{llllll} 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \end{array}\right) \]

6.4.26 Graph theory

5.09 $

Problem: A weighted graph is defined by a matrix of arc lengths. Plot the graph. Find: a) the spanning tree of minimum weight; b) the shortest distance from vertex \( v_{4} \) to the remaining vertices of the graph, using Dijkstra's algorithm. \[ \left[\begin{array}{cccccc} \infty & \infty & \infty & 2 & 3 & 4 \\ \infty & \infty & 3 & \infty & 1 & 2 \\ \infty & 3 & \infty & 5 & \infty & 1 \\ 2 & \infty & 5 & \infty & 4 & 1 \\ 3 & 1 & \infty & 4 & \infty & \infty \\ 4 & 2 & 1 & 1 & \infty & \infty \end{array}\right] \]

6.4.27 Graph theory

6.36 $

Problem: A digraph is defined by an adjacency matrix. It is necessary to: a) plot the graph; b) identify components of strong connectivity; c) replace all arcs with edges and find an Euler chain (or cycle) in the obtained undirected graph. \[ \left(\begin{array}{llllll} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{array}\right) \]

6.4.28 Graph theory

1.78 $

Problem: A weighted graph is defined by a matrix of arc lengths. Plot the graph. Find: a) the spanning tree of minimum weight; b) the shortest distance from vertex \( v_{4} \) to the remaining vertices of the graph, using Dijkstra's algorithm.

6.4.29 Graph theory

6.36 $

‹
1
2