Discrete Mathematics 2018 Question Paper — Government College of Engi…
The 2018 Discrete Mathematics previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.
- University: Government College of Engineering and Technology, Jammu
- Subject: Discrete Mathematics
- Course: DISCRETE MATHEMATICS
- Branch: Computer Engineering
- Year: 2018
- Paper: end-term
- Duration: 180 minutes
- Total marks: 100
Instructions
- Attempt five questions in all, selecting at least two questions from each section. Each section carries 20 marks.
Questions
Section-A
- Q1. (a) Show that the set $Q^+$ of all positive rational numbers form an abelian group under operation $o$ defined by : $aob = \frac{ab}{2}, \forall a,b \in Q^+$. (b) Show that the intersection of two subgroups of a group is again a subgroup. (c) Show that the sum of first '$n$' natural numbers is $\frac{n(n+1)}{2}$.
- Q2. (a) Show that the set of all positive rational numbers is a countably infinite set. (b) Show that the function, $f:R \to R$ defined by $f(x) = 2x^3 + 1, \forall x \in R$ is a bijection. (c) Determine the no. of integers between 1 and 250 which are divisible by any of the integers $2, 3, 5, 7$.
- Q3. (a) State and prove De-Morgan's law. (b) Show that the relation of parallel lines in a plane is an equivalence relation. (c) Prove that a field is an integral domain. Is the converse of this statement true? Explain
- Q4. (a) Prove that a ring $R$ is without zero divisors iff cancelation laws hold in it. (b) Let $f:G \to G'$ be a group homomorphism. Then show that kernel of $f$ is a normal subgroup of $G$. (c) Prove that any two left (right) cosets of a subgroup in a group are either identical or disjoint.
Section-B
- Q5. (a) Write in detail about Konigsberg bridge problem. (b) Define the following terms : (i) Graphs (ii) Walk (iii) Path (iv) Circuits (v) Euler graph (vi) Hamiltonian Circuit (vii) Trees (c) Prove that any connected graph with $n$ vertices and $n-1$ edges is a tree.
- Q6. (a) Find the shortest path in the given below weighted graph : (A is the starting point). (b) What is Travelling-Salesman problem ? (c) Prove that a tree with $n$ vertices has $n-1$ edges.
- Q7. (a) Prove that every connected graph has at least one spanning tree. (b) Prove that every circuit has an even number of edges in common with every cutset. (c) Give an example of a graph that has : (i) Both a Hamiltonian circuit and Euler circuit. (ii) Euler circuit but not Hamiltonian circuit.
- Q8. (a) Prove that a given connected graph $G$ is an Euler graph iff all vertices of $G$ are of even degree. (b) Prove that every cut-set in a connected graph $G$ must contain at least one branch of every spanning tree of $G$. (c) State and prove Euler's formula.
Related pages
Other years
- Discrete Mathematics 2022 question paper — end-term
- Discrete Mathematics 2018 question paper — end-term