Assignment must be submitted by 28th July, 2024
- Define odd degree vertex and even degree vertex in a graph. State the Handshaking Theorem for an undirected graph G (V,E).
- Show that the numbers of odd vertices in any graph is always even.
- Discuss adjacency matrix representation of a graph with suitable example.
- What is graph isomorphism? Show that the graphs in the following figure are not isomorphic.
- What is Complete Bipartite graph? Consider the following graph G = {V,E}, where V = {u1,u2 ,w1,w2 ,w3}, is it bipartite?
- Differentiate between Euler and Hamiltonian circuits and paths with example.
- Explain the process of identifying whether the graph is reflexive, symmetric or transitive by using digraph with suitable example.
- Using Dijkstra’s algorithm, find the shortest path from vertex a to z.
- What is spanning tree? State a necessary and sufficient condition for a graph to have a spanning tree. Draw all spanning trees of the following graph.
- How many spanning trees are possible from complete graph ? In which order does the pre-order, in-order and post-order traversal visit the vertices in rooted tree.
- If D(V, A) be a directed graph, where the vertices set V= {a, b, c, d, e, f, g, h, i, j} and the directed edges set E = {(b, c), (b, a), (d, e), (d, f), (e, h), (f, g), (d, b), (g, i), (g, j)}, show that D(V, E) is a rooted tree and identify the root and leaves. Also find the height of the tree.
- Discuss Kruskal’s algorithm for constructing a minimum spanning tree. Use Kruskal’s algorithm to find minimum spanning tree in the graph given below.
- From the following successor list of a directed graph D(V,E):
- Construct the adjacency matrix of the diagraph.
- Find in-degree and out-degree of each vertex from the adjacency matrix.
- Find the number of directed edges and verify that ∑od (V1) = ∑id (V1) = [E]
- Determine whether D is unilaterally connected or/ and strongly connected.
- A tree has two vertices of degree 2, one vertex of degree 3 and three vertices of degree of 4. How many pendant vertices does it have?
- Use BFS and DFS to produce a spanning tree for the following simple graph, choosing ‘d’ as the root of the spanning tree.
