B.TECH - Semester 8 graph theory Question Paper 2019 (nov)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Explain the terms rank and nullity of a graph. How are they related?
- What do you mean by a self-dual graph? Give an example.
- Define the adjacency matrix and successor listing representations of a graph with an example.
- Give the definition of a sequential machine with an example
- Explain the terms in-degree and out-degree in a directed graph. How are they related? Give an example. each module, Each question carries 20 marks
- (a) Find the minimum spanning tree of the following graph using Prim's algorithm.
- (b) Prove that a simple graph with $n$ vertices and $k$ components have at most $(n-k)(n-k+1) / 2$ edges.
- (a) State Cayley's theorem. Draw all the possible trees of four labeled vertices.
- (b) Explain the six difference operations on graphs with examples.
- (a) Prove that in the vector space of a graph, the circuit subspace and the cutset subspace are orthogonal to each other.
- (b) How long is a longest circular (or cyclic) sequence of 1's and 0's such that no subsequence of $r$ bits appears more than once is the sequence? Construct one such longest sequence.
- (a) What is an Arborescence? Prove that an arborescence is a tree in which every vertex other than the root has an in-degree of exactly one.
- (b) State and prove Euler's formula and its corollary.
- (a) Explain the algorithm to find the shortest path between all pairs of vertices in a graph G with an example.
- (b) What is the graph isomorphism problem? Explain a heuristic procedure to check whether two graphs are isomorphic or not.
- (a) Explains the depth-first search algorithm in a graph $G$ with an example.
- (b) Explain the algorithm to find out the number of components in a given graph G.
- Design a sequential machine to respond to an arbitrary input sequence of 0 's and 1's. The machine should produce an output of 1 whenever there appears a set of four consecutive input bits of value greater than 9 in a serial 8-4-2-1 BCD code (the lea...
- (a) Write a note on m-cubes and its properties. Draw the graphs of 3-cube and 4-cube.
- (b) Write a note on graphs in coding theory.
- Prove the following. "A Graph G is disconnected if and only if its vertex set V can be partitioned into two non empty disjoint subsets $V_{1}$ and $V_{2}$ such that there exists no edge in $G$ whose one end vertex is in $\mathrm{V}_{1}$ and other in ...
- Find the number of vertices of a graph with 12 edges, where 6 vertices have degree 3 and other vertices have degree less than 3 . Draw the graphs.
- Prove that in any undirected graph, the number of vertices of odd degree should be even.
- Define the term fundamental circuit. Give an example.
- If a connected graph G has n vertices, e edges and r regions, then prove that $n-e+r=2$.
- Prove that the ring sum of two circuits in a graph G is either a circuit or an edge disjoint union of circuits.
- Distinguish between strongly and weakly connected digraphs.
- Find the transmission matrix for the following contact network.
- Explain the switching functions of m-cube.
- Explain the properties of state Graphs in sequential switching networks. ( $\mathbf{1 0} \boldsymbol{\times} \mathbf{4} \boldsymbol{=} \mathbf{4 0}$ Marks) Answer any one full questions from each Module. Each question carries 20 marks
- (a) Prove that a simple graph with n vertices and k components can have at the most $\frac{(n-k)^{*}(n-k+1)}{2}$ edges.
- (b) Define Center of a graph. Prove that every tree has one or two centers
- (c) Prove that "in a complete graph with n vertices, there are $\frac{(n-1)}{2}$ edge disjoint Hamiltonian circuits, if n is an odd number $\geq 3$ OR 2 H - 3416
- (a) Write and explain Prim's Algorithm. Analyze the complexity.
- (b) Consider the following Graph. How many different MSTs can be obtained using Prim's algorithm starting from vertex 'a'? Draw all MSTs starting from vertex 'a'.
- (a) Define Geometric Dual and combinational Dual of a graph. Give Example. 8
- (b) For the graph given below check whether the circuit vector space $W_{r}$ is orthogonal complement to cutest vector space $\mathrm{W}_{\mathrm{s}}$.
- (c) Describe the methods used to check the planarity of a graph. OR
- (a) Consider the graph. 3 LIBRARY
- (i) Define the basis of $\mathrm{W}_{\mathrm{r}}$ and $\mathrm{W}_{\mathrm{s}}$. (ii) Write the basis of $\mathrm{W}_{\mathrm{r}}$ and $\mathrm{W}_{\mathrm{s}}$ (iii) Compute the subspaces $\mathrm{W}_{\mathrm{r}}$ and $\mathrm{W}_{\mathrm{s}}$ (iv) ...
- (b) A necessary and sufficient condition for two planar graphs $G_{1}$ and $G_{2}$ to be duals of each other is as follows: There is one-to-one correspondence between the edges in $\mathrm{G}_{1}$ and edges in $\mathrm{G}_{2}$ such that a set of edg...
- (a) Write an algorithm to print the connected components of a graph. Analyze the complexity.
- (b) What are contact networks? Explain the synthesis of contact networks.
- (a) Write an algorithm to find the directed circuits in a digraph.
- (b) Write brief notes on the application of graphs in coding theory.