University : University of Madras
Degree : B.Sc
Department :Mathematics
Subject :UCMH Graph Theory
Document type : Question Paper
Website : ideunom.ac.in
Download Previous/ Old Question Paper :
OCT 2011 : https://www.pdfquestion.in/uploads/ideunom.ac.in/6857-._QBNEW_uid32358%20UCMH.pdf
OCT 2012 : https://www.pdfquestion.in/uploads/ideunom.ac.in/6857-._DEC12_uid32358%20UCMH.pdf
OCT 2013 : https://www.pdfquestion.in/uploads/ideunom.ac.in/6857-._DEC2013_uid32358%20UCMH.pdf
May 2011 : https://www.pdfquestion.in/uploads/ideunom.ac.in/6857-._MAY2011_uid32358%20UCMH.pdf
IDEUNOM UCMH Graph Theory Question Paper
U/ID 32358/UCMH
Time : Three hours
Maximum : 80 marks
Related / Similar Question Paper : IDEUNOM B.Sc PAU Real & Complex Analysis Question Paper
October 2011
PART A — (10 ´ 2 = 20 marks)
Answer any TEN questions.
Each questions carries 2 marks.
1. Define bipartite graph with an example.
2. Define regular graph with an example. Is every regular graph is an complete graph.
3. Give an example of a closed walk of even length which does not contain a cycle.
4. Define cut point and bridge with an example.
5. Define Eulerian graph with an example. For what values of n , is n k eulerian?
6. Define planar graph with an example. Is 3 3 K , planar.
7. Show that every non trivial tree G has atleast two vertices of degree 1.
8. Define array and vector
9. Define structure.
10. Write the syntax for if-else statement.
11. What are pointers? Explain with an example.
12. Give any 3 advantages of functions.
PART B — (5 ´ 4 = 20 marks)
Answer any FIVE questions.
Each questions carries 4 marks.
13. Prove that a graph is hamiltonian iff its closure is hamiltonian.
14. Explain Fleur’s Algorithm with an example.
15. Prove that a closed walk of odd length contains a cycle.
16. Show that in any group of two or more people there are always two with exactly the same
number of friends inside the group.
17. Show that 5 K is non-planar.
18. Explain any six characteristic functions.
19. Write a program to find the integral value using Simpson’s rule.
PART C — (4 ´ 10 = 40 marks)
Answer any FOUR questions.
Each questions carries 10 marks.
20. Show that a graph G with atleast two points is bipartite iff its cycles are of even length.
21. Prove that the maximum number of lines among all point graphs with no triangles is [p2/4]
22. Let G be a graph with p points and let u and v be non adjacent points in G such that
d(u) + d(v) ³ p, then prove that G is Hamiltonian iff G + uv is hamiltonian.
23. Write a program to solve a set of simultaneous linear equations.
24. Write down the difference between array and structure.
25. Write a ‘C’ program to find the length and substring of a string using switch statement.
October 2012
U/ID 32358/UCMH
Time : Three hours
Maximum : 80 marks
SECTION A — (10 × 2 = 20 marks)
Answer any TEN questions.
Each question carries 2 marks.
1. Define a regular graph.
2. In a graph G(p,q) prove that S = i i deg V 2q
3. Define a graphic sequence.
4. Define the adjancency matrix of G .
5. Define C(G).
6. Define a tree.
7. Define the main ( ) function.
8. Define constant.
9. What is meant by function in C?
10. How do you open a file?
11. Define string.
12. Define union.
SECTION B : (5 × 4 = 20 marks)
Answer any FIVE questions.
Each question carries 4 marks :
13. Define isomorphic graphs and prove that the following graphs are not isomorphic.
14. If d ³ K , prove that G has a path of length K .
15. If G is a graph in which the degree of every vertex is atleast two, prove that G contains a cycle.
16. Prove that 5 K is non-planar.
17. Explain the formatted output statement.
18. Explain the switch statement with examples.
19. Distinguish between ‘call by reference’ and ‘call by value’.
SECTION C : (4 × 10 = 40 marks)
Answer any FOUR questions.
Each question carries 10 marks :
20. (a) Prove that (G) = (G ).
21. Prove that a partition ( ) p p d ,d …,d 1 2 = of an even number into p-parts with p p -1 ³ d ³ d ³ …³ d 1 2 is graphical if and only if the modified partition. ( ) d d p p d 1,d 1,…d 1,d 1,..,d 2 3 1 1 1 2 ¢ = – – – -+ + is graphical.
22. Prove that the edges of a connected graph G = (V,E) can be oriented that the resulting digraph is strongly connected if and only if every edge of G is contained in atleast one cycle.
23. Describe the different data type in C.
24. Explain the various control statement in C program.
25. Write a C program to find the average of N numbers.