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: Determine which vertices are the source or sink of a given graph. Find strongly connected components and construct a factor graph. Give the necessary explanations.

6.4.1 Graph theory

1.23 $

Problem: Find number of perfect matching. a) in the complete graph \( K_{5} \), b) in the complete bipartite graph \( K_{5,5} \), c) in the graph obtained from the complete bipartite graph \( K_{5,5} \) by erasing four edges adjacent to the vertex \( V_{6} \).

6.4.2 Graph theory

4.94 $

Problem: a) Bring an example of an Eulerian graph with an even number of vertices which does not have a perfect matching. b) Prove that any Hamiltonian graph with an even number of vertices has a perfect matching.

6.4.3 Graph theory

4.94 $

Problem: Using the vertex adjacency matrix, construct a graph diagram. Build flat layout. Create an adjacency matrix of the edges and an incidence matrix. Find the eccentricities of the vertices, the radius and diameter of the graph, peripheral, central vertices, diametrical chains. Find all cycles. Construct a cyclomatic matrix. Color the graph. \[ \left(\begin{array}{lllll} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{array}\right) . \]

6.4.4 Graph theory

6.17 $

Problem: Using the vertex adjacency matrix, construct the graph diagram. Create an arc adjacency matrix, an incidence matrix and a reachability matrix. Arrange the vertices and arcs of the digraph. \[ \left(\begin{array}{llllll} 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{array}\right) . \]

6.4.5 Graph theory

4.94 $

Problem: Given a weight matrix \( \Omega \) of graph \( G \). find the value of the minimum path and the path itself from vertex \( v_{1} \) to vertex \( v_{6} \) using Dijkstra's algorithm, and then the value of the maximum path and the path itself between the same vertices. \[ \left(\begin{array}{cccccc} - & 2 & \infty & 3 & 4 & \infty \\ \infty & - & 6 & \infty & \infty & \infty \\ \infty & \infty & - & \infty & \infty & 2 \\ \infty & 2 & 4 & - & 3 & 7 \\ \infty & 7 & 5 & \infty & - & 10 \\ \infty & \infty & \infty & \infty & \infty & \infty \end{array}\right) . \]

6.4.6 Graph theory

4.94 $

Problem: 1. Write a route, a chain, a simple chain, a cycle, a simple cycle, an adjacency matrix (neighborhood of vertices) and an incidence matrix (belonging to vertices and edges) for the given undirected graph. Convert the given undirected graph into a directed one and write for it a route, a path, a simple path, a contour, a simple contour, an adjacency matrix and an incidence matrix. 2. For the given graph, find the shortest distance for all vertices from vertex 2 . \[ \begin{array}{l} G=(V, E), V=\{1,2,3,4,5\}, \quad E=\{(1,2),(1,3), \\ (1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)\} . \end{array} \]

6.4.7 Graph theory

7.41 $

Problem: Construct a matrix of the basic cutting set (matrix of basic cuts) for the given digraph:

6.4.8 Graph theory

4.94 $

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

6.4.9 Graph theory

1.98 $

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

6.4.10 Graph theory

2.47 $

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.11 Graph theory

3.7 $

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

6.4.12 Graph theory

1.98 $

Problem: Find the spanning tree of the minimum weight of the graph. The weights of the edges are given in the graph.

6.4.13 Graph theory

2.47 $

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.14 Graph theory

3.7 $

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

6.4.15 Graph theory

1.98 $

1
2
›