JNTUK B.Tech 2-1(R23) Discrete Mathematics and Graph Theory Important Questions are now available, the candidates can get good marks by reading these questions. Here you can find all the latest syllabus, materials, previous year papers, e-books, important questions ext.
UNIT-I
2-Mark Questions
- Define a proposition and give an example.
- What is a well-formed formula (WFF)? Provide an example.
- Explain the concept of a truth table.
- What is the difference between a tautology and a contradiction?
- Define the terms "free variable" and "bound variable" in predicate logic.
- What is the significance of the duality law in propositional logic?
- State De Morgan's laws and provide an example for each.
- What is a logical connective? List the basic logical connectives.
- Define the term "predicate" in the context of predicate calculus.
- What is the purpose of the indirect method of proof?
10-Mark Questions
- Explain the process of constructing a truth table for a compound proposition. Illustrate your answer with an example involving at least three propositions.
- Discuss the rules of inference in propositional logic. Provide examples of how each rule can be applied to derive conclusions from premises.
- Describe the process of converting a propositional formula into its normal forms (Conjunctive Normal Form and Disjunctive Normal Form). Provide an example to illustrate the conversion.
- Explain the concept of quantifiers in predicate logic. Differentiate between universal and existential quantifiers with examples.
- Discuss the theory of inference for predicate calculus, including the methods used to derive conclusions from premises. Provide examples to illustrate your explanation.
UNIT-II
2-Mark Questions
- Define a set and provide an example of a finite set.
- What is the difference between a subset and a proper subset?
- Explain the union of two sets with an example.
- What is the intersection of two sets? Provide an example.
- Define the Cartesian product of two sets and give an example.
- What is a universal set? How is it used in set theory?
- State the principle of inclusion-exclusion for two sets.
- What is a relation in the context of set theory?
- Define a function and differentiate between injective, surjective, and bijective functions.
- What is a power set? How many elements does the power set of a set with n elements contain?
10-Mark Questions
- Discuss the properties of set operations (union, intersection, difference, and complement) and provide examples for each operation.
- Explain the concept of relations in set theory. Discuss the properties of relations such as reflexivity, symmetry, and transitivity, providing examples for each.
- Describe the different types of functions (injective, surjective, and bijective) with examples. Explain their significance in set theory.
- Explain the principle of inclusion-exclusion for three sets and provide a detailed example to illustrate its application.
- Discuss the concept of equivalence relations and provide examples. Explain how equivalence classes are formed and their significance in set theory.
UNIT-III
2-Mark Questions
- Define permutations and provide the formula for calculating permutations of n objects taken r at a time.
- What is the difference between permutations and combinations?
- State the binomial theorem and provide a simple example.
- What is a recurrence relation? Give an example of a simple recurrence relation.
- Define generating functions and explain their purpose in combinatorics.
- What is the principle of counting? Provide a brief example.
- Explain the concept of combinations and provide the formula for calculating combinations of n objects taken r at a time.
- What is a circular permutation? How does it differ from a linear permutation?
- Define the term "multinomial coefficient" and provide an example.
- What is the significance of the Fibonacci sequence in combinatorics?
10-Mark Questions
- Derive the formula for the number of ways to arrange n distinct objects in a line. Provide examples to illustrate your derivation.
- Explain the concept of the principle of inclusion-exclusion in combinatorics. Provide a detailed example involving the counting of elements in overlapping sets.
- Discuss the method of solving recurrence relations using the characteristic equation method. Provide a detailed example to illustrate the process.
- Explain the concept of generating functions in detail. Show how to use generating functions to solve a combinatorial problem.
- Discuss the applications of combinatorial techniques in computer science, including examples such as algorithm analysis and data structure design.
UNIT-IV
2-Mark Questions
- Define a graph and differentiate between directed and undirected graphs.
- What is a vertex and an edge in the context of graph theory?
- Explain the term "subgraph" and provide an example.
- What is an isomorphic graph? How can you determine if two graphs are isomorphic?
- Define Eulerian and Hamiltonian graphs with examples.
- What is the degree of a vertex in a graph?
- Explain the concept of a connected graph.
- What is a bipartite graph? Provide an example.
- Define a spanning tree and explain its significance in graph theory.
- What is a complete graph? How is it denoted?
10-Mark Questions
- Discuss the different representations of graphs (adjacency matrix, adjacency list, and incidence matrix) and provide examples for each representation.
- Explain Euler's theorem and its application in determining the existence of Eulerian circuits in a graph. Provide an example to illustrate your explanation.
- Describe Hamiltonian paths and circuits. Discuss the necessary and sufficient conditions for a graph to contain a Hamiltonian circuit, providing examples.
- Explain the concept of graph coloring. Discuss the chromatic number of a graph and provide examples of how to determine it.
- Discuss the algorithms for finding the minimum spanning tree of a graph, specifically Prim's and Kruskal's algorithms. Provide a detailed example for each algorithm.
UNIT-V
2-Mark Questions
- Define a multigraph and explain how it differs from a simple graph.
- What is a bipartite graph? Provide an example.
- Explain Euler's theorem in the context of multigraphs.
- What is a planar graph? Give an example of a planar graph.
- Define the chromatic number of a graph and explain its significance.
- What is a spanning tree in the context of multigraphs?
- Explain the concept of graph coloring and its applications.
- What is a clique in graph theory?
- Define a Hamiltonian cycle and provide an example.
- What is the significance of the Traveling Salesperson Problem (TSP) in graph theory?
10-Mark Questions
- Discuss the properties of multigraphs and provide examples to illustrate these properties. Explain how they can be used in real-world applications.
- Explain Euler's circuit and path in detail. Provide a proof of Euler's theorem and illustrate it with an example involving a multigraph.
- Discuss the concepts of bipartite graphs and their applications. Provide examples of real-world problems that can be modeled using bipartite graphs.
- Explain the concept of planar graphs and discuss Kuratowski's theorem. Provide examples of graphs that are and are not planar.
- Discuss the algorithms for finding the chromatic number of a graph. Provide examples to illustrate the application of these algorithms in graph coloring problems.