DISCRETE MATHEMATICS - U20MABT08

                  DISCRETE MATHEMATICS 

UNIT - 1

PART - A 

1. What is meant by proposition.

   A proposition is a declarative statement that can either be true or false, but not both. For example, "The sky is blue" is a proposition.

2. Define Tautology and Contradiction.

   - Tautology: A statement that is always true, no matter the truth values of its components. For example, \( P \lor \neg P \) (either \(P\) is true or \(P\) is false).

   - Contradiction: A statement that is always false, regardless of the truth values of its components. For example, \( P \land \neg P \) (a statement cannot be both true and false at the same time).

3. Write down DeMorgan’s law.

   - \( \neg (P \land Q) = \neg P \lor \neg Q \): The negation of a conjunction is the disjunction of the negations.

   - \( \neg (P \lor Q) = \neg P \land \neg Q \): The negation of a disjunction is the conjunction of the negations.

4. Check whether the sentence is a proposition or not

(i) Dog is an animal: Yes, because it is a statement that is either true or false.  

(ii) Rose is an animal: Yes, because it is a statement that is either true or false.  

(iii) Sun rises in the east: Yes, this is a fact that is either true or false.  

(iv) \( x^2 + 9 = 0 \): No, because the truth value depends on the value of \(x\), so it is not a proposition in general.

5. Define Atomic statement. 

   An atomic statement is a simple, indivisible statement that does not contain any logical connectives. Example: "The sky is blue" is atomic.

6. Define Molecular statement.

   A molecular statement is a compound statement formed by combining atomic statements using logical connectives like AND (\( \land \)), OR (\( \lor \)), and NOT (\( \neg \)).

7.Define well-formed formulas.

   Well-formed formulas (WFFs) are logical expressions that are correctly structured according to the rules of propositional logic, meaning they are syntactically valid.

8. Write the dual of \( (P \land \neg Q) \lor R \).

   The dual of a logical expression is obtained by replacing AND (\( \land \)) with OR (\( \lor \)) and OR (\( \lor \)) with AND (\( \land \)), and also replacing \( \neg \) with \( \neg \). The dual of \( (P \land \neg Q) \lor R \) is \( (P \lor \neg Q) \land R \).

9. Define PCNF and PDNF.

   - PCNF (Principal Conjunctive Normal Form): A formula expressed as a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals.  

   - PDNF (Principal Disjunctive Normal Form): A formula expressed as a disjunction (OR) of minterms, where each minterm is a conjunction (AND) of literals.

10. What do you mean by a rule CP?

    CP (Conditional Proof)  is a method used to prove an implication \(P \to Q\). You assume \(P\) as true and then derive \(Q\). If you can prove \(Q\) from this assumption, then the implication \(P \to Q\) is valid.

UNIT - 1

PART - B 

1. Truth Table for (P → Q) ↔ (¬P ∨ Q)

P	Q	¬P	¬P ∨ Q	(P → Q) ↔ (¬P ∨ Q)
True	True	False	True	True
True	False	False	False	True
False	True	True	True	True
False	False	True	True	True

2. Prove ((P → Q) ∧ (Q → R)) → (P → R) is a Tautology

To prove that the expression is always true:

• Expand: \( P → Q ≡ ¬P ∨ Q \) and \( Q → R ≡ ¬Q ∨ R \).
• Combine: \(((¬P ∨ Q) ∧ (¬Q ∨ R)) → (¬P ∨ R)\).
• The truth table verifies that the expression evaluates to True for all inputs.

P	Q	R	P → Q	Q → R	(P → Q) ∧ (Q → R)	P → R	Final Result
True	True	True	True	True	True	True	True
True	True	False	True	False	False	False	True
True	False	True	False	True	False	True	True
False	True	False	True	True	True	True	True

3. Show R → S Can Be Derived

Given the premises:

• \( P → (Q → S) \equiv ¬P ∨ (¬Q ∨ S) \)
• \( ¬R ∨ P \)
• \( Q \)

By substituting and simplifying:

• If \( R \) is true, then \( P \) is true (from \( ¬R ∨ P \)).
• Given \( P → (Q → S) \) and \( Q \), we deduce \( S \) must be true.
• Thus, \( R → S \) holds logically.

4. Without Truth Table, Prove (P ∨ Q) ∧ (¬P ∨ Q) ↔ P

Step-by-step:

• Expand the left-hand side: \( (P ∨ Q) ∧ (¬P ∨ Q) \).
• Simplify using distribution: \( Q ∨ (P ∧ ¬P) \equiv Q ∨ False \equiv Q \).
• The equivalence simplifies to \( P ↔ P \), which is true.

5. Prove (∀x)M(x) Follows from (∃x)H(x) → M(x) and (∃x)H(x)

Logical Steps:

