Anna University Chennai - Important Questions of CS6702 Graph Theory and Applications
B.E/B.TECH DEGREE EXAMINATION NOV / DEC 2016
7th Semester
Department of Computer Science Engineering
CS6702 Graph Theory and Applications
Nov Dec 2016 Important Questions
(Regulation 2013)
CS6702 Graph Theory and Applications - All Important 16 Marks Questions are available below.
CS6702 Graph Theory and Applications
1. Define the following with one example each (a) Infinite graph(b) Hamiltonian path (c) Component of a graph (d) Euler graph (e) Spanning subgraph (f) Arbitrarily traceable graph.
2. Give the explanation to prove that the following graphs G and H are not isomorphic
3. Prove that graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty subsets V1 and V2 such that there exists no edge in G whose one end vertex is in V1 and the other in V2
4. Show that the ring-sum of any two cut-sets in a graph is either third cut-set or an edge disjoint union of cut-sets.
5. Which of the following simple graphs have a Hamilton Circuit or if no, a Hamilton Path?
6. Prove that the ring sum of two cut sets is either a third cut set or an edge disjoint union of two cut sets
7. Using the algorithm of Kruskal, find a shortest spanning tree (study with Example graph)
8. Discuss network flow problem in detail
9. Create the algorithm to find the shortest path from a given source vertex to any vertex in a graph with an example
10. Explain with proof that a graph is non-planar if and only if it contains a sub-graph homomorphic to K5 or K3,3
11. State and explain the Four-Color Problem
12. List and explain various types of digraphs with neat diagram
13. Explain isomorphic digraphs with example
14. Describe chromatic number and chromatic polynomial of a graph? Determine the chromatic number and chromatic polynomial of the following graphs
15. How binary relations are closely related to theory of graphs? Explain in detail
16. State and prove the principle of inclusion and exclusion.
17. List all the combinations of size 3 that results for letters m, r, a, f and t?
18. Let A = {1,2,3,4} and B={u,v,w,x,y,z}. How many oneto-one function f:A->B satisfy none of the following conditions. C1: f(1)= u or v, C2: f(2)=w, C3:f(3)=w or x, C4:f(4)=x,y or z
19. Find the number of ways of ways of arranging the word APPASAMIAP and out of it how many arrangements have all A’s together.
20. Explain the Fundamental principles of counting.
21. Explain Generating functions. Discuss Method of generating functions
22. Find the number of non negative and positive integer solutions of for x1+x2+x3+x4=25.
23. Solve the recurrence relation an= -3an-1- 3an-2- an- 3given that a0=5, a1=9 and a2=15. (study for different series also)
24. Solve the Fibonacci relation Fn = Fn-1+Fn-2.(study for different series also)
25. Solve the recurrence relation S(n) = S(n-1)+2(n-1), with S(0)=3 S(1)=1, by finding its generating function
Thanks for visiting our website for using our study materials, CS6702 Graph Theory and Applications Nov Dec 2016 Important Questions . For more related study materials like previous years question papers, model question papers, question bank, subject notes, etc, use our search box provided at the top of the website. If you have any questions and comments, provided them below.
B.E/B.TECH DEGREE EXAMINATION NOV / DEC 2016
7th Semester
Department of Computer Science Engineering
CS6702 Graph Theory and Applications
Nov Dec 2016 Important Questions
(Regulation 2013)
CS6702 Graph Theory and Applications - All Important 16 Marks Questions are available below.
CS6702 Graph Theory and Applications
1. Define the following with one example each (a) Infinite graph(b) Hamiltonian path (c) Component of a graph (d) Euler graph (e) Spanning subgraph (f) Arbitrarily traceable graph.
2. Give the explanation to prove that the following graphs G and H are not isomorphic
3. Prove that graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty subsets V1 and V2 such that there exists no edge in G whose one end vertex is in V1 and the other in V2
4. Show that the ring-sum of any two cut-sets in a graph is either third cut-set or an edge disjoint union of cut-sets.
5. Which of the following simple graphs have a Hamilton Circuit or if no, a Hamilton Path?
6. Prove that the ring sum of two cut sets is either a third cut set or an edge disjoint union of two cut sets
7. Using the algorithm of Kruskal, find a shortest spanning tree (study with Example graph)
8. Discuss network flow problem in detail
9. Create the algorithm to find the shortest path from a given source vertex to any vertex in a graph with an example
10. Explain with proof that a graph is non-planar if and only if it contains a sub-graph homomorphic to K5 or K3,3
11. State and explain the Four-Color Problem
12. List and explain various types of digraphs with neat diagram
13. Explain isomorphic digraphs with example
14. Describe chromatic number and chromatic polynomial of a graph? Determine the chromatic number and chromatic polynomial of the following graphs
15. How binary relations are closely related to theory of graphs? Explain in detail
16. State and prove the principle of inclusion and exclusion.
17. List all the combinations of size 3 that results for letters m, r, a, f and t?
18. Let A = {1,2,3,4} and B={u,v,w,x,y,z}. How many oneto-one function f:A->B satisfy none of the following conditions. C1: f(1)= u or v, C2: f(2)=w, C3:f(3)=w or x, C4:f(4)=x,y or z
19. Find the number of ways of ways of arranging the word APPASAMIAP and out of it how many arrangements have all A’s together.
20. Explain the Fundamental principles of counting.
21. Explain Generating functions. Discuss Method of generating functions
22. Find the number of non negative and positive integer solutions of for x1+x2+x3+x4=25.
23. Solve the recurrence relation an= -3an-1- 3an-2- an- 3given that a0=5, a1=9 and a2=15. (study for different series also)
24. Solve the Fibonacci relation Fn = Fn-1+Fn-2.(study for different series also)
25. Solve the recurrence relation S(n) = S(n-1)+2(n-1), with S(0)=3 S(1)=1, by finding its generating function
Thanks for visiting our website for using our study materials, CS6702 Graph Theory and Applications Nov Dec 2016 Important Questions . For more related study materials like previous years question papers, model question papers, question bank, subject notes, etc, use our search box provided at the top of the website. If you have any questions and comments, provided them below.
0 comments:
Pen down your valuable important comments below