Graphs adt assignment variants

Graphs ADT

Assignment variants:

1. Find a vertex with the minimum degree in the graph.

2. Find a vertex with the maximum degree in the graph.

3. A graph is given. Is it possible to close three roads so that a vertex A cannot be reached from vertex B.

4. Find the median of the graph, i.e. such vertex that the sum of distances from it to all other vertices is minimal.

5. Remove from the graph the vertices from which the given vertex is inaccessible.

6. As the source of the orgraph (ordered graph) we denote a vertex from which all other vertices are reachable; as the sink we denote a vertex reachable from all other vertices. Find all the sources and drains of the orgraph.

7. Check the existence of a cycle in the given graph.

8. Check the existence of a chain in the given graph.

9. Implement Dijkstra's algorithm to find the shortest path between two given graph vertices.

10. A system of two-way roads is given. Find two cities and a path connecting them that passes through each of the roads of the graph exactly once.

11. Find the diameter of the graph, that is, the maximal distance between all possible pairs of its vertices.

12. Calculate the diameter of a given graph.

13. Find the vertex in the graph which is the most distant from the given one.

14. Check the connectivity of the given graph.

15. Determine whether the given graph is a tree.

16. Find all vertices in the graph to which there exists a path of length n from some given one.

17. Find all vertices in the graph from which there exists a path of length n to a given vertex.

18. Determine whether the graph is bipartite.

19. Determine whether the graph is Eulerian.

20. Determine whether the graph is Hamiltonian.

21. Construct a minimal spanning tree in the graph using the Kruskal algorithm.

22. Construct a minimal spanning tree in the graph using Prim's algorithm.

23. Find a vertex with the maximum degree in the given graph.

24. Check the correctness of the statement for a given graph: the number of degrees of graph vertices having odd degree is even.

25. Check the correctness of the statement for a given graph: the sum of powers of all vertices of a graph is equal to twice the number of edges.

26. Using a system of one-way roads determine whether there is a city from which one can get to all other cities

27. Using a system of two-way roads, determine whether by constructing some roads it is possible to get from a given city to all other cities.

28. Using a system of two-way roads, see if you can block some roads so that it would be impossible to get from city A to city B.

29. Given a system of two-way roads and city A. Find all the cities whose distances from city A are greater than n.

30. Determine whether in a given system of one-way roads it is possible to pass from city A to city B in such a way as to visit city C and not to pass any road more than once.