• Premise 1: \( (∃x)(H(x)) → (∀x)(M(x)) \equiv ¬(∃x)(H(x)) ∨ (∀x)(M(x)) \).
• Premise 2: \( (∃x)(H(x)) \).
• From Premise 2, the first term of Premise 1 is false, leaving \( (∀x)(M(x)) \) as true.

Thus, \( (∀x)(M(x)) \) follows logically.

6. Truth Table for (P → Q) ∧ (P → R) ↔ P → (Q ∧ R)

P	Q	R	P → Q	P → R	(Q ∧ R)	P → (Q ∧ R)	Final Result
True	True	True	True	True	True	True	True
True	True	False	True	False	False	False	True
True	False	True	False	True	False	False	True
False	True	False	True	True	False	True	True

UNIT - 1

PART - C 

1. Show that ¬(P ↔ Q) ⇔ (P ∨ Q) ∧ ¬(P ∧ Q).

(i) Using truth table.

(ii) Without using truth table.

2.Find the PDNF and PCNF of ¬((P ∨ Q) ∧ R) ∧ (P ∨ R).  - imp

3.Find the PDNF and PCNF of (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R).  - imp

4 . By constructing the truth table, prove that (P ∨ Q) ∧ (P → R) ⇔ P → (Q ∧ R).

8 . Show that without using truth table:
¬(P ∧ Q) → (¬P ∨ ¬P ∨ Q)) ⇔ (¬P ∨ ¬Q).

UNIT - 2

PART - A 

1. Define Permutation and Combination.

A.  Permutation refers to the arrangement of objects in a specific order.  

     Combination refers to the selection of objects without considering the order.  

2. Write the formula to find \( {}^nP_r \) and \( {}^nC_r \).

  A . Formula for permutation: \( {}^nP_r = \frac{n!}{(n-r)!} \).  

     Formula for combination: \( {}^nC_r = \frac{n!}{r!(n-r)!} \).

3. What is Fibonacci sequence? 

A.The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1.  

     Example: 0, 1, 1, 2, 3, 5, 8, 13, ...

4. Define Recurrence relation.

A. A recurrence relation is an equation that recursively defines a sequence, where each term is defined as a function of its preceding terms.

5. In how many ways can a team of 11 players be chosen out of 15 players?  

A. Use the combination formula:  

     \( {}^{15}C_{11} = \frac{15!}{11!(15-11)!} = \frac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = 1365 \).  

     Therefore, 1365 ways.

6. If \( {}^nP_2 = 4 \times {}^{12}P_2 \), then find \( n \). 

A. \( {}^nP_2 = n(n-1) \), and \( {}^{12}P_2 = 12 \times 11 = 132 \).  

     Given, \( n(n-1) = 4 \times 132 = 528 \).  

     Solve: \( n^2 - n - 528 = 0 \).  

     Using the quadratic formula, \( n = 24 \) (only positive solutions are valid).  

7. Define Pigeonhole Principle.

A. The pigeonhole principle states that if \( n \) items are put into \( m \) containers, where \( n > m \), then at least one container must contain more than one item.

8. How many arrangements can be made from the word "MATHEMATICS"?

A.  The word "MATHEMATICS" has 11 letters, with the following repetitions:  

     M = 2, A = 2, T = 2, H = 1, E = 1, I = 1, C = 1, S = 1.  

     Total arrangements:  

     \( \frac{11!}{2! \times 2! \times 2!} = \frac{39916800}{8} = 4989600 \).  

9. How many arrangements can be made from the word "MISSISSIPPI"?

A. The word "MISSISSIPPI" has 11 letters, with the following repetitions:  

     M = 1, I = 4, S = 4, P = 2.  

     Total arrangements:  

     \( \frac{11!}{4! \times 4! \times 2!} = \frac{39916800}{1152} = 34560 \).  

10. How many arrangements can be made from the word "ASSASSINATION"?

A. The word "ASSASSINATION" has 13 letters, with the following repetitions:  

      A = 3, S = 4, I = 2, N = 2, T = 1, O = 1.  

      Total arrangements:  

      \( \frac{13!}{3! \times 4! \times 2! \times 2!} = \frac{6227020800}{288} = 21621600 \).  

UNIT - 2

PART - B

1. Using Mathematical Induction, Prove that 1 + 2 + 3 + ... + n = n(n+1)/2

Step 1: Base Case
For n = 1:
LHS = 1.
RHS = (1(1+1))/2 = 1.
Since LHS = RHS, the base case holds.
Step 2: Inductive Hypothesis
Assume the formula is true for n = k:
1 + 2 + 3 + ... + k = k(k+1)/2.
Step 3: Prove for n = k+1:
We need to show:
1 + 2 + ... + k + (k+1) = ((k+1)(k+2))/2.
Start with the hypothesis:
1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1).
Combine terms:
(k(k+1) + 2(k+1))/2 = ((k+1)(k+2))/2.
Thus, true for n = k+1. By induction, the formula is true for all n.

 2. Find the number of words (with or without meaning) formed from "RINGING", "PARROT",

"CHERRAPUNJI"

For "RINGING":

Total letters = 7, Repeated letters: G = 2, N = 2.

Permutations = 7! / (2! * 2!) = 1260.

For "PARROT":

Total letters = 6, Repeated letters: R = 2.

Permutations = 6! / 2! = 360.

For "CHERRAPUNJI":

Total letters = 12, Repeated letters: R = 2, I = 2.

Permutations = 12! / (2! * 2!) = 119750400.

 3. How many cricket matches are there if 7 teams play each other once?

Each match involves 2 teams:

7C2 = (7 * 6)/2 = 21 matches.

 4. Minimum students needed to guarantee 5 in one subject (English, Maths, Physics,

Chemistry):

Detailed Step-by-Step Explanation

Using the Pigeonhole Principle:

4 subjects * 4 = 16 (4 in each subject). Adding 1 ensures 5 in one subject.

Minimum students = 17.

5. Ways to form a cricket team of 11 from 15 (7 bowlers), with at least 5 bowlers

6 . Show that among 100 people, at least 9 of them were born in the same month.

A.There are 12 months. Using the Pigeonhole Principle, divide 100 people among 12 months:

• $\mathrm{[100}\mathrm{/}12\rceil =9$.
  Hence, at least 9 people were born in the same month

7. Show that if 25 dictionaries in the library contain a total of 40,325 pages, then one of the dictionaries

must have at least 1614 pages.

A.If each dictionary had exactly \( 40,325 / 25 = 1613 \) pages, the total would be 40,325.

If one dictionary has fewer than 1614 pages, another must have more than 1614 to balance the total.

Hence, at least one dictionary must have \( \geq 1614 \) pages.

8. Find the minimum number of students to guarantee that 5 of them belong to the same subject, having

majors in English, Maths, Physics, and Chemistry.

A.Same as Question 4. Minimum = 17 students

10. How many arrangements can be made from the words "CHAIR," "INDIA," and "SWIMMING"?

UNIT - 2

PART - C 

1.Solve the recurrence relation:
$s(n)-4s(n-1)-11s(n-2)+30s(n-3)=0$
with $s(0)=0$, $s(1)=-35$, $s(2)=-85$.  -imp

            

2.Write the recurrence relation for Fibonacci numbers and hence solve it.

3. Solve the recurrence relation:

$u_{n+3}-6u_{n+2}+11u_{n+1}-6u_n=0$
with $u_0=2$, $u_1=0$, $u_2=-2$. -imp

4 . Solve the recurrence relation:
$s(k)-10s(k-1)+9s(k-2)=0$, $k\ge 0$,

5 . Solve the recurrence relation:

$y(n)-3y(n-1)-4y(n-2)=4^n$.

6 . Solve the recurrence relation:
$s(k)-5s(k-1)+6s(k-2)=2$,
with $s(0)=1$, $s(1)=-1$.

7. Solve the recurrence relation:

$s(k)-7s(k-1)+10s(k-2)=6+8k$.

UNIT - 3

PART - A 

1. What is a Complete Bipartite Graph?

A Complete Bipartite Graph is a graph in which the vertex set can be divided into two disjoint sets such that every vertex in the first set is connected to every vertex in the second set, and no edges exist within a set. This type of graph is denoted as $K_{m,n}$, where $m$ and $n$ are the sizes of the two sets.

2. What is a Hamiltonian Graph?

A Hamiltonian Graph is a graph that contains a Hamiltonian cycle, meaning there exists a cycle that visits every vertex exactly once and returns to the starting vertex. A Hamiltonian cycle must include each vertex at least once and the cycle should be closed.

3. Define Adjacency Matrix with Example.

An Adjacency Matrix is a square matrix used to represent a graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. If there is an edge between two vertices, the corresponding matrix entry is 1, otherwise it is 0.

Example: Consider the graph with vertices $A,B,C$ and edges $(A,B),(B,C)$.

The adjacency matrix is:

                                                    

4. Define Graph Isomorphism.

Graph Isomorphism refers to the concept where two graphs $G_1$ and $G_2$ are isomorphic if there exists a one-to-one correspondence between their vertices and edges, preserving adjacency. In other words, the structure of the graphs is identical, but the labeling of vertices may differ.

5. State Handshaking Theorem.

The Handshaking Theorem states that in any graph, the sum of the degrees of all vertices is twice the number of edges. Mathematically, this is expressed as:

$$\sum \text{degree of vertices}=2\times \text{number of edges}\mathrm{.}$$

This is because each edge contributes to the degree of two vertices.

6. Define Incidence Matrix with Example.

An Incidence Matrix is a matrix that represents the relationship between vertices and edges of a graph. In this matrix, the rows represent the vertices and the columns represent the edges. The entry is 1 if the vertex is incident to the edge, and 0 if it is not.

Example: For a graph with vertices $A,B,C$ and edges $e_1=(A,B),e_2=(B,C)$, the incidence matrix would be:

                                                

7. What is a Cubic Graph and Give Two Examples?

A Cubic Graph is a graph where each vertex has degree 3. This means that each vertex is connected to exactly three edges.

Examples:

• The Petersen graph is a well-known cubic graph.
• The 3-regular graph on 4 vertices.

8. Define Degree of a Vertex and Give One Example.

The Degree of a Vertex in a graph is the number of edges incident to it. It indicates how many connections the vertex has with other vertices.

Example: In the graph with vertices $A,B,C$ and edges $(A,B),(B,C)$, the degree of vertex $B$ is 2 (since it's connected to $A$ and $C$).

9. What is a Directed Graph and Give One Example?

A Directed Graph (Digraph) is a graph where edges have a direction, meaning each edge has a starting vertex and an ending vertex. This is represented by directed edges (arcs) with arrows.

Example: A directed graph with vertices $A,B,C$ and edges $(A\to B),(B\to C)$ is a directed graph where $A$ points to $B$, and $B$ points to $C$.

10. Define Eulerian Graph.

An Eulerian Graph is a graph in which there exists an Eulerian circuit, i.e., a cycle that uses every edge of the graph exactly once and returns to the starting vertex. A graph is Eulerian if and only if all of its vertices have an even degree, and it is connected.

UNIT - 3

PART - B 

1. Write the incidence matrix of the given graph

An incidence matrix shows the relationship between vertices and edges. Let the vertices of the given graph be $v_1,v_2,v_3,v_4,v_5$, and edges be $e_1,e_2,e_3,e_4,e_5,e_6$. The rows of the matrix correspond to vertices, and the columns correspond to edges.

• A cell in the matrix contains:
  • 1 if the vertex is incident to the edge,
  • 0 otherwise.

For the provided graph:

• Analyze each vertex and edge. If $e_1$ connects $v_1$ and $v_2$, the matrix will have 1s at those positions under $e_1$.
• Example structure of the matrix
• 

2. Check whether the given graphs are isomorphic or not

A.Two graphs are isomorphic if they have:

1. The same number of vertices and edges.
2. Vertices of the same degree.
3. The same adjacency structure (can be redrawn to look identical).

Steps to verify:

• Count vertices and edges in both graphs: If unequal, they are not isomorphic.
• Compare vertex degrees: If the degree of any vertex differs in the two graphs, they are not isomorphic.
• Match adjacency patterns: If vertex connections align perfectly, the graphs are isomorphic.

For the given graphs in the image:

1. Both have 6 vertices and 9 edges.
2. The degree sequence (arranged degrees of vertices) matches: $\mathrm{<span\; class="katex"\; style="white-space:\; normal;"><span\; class="mord">3</span><span\; class="mpunct">,</span><span\; class="mspace"></span><span\; class="mord">3</span><span\; class="mpunct">,</span><span\; class="mspace"></span><span\; class="mord">3</span><span\; class="mpunct">,</span><span\; class="mspace"></span><span\; class="mord">2</span><span\; class="mpunct">,</span><span\; class="mspace"></span><span\; class="mord">2</span><span\; class="mpunct">,</span><span\; class="mspace"></span><span\; class="mord">2</span></span><span\; style="white-space:\; normal;">.</span>}$
3. Adjacency relationships can be redrawn to match exactly.

Hence, the graphs are isomorphic.

3. State and prove the Handshaking Theorem

Theorem Statement:
In any undirected graph, the sum of the degrees of all vertices equals twice the number of edges:

∑deg(vi​)=2∣E∣

Here, $v_i$ represents vertices and $\mathrm{\mid }E\mathrm{\mid }$ represents edges.

Proof:

1. Each edge in an undirected graph contributes 1 to the degree of each of its two endpoints.
2. Thus, each edge is counted twice when summing all vertex degrees.
3. The sum of degrees is therefore $2\mathrm{\mid }E\mathrm{\mid ,\; where }$$\mathrm{\mid }E\mathrm{\mid }$ is the total number of edges.

Example: Consider a graph with:

• 4 vertices: $v_1,v_2,v_3,v_4$
  
• 5 edges: $e_1,e_2,e_3,e_4,e_5$
  

Degrees of vertices:

deg(v1​)=2,deg(v2​)=3,deg(v3​)=2,deg(v4​)=3

Sum of degrees:

$$2+3+2+3=10=2\cdot 5$$

4. Prove that the number of odd-degree vertices in an undirected graph is even

Using the Handshaking Theorem:

∑deg(vi​)=2∣E∣

1. The sum of degrees is always even since it equals $2\mathrm{\mid }E\mathrm{\mid }$.
2. Vertices with odd degrees contribute odd numbers to the sum.
3. For the total sum to remain even, the count of odd-degree vertices must itself be even (odd numbers sum to even only in pairs).

Example: In a graph with 5 vertices:

  Degrees : 3,3,2,2,4,

 Odd-degrees-vertices : v1,v2 (3,3),

Total odd vertices =2(even count).

5.Give an example of a graph which is

i) Eulerian but not Hamiltonian

ii) Hamiltonian but not Eulerian

iii) Both Eulerian and Hamiltonian

iv) Non Eulerian and Non-Hamiltonian

• Eulerian but not Hamiltonian:

  • A graph is Eulerian if it contains a closed trail that visits every edge exactly once. This requires all vertices to have even degrees.
  • Example: A figure-eight graph with no Hamiltonian cycle.

• Hamiltonian but not Eulerian:

  • A graph is Hamiltonian if it contains a cycle that visits every vertex exactly once. Vertices may have odd degrees.
  • Example: A pentagon graph with one diagonal.

• Both Eulerian and Hamiltonian:

  • A graph that satisfies both conditions.
  • Example: A triangle ($C_3$).

• Neither Eulerian nor Hamiltonian:

• Example: A disconnected graph or a graph with isolated vertices.

All Graphs

• 
  
  

6. Prove that the maximum number of edges in a simple graph with 

$n$ vertices is $\frac{n(n-1)}{2}$

A simple graph has no loops or multiple edges. The maximum number of edges occurs in a complete graph:

$$\text{Maximum edges}=\left(\genfrac{}{}{0px}{}{n}{2}\right)=\frac{n(n-1)}{2}$$

Proof:

1. A complete graph connects every pair of $n$ vertices.
2. Total edges = Number of ways to choose 2 vertices from $n$:

$$\left(\genfrac{}{}{0px}{}{n}{2}\right)=\frac{n(n-1)}{2}$$

Example: For $n=\mathrm{4:}$

$$\text{Maximum edges}=\frac{4(4-1)}{2}=6$$

7. Write the adjacency matrix of the given graph

8. Write the incidence matrix of the given graph

9. Write the adjacency matrix of the given graph

10.Explain

i) Complete Graph

ii) Regular Graph

iii) Directed Graph

and give one example

i) Complete Graph:

A simple graph with n vertices is called a complete graph if the degree of each vertex is n-1, that is, one vertex is attached with n-1 edges or the rest of the vertices in the graph. A complete graph is also called Full Graph

ii)Regular Graph:

A simple graph is said to be regular if all vertices of graph G are of equal degree. All complete graphs are regular but vice versa is not possible. A regular graph is a type of undirected graph where every vertex has the same number of edges or neighbors. In other words, if a graph is regular, then every vertex has the same degree

iii)Digraph Graph or Directed Graph :

A graph G = (V, E) with a mapping f such that every edge maps onto some ordered pair of vertices (Vi, Vj) are called a Digraph. It is also called Directed Graph. The ordered pair (Vi, Vj) means an edge between Vi and Vj with an arrow directed from Vi to Vj. Here in the figure: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

ad

UNIT - 3

PART - C 

Prove that the maximum number of edges in a simple graph with $n$ vertices is $\frac{n(n-1)}{2}$.-IMP

2.Prove that a simple graph with $n$ vertices and $k$ components can have at most-IMP

3.Explain the Königsberg Bridge Problem.

4.Explain the Travelling Salesman Problem.

Introduction

The Travelling Salesman Problem (TSP) is regarded as the benchmark problem in the fields of operations research and optimization. It captures the difficulties of decision-making and logistics in the real world, making it a topic of tremendous importance in many different businesses. The Problem is best described as follows: Find the shortest route that stops in each city exactly once, travels the distance between them, and then returns to the beginning city. The TSP's computational complexity has historically sparked the curiosity of mathematicians, computer scientists, and engineers despite its deceptively straightforward explanation.

Historical Background

The Iris mathematician W.R. Hamilton and the British mathematician Thomas Kirkman were in the 1800s. However, the problem did not start to receive much attention until the middle of the 20th century. In order to overcome integer programming difficulties, George Dantzig, Ray Fulkerson, and Selmer Johnson created the idea of linear programming in 1954. This sparked further investigation of the TSP. The invention of computers made it possible for researchers to address more complex cases of the issue, which led to the development of several algorithms and heuristics.

What is the Travelling Salesman Problem?

The Travelling Salesman Problem (TSP) is a well-known optimization problem in both computer science and mathematics. It entails determining the quickest path that makes a specific set of stops precisely once before heading back to the beginning location. In other words, the challenge is to find the route that will allow a traveling salesperson to visit the most places with the least amount of travel time while still returning to the originating city.

Let's think of a collection of n cities as the mathematical representation of the TSP. The objective is to identify a combination of these cities that yields the least feasible distance traveled overall. Typically, a distance matrix represents the distances between the cities, with each entry in the i-th row and j-th column denoting the distance between cities i and j.

Problem Statement

Given:

• A set of $N$ cities.
• The distances (or costs) between each pair of cities.

Objective:

• Find the shortest possible path (or the path with the minimum cost) that starts and ends at the same city and visits every other city exactly once.

Mathematical Formulation

1. Represent the cities as nodes in a graph.
2. The distances between cities are represented as weighted edges.
3. Find a Hamiltonian cycle with the minimum weight.

Example

If there are four cities $A,B,C,D$ and the distances between them are given, the goal is to compute a tour like $A\to B\to C\to D\to \mathrm{A\; with\; the\; least\; total\; distance.}$

Challenges

• NP-Hard Problem: TSP belongs to the class of NP-hard problems, meaning that no efficient algorithm is known to solve it for large $N$ in polynomial time.
• Exponential Complexity: A brute-force approach checks all permutations of cities, leading to $(N-1)!$possibilities for $N$ cities.

Approaches to Solve TSP

1. Exact Algorithms (used for small-scale problems):

   • Brute Force: Check all possible routes and select the shortest one.
   • Dynamic Programming (e.g., Held-Karp Algorithm): Reduces time complexity to $O(N^2\cdot 2^N)$
     
   • Integer Linear Programming: Formulate the problem as a linear program with integer constraints.

2. Approximation Algorithms (used for large-scale problems):

   • Nearest Neighbor: Start at a city and repeatedly visit the nearest unvisited city.
   • Minimum Spanning Tree (MST) Based Heuristics: Use MSTs to construct a tour.
   • Christofides' Algorithm: Guarantees a solution within 1.5 times the optimal for metric TSP.

3. Metaheuristic Algorithms (for near-optimal solutions):

   • Genetic Algorithms.
   • Simulated Annealing.
   • Ant Colony Optimization.

Applications

• Logistics and Supply Chain: Optimize delivery routes.
• Manufacturing: Minimize tool changes on a production line.
• Astronomy: Plan the path of telescopes observing celestial objects.
• Data Networking: Optimize routing in communication networks.

TSP exemplifies the complexity of real-world optimization problems and serves as a benchmark for evaluating optimization techniques.

5.Prove that a simple graph with $n$vertices is connected if it has more than $\frac{(n-1)(n-2)}{\mathrm{<span\; style="color:\; \#b45f06;"><b>2</b></span>}}$

6.Show that the following graphs are isomorphic or not 

7.Show that the following graphs are isomorphic or not. 

UNIT - 4

PART - A 

1. Define Group and Give an Example.

2.Define semigroups and monoids. 

3.Define order of an element

4.Define subgroup and give an example

5.Define cyclic group and give an example.

6.What is Group homomorphism. 

 7. Check whether the function $f(x)=x^2$is a homomorphism or not.

8.Define Kernel of Homomorphism.

9. State Lagrange’s Theorem.

 

10. State Fundamental Theorem of Homomorphism.

UNIT - 4

PART - B 

1. Prove that the identity element in a group is unique.

2.Prove that the inverse of every element is unique.

3.Prove that, intersection of two subgroups is also a

subgroup of a group. 

Let $H_1$ and $H_2$ be subgroups of a group $G$. Define the intersection:

$$H_1\cap H_2=\{x\in G\mid x\in H_1\text{ and }x\in H_2\}\mathrm{.}$$

We aim to show that $H_1\cap H_2$ is a subgroup of $\mathrm{<br>}$.

Subgroup Criteria:

1. Closure: For all $x,y\in H_1\cap H_2$, $x\ast y^{-1}\in H_1\cap H_2$.
2. Identity: The identity element $e$ is in $H_1\cap H_2$.
3. Inverses: For all $x\in H_1\cap H_2$, $x^{-1}\in H_1\cap H_2$.

Proof:

1. Closure:

   • Since $x,y\in H_1\cap H_2$, we know $x,y\in H_1$ and $x,y\in H_2$.
   • Because $H_1$ and $H_2$ are subgroups, $x\ast y^{-1}\in H_{\mathrm{1<span\; class="katex"><span\; aria-hidden="true"\; class="katex-html"><span\; class="base"><span\; class="mord"><span\; class="msupsub"><span\; class="vlist-t\; vlist-t2"><span\; class="vlist-r"><span\; class="vlist-s"></span></span><span\; class="vlist-r"><span\; class="vlist"></span></span></span></span></span></span></span></span> and }}$$x\ast y^{-1}\in H_2$.
   • Hence, $x\ast y^{-1}\in H_1\cap H_2$, proving closure.

2. Identity:

   • The identity element $e\in H_1$ (since $H_1$ is a subgroup).
   • Similarly, $e\in H_{\mathrm{2<span\; class="katex"><span\; aria-hidden="true"\; class="katex-html"><span\; class="base"><span\; class="mord"><span\; class="msupsub"><span\; class="vlist-t\; vlist-t2"><span\; class="vlist-r"><span\; class="vlist-s"></span></span><span\; class="vlist-r"><span\; class="vlist"></span></span></span></span></span></span></span></span> (since }}$$H_2$ is a subgroup).
   • Therefore, $e\in H_1\cap H_2$, proving the identity element exists in the intersection.

3. Inverses:

   • Let $x\in H_1\cap H_2$. Then $x\in H_1$ and $x\in H_2$.
   • Since $H_1$ and $H_2$ are subgroups, $x^{-1}\in H_1$ and $x^{-1}\in H_2$
     
   • Thus, $x^{-1}\in H_1\cap H_2$, proving the existence of inverses.

Therefore, $H_1\cap H_2$ is a subgroup of $G$.

4. Prove that $G=\{1,-1,i,-i\}$  is a group under multiplication.

Let $G=\{1,-1,i,-i\}$ with multiplication as the group operation.

Verification of Group Properties:

1. Closure:

   • The product of any two elements in $G$ is also in $G$. For example:
     • $1\cdot i=i$
       
     • $i\cdot i=-1$
     • $i\cdot -i=-1$
       
     • $-1\cdot -1=1$.
   • Thus, $G$ is closed under multiplication.

2. Associativity:

   • Multiplication of complex numbers is associative. For all $x,y,z\in G$:$$(x\cdot y)\cdot z=x\cdot (y\cdot z)\mathrm{.}$$

3. Identity:

   • The identity element under multiplication is $1$, since:$$1\cdot x=x\cdot 1=x\text{for all }x\in G\mathrm{.}$$
     

4. Inverses:

   • Each element in $G$ has an inverse:
     • $1^{-1}=1$
       
     • $(-1{)}^{-1}=-1$
       
     • $i^{-1}=-i$
       
     • $(-i{)}^{-1}=i$
       

Since $G$ satisfies all group properties, $G$ is a group under multiplication.

5. Determine whether 

$H_1=\{0,5,10\}$and $H_2=\{0,4,8,12\}$ are subgroups of ${\mathbb{Z}}_{15}$ under addition.

6. Let $G=\{1,-1,i,-i\}$.

(i) What are the generators of $G$?
(ii) Find the order of every element in G?

7. If $f:G\to G^{\mathrm{\prime <span\; style="font-size:\; medium;"> </span><span\; style="font-size:\; medium;">is\; a\; group\; homomorphism,\; and</span><span\; style="font-size:\; medium;"> </span>}}$$H$ is a subgroup of $G$, then $f(H)$ is a subgroup of $G^{\mathrm{\prime }}$

8. Prove that the kernel of a homomorphism $f$ from $G$ to $G^{\mathrm{\prime }}$ is a subgroup of G

9. Define Left and Right Coset with an Example.

10. Prove that every cyclic group is abelian

UNIT - 4

PART - C 

1.Prove that every subgroup of a cyclic group is cyclic 

2(i) if f: G -> G' is a group homomorphism ,H is a subgroup of  G, then f(H) is a subgroup of G'

2)ii) Prove that, intersection of two subgroups is also a subgroup

of a group

3.Prove that $(\mathbb{R}\setminus \{1\},\ast )$ forms an abelian group where the operation $\ast$ is defined as, a∗b=a+b−1,

for any $\mathrm{ <br>}$.

4.State and Prove the fundamental theorem of group  homomorphism

5.State and prove the Lagrange’s theorem 

7.imp

 

UNIT-5

PART-A

1. Define Poset and give an example.

• Definition: A Poset (Partially Ordered Set) is a set $P$ equipped with a binary relation $\le$ that is reflexive, antisymmetric, and transitive.

• Example: $(\mathbb{N},\le )$, where $\mathbb{N}$ is the set of natural numbers and $\le$ is the usual "less than or equal to" relation.

2. Define LUB and GLB.

• LUB (Least Upper Bound): The smallest element in a poset that is greater than or equal to all elements of a subset $S$. Also called the supremum

• GLB (Greatest Lower Bound): The largest element in a poset that is less than or equal to all elements of a subset $S$. Also called the infimum.

3. Define a Lattice and give an example.

• Definition: A Lattice is a poset $(L,\le )$ where every pair of elements $a,b\in L$ has:
  1. A least upper bound (join, denoted $a\vee b$).
  2. A greatest lower bound (meet, denoted $a\wedge b$).
• Example: The set of integers $\mathbb{Z}$ under the divisibility relation forms a lattice.

4. State the four properties of a Lattice.

1. Commutativity: $a\vee b=b\vee a$ and $a\wedge b=b\wedge a$
   
2. Associativity: $a\vee (b\vee c)=(a\vee b)\vee c$ and $a\wedge (b\wedge c)=(a\wedge b)\wedge c$
   
3. Absorption: $a\vee (a\wedge b)=a$ and $a\wedge (a\vee b)=a$
   
4. Idempotence: $a\vee a=a$ and $a\wedge a=a$
   

5. State the principle of duality with respect to Lattices.

• Principle of Duality: If a statement about lattices is true, its dual statement (obtained by interchanging $\vee$ with $\wedge$, and $\le$ with $\ge$) is also true.

6. Define Sublattice.

• Definition: A sublattice of a lattice $L$is a subset $L^{\mathrm{\prime }}\subseteq L$ that is itself a lattice with the same meet ($\wedge$) and join ($\vee$) operations as in $L$.

7. Define Boolean Algebra.

• Definition: A Boolean algebra is a lattice $(B,\vee ,\wedge {,}^{\mathrm{\prime }},0,1)$where:
1. $\vee$ and $\wedge$ are commutative, associative, and distributive.
2. There exists a complement $a^{\mathrm{\prime }}$ for every element $a\in B$ such that:
   • $a\vee a^{\mathrm{\prime }}=1$,
   • $a\wedge a^{\mathrm{\prime }}=0$.
3. $0$ is the identity for $\vee$, and $1$ is the identity for $\wedge$
   

8. Write any two properties of Boolean Algebra.

1. Distributive Law: $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
   
2. Complement Law: $a\vee a^{\mathrm{\prime }}=1$ and $a\wedge a^{\mathrm{\prime }}=0\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}\mathrm{<br>}$

9. In a Boolean algebra $B$, prove that $0^{\mathrm{\prime }}=1$ and $1^{\mathrm{\prime }}=0$.

• Proof:
  • By definition, $0$ and $1$ are the identity elements for $\wedge$ and $\vee$ respectively.
  • For $0^{}$:$$0\vee 0^{\mathrm{\prime }}=1\text{and}0\wedge 0^{\mathrm{\prime }}=0.$$ Thus, $0^{\mathrm{\prime }}=1$.
  • For ${\mathrm{1\prime }}^{}$:$$1\vee 1^{\mathrm{\prime }}=1\text{and}1\wedge 1^{\mathrm{\prime }}=0.$$ Thus, $1^{\mathrm{\prime }}=0$
    

10. Prove that:

(i) $a+a=a$:

• By the idempotent law of Boolean algebra:$$a\vee a=a\mathrm{.}$$
  

(ii) $a\cdot a=a$ (for all $a\in B$):

• By the idempotent law of Boolean algebra:=  a∧a=a.

UNIT-5

PART-B

1. State and prove the double complement law.

2. State and prove the absorption law.

3. Prove that $a+1=1$ and $a\cdot 0=0$ for all $\mathrm{<b><span\; style="color:\; \#38761d;">a</span></b>}<b><span\; style="color:\; \#38761d;">\in </span></b>\mathrm{<b><span\; style="color:\; \#38761d;">B</span></b>}\mathrm{<b><span\; style="color:\; \#38761d;"><br></span></b>}$

4. Prove that $a\cdot (a+b)=a$ and $a+(a\cdot b)=a$ for all $a,b\in B$

5.

6. Draw the Hasse diagram of the poset $\{D_{100},\mathrm{\mid }\}$,Hence, find the LUB and GLB of $\{10,20\}$ and $\{5,10,20,25\}$.

7. Draw the Hasse diagram for the posets $\{A,\mathrm{\mid }\}$and $\{B,\mathrm{\mid }\}$, where $A=\{2,3,6,12,24,36\}$and $B=\{1,2,4,6,8,16\}$.

8. Draw the Hasse diagram of the lattice 

${p(s),⊆}, where s={a,b,c}.$

10.Prove that any chain is a distributive lattice

In a chain, all elements are comparable.

This ensures that distributive laws always hold:

Thus, every chain is distributive.

UNIT-5

PART-C

1.State and prove Isotonicity property of Lattice. 

2.State and prove De Morgan’s law in a complemented

distributive Lattice

3.In a Boolean algebra, prove that the following statements

are equivalent 

(i) 

$b+a=1$
(ii) $a+a^{\mathrm{\prime }}\cdot b=b$
(iii) $a=1$
(iv) $a\cdot b^{\mathrm{\prime }}=0$

4.State and prove De Morgan’s law in Boolean algebra  (imp)

5.Draw the Hasse diagram of the poset  (imp)

$\{D_{30},\mathrm{\mid }\}$, hence find

1. The LUB (Least Upper Bound) of $\{10,15\}$
   
2. The GLB (Greatest Lower Bound) of $\{10,15\}$.

6.State and prove distributive inequality of Lattice  (imp)