Here, We provide **Discrete Mathematics GTU Paper Solution Winter 202**2. Read the Full **DM** **GT&C GTU paper solution** given below.

**Discrete Mathematics** **GTU Old Paper Winter 2022 [Marks : 70] : **Click Here

**(a)** A committee 5 persons, is to be formed from 6 men and 4 women. In how many ways this can be done when (i) at least 2 women are included, (ii) at most 2 women are included.

(i) To find the number of ways to form a committee with at least 2 women, we can use the principle of inclusion-exclusion.

The total number of ways to form a committee of 5 people from 10 is: 10C5 = 252

Now, we need to subtract the number of committees with 0 or 1 woman: 6C5 * 4C0 + 6C4 * 4C1 = 6 + 360 = 366

But we’ve double-counted the committees with 0 women and 0 men, so we need to add those back in: 6C0 * 4C5 = 0 Total = 252 – 366 + 0 = 114

Therefore, there are 114 ways to form a committee with at least 2 women.

(ii) To find the number of ways to form a committee with at most 2 women, we can count the number of committees with 0, 1, or 2 women, and add them up.

The number of committees with 0 women is: 6C5 * 4C0 = 6

The number of committees with 1 woman is: 6C4 * 4C1 = 360

The number of committees with 2 women is: 6C3 * 4C2 = 180

Total = 6 + 360 + 180 = 546

Therefore, there are 546 ways to form a committee with at most 2 women.

**(b) **If A ={4,5,7,8,10} , B={4,5,9} and C={1,4,6,9} , then verify that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

To verify the given equality, we need to show that each set is a subset of the other:

First, we will show that A ∪ (B ∩ C) is a subset of (A ∪ B) ∩ (A ∪ C):

Let x be an arbitrary element of A ∪ (B ∩ C). Then, x is either an element of A or an element of both B and C.

Case 1: x is an element of A In this case, x is an element of (A ∪ B) and (A ∪ C), so it is also an element of (A ∪ B) ∩ (A ∪ C).

Case 2: x is an element of both B and C In this case, x is an element of B ∩ C, and therefore it is also an element of A ∪ (B ∩ C). Since x is an element of both B and C, it is also an element of both A ∪ B and A ∪ C, and thus it is also an element of their intersection (A ∪ B) ∩ (A ∪ C).

Therefore, we have shown that A ∪ (B ∩ C) is a subset of (A ∪ B) ∩ (A ∪ C).

Second, we will show that (A ∪ B) ∩ (A ∪ C) is a subset of A ∪ (B ∩ C):

Let y be an arbitrary element of (A ∪ B) ∩ (A ∪ C). Then, y is an element of both A ∪ B and A ∪ C.

Case 1: y is an element of A In this case, y is an element of A ∪ (B ∩ C).

Case 2: y is an element of both B and C In this case, y is an element of (B ∩ C). Therefore, y is also an element of A ∪ (B ∩ C).

Therefore, we have shown that (A ∪ B) ∩ (A ∪ C) is a subset of A ∪ (B ∩ C).

Since we have shown that each set is a subset of the other, we can conclude that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Hence, the given equality is verified.

**(c) Define Functionally complete set of connectives, Principal Disjunctive Normal Form (PDNF). Obtain PDNF for the expression ~(( p ˄ q ) ˅ ( ̴ p ˄ q ) ˅ ( q ˄ r ))**

Functionally complete set of connectives: A set of logical connectives is called functionally complete if every logical function can be expressed using only connectives from that set. The connectives {not, and, or} form a functionally complete set.

Principal Disjunctive Normal Form (PDNF): A logical expression in disjunctive normal form (DNF) is an expression that is a disjunction (OR) of one or more conjunctions (ANDs), where each conjunction is a combination of literals. If the literals are the propositional variables, then it is said to be in principal disjunctive normal form (PDNF).

To obtain PDNF for the expression ~(( p ˄ q ) ˅ ( ̴ p ˄ q ) ˅ ( q ˄ r )):

Step 1: Apply De Morgan’s law to the first term: ~(p ˄ q) = ~p ˅ ~q

Step 2: Apply De Morgan’s law to the second term: ~( ̴ p ˄ q ) = p ˅ ~q

Step 3: The third term is already in the form of q ˄ r.

So, the given expression becomes: (~p ˅ ~q) ˅ (p ˅ ~q) ˅ (q ˄ r)

Step 4: Use distributive law to simplify the expression: ((~p ˅ ~q) ˅ p ˅ q) ˄ ((~p ˅ ~q) ˅ r)

Step 5: The expression is now in PDNF: (~p ˅ ~q ˅ p ˅ q ˅ r)

Therefore, the principal disjunctive normal form (PDNF) for the expression ~(( p ˄ q ) ˅ ( ̴ p ˄ q ) ˅ ( q ˄ r )) is (~p ˅ ~q ˅ p ˅ q ˅ r).

**(a)** Define Partial Order Relation. Illustrate with an example.

A partial order relation is a binary relation that is reflexive, antisymmetric, and transitive. In other words, it is a relation that can be used to compare elements of a set, such that each element is related to itself, and if element A is related to element B, and element B is related to element C, then element A is related to element C.

More formally, let R be a binary relation on a set A. Then R is a partial order relation if it satisfies the following three properties:

- Reflexivity: for all a ∈ A, aRa.
- Antisymmetry: for all a, b ∈ A, if aRb and bRa, then a = b.
- Transitivity: for all a, b, c ∈ A, if aRb and bRc, then aRc.

An example of a partial order relation is the “less than or equal to” relation on the set of natural numbers. Let N be the set of natural numbers. Then the relation “less than or equal to”, denoted by ≤, is a partial order relation on N, because it satisfies the three properties of a partial order relation:

- Reflexivity: for all n ∈ N, n ≤ n.
- Antisymmetry: for all m, n ∈ N, if m ≤ n and n ≤ m, then m = n.
- Transitivity: for all k, m, n ∈ N, if k ≤ m and m ≤ n, then k ≤ n.

For example, 2 ≤ 2, 2 ≤ 3, and 2 ≤ 4. However, 3 is not less than or equal to 2, so 3 ≤ 2 is not true. Similarly, if 2 ≤ 3 and 3 ≤ 4, then 2 ≤ 4.

**(b) Define one – one function. Show that the functionf: R -> R , f (x) = 3x – 7 is one – one and onto both. Also find its inverse. **

A one-to-one function, also known as an injective function, is a function where each element of the domain maps to a unique element of the range. In other words, if f(x1) = f(x2), then x1 = x2.

To show that the function f(x) = 3x – 7 is one-to-one, we need to show that if f(x1) = f(x2), then x1 = x2. So, let’s assume that f(x1) = f(x2):

f(x1) = 3×1 – 7

f(x2) = 3×2 – 7

If f(x1) = f(x2), then:

3×1 – 7 = 3×2 – 7

3×1 = 3×2

x1 = x2

Therefore, f(x) = 3x – 7 is a one-to-one function.

To show that f(x) is onto, also known as a surjective function, we need to show that for every y in the range of f(x), there exists an x in the domain of f(x) such that f(x) = y.

Let y be any element in the range of f(x). Then y = 3x – 7 for some x in the domain of f(x). We can solve for x to get:

x = (y + 7)/3

Therefore, for any y in the range of f(x), there exists an x in the domain of f(x) such that f(x) = y. This shows that f(x) is onto.

To find the inverse of f(x) = 3x – 7, we can follow these steps:

Step 1: Replace f(x) with y.

y = 3x – 7

Step 2: Solve for x in terms of y.

y + 7 = 3x

x = (y + 7)/3

Step 3: Replace x with f^-1(x).

f^-1(x) = (x + 7)/3

Therefore, the inverse of f(x) = 3x – 7 is f^-1(x) = (x + 7)/3.

**(c) **Solve the recurrence relation aₙ₊₂-5aₙ₊₁+6aₙ = 2with initial condition a₀ = 1 and a₁ = -1 using method of undetermined coefficients.

To solve the recurrence relation aₙ₊₂ – 5aₙ₊₁ + 6aₙ = 2 with initial conditions a₀ = 1 and a₁ = -1 using the method of undetermined coefficients, we first need to find the homogeneous solution of the recurrence relation.

Homogeneous solution: The characteristic equation is:

r² – 5r + 6 = 0

Solving this equation, we get:

r₁ = 2 and r₂ = 3

Therefore, the homogeneous solution is:

aₙ = c₁(2)ⁿ + c₂(3)ⁿ

where c₁ and c₂ are constants that depend on the initial conditions.

Using the initial conditions a₀ = 1 and a₁ = -1, we can find c₁ and c₂ as follows:

a₀ = 1 = c₁ + c₂

a₁ = -1 = 2c₁ + 3c₂

Solving these equations, we get:

c₁ = -4 and c₂ = 5

So, the homogeneous solution is:

aₙ = -4(2)ⁿ + 5(3)ⁿ

Particular solution: To find the particular solution, we assume that it has the form:

aₙ = A

where A is a constant. Substituting this into the recurrence relation, we get:

A – 5A + 6A = 2

Solving for A, we get:

A = -2

Therefore, the particular solution is:

aₙ = -2

General solution: The general solution is the sum of the homogeneous and particular solutions:

aₙ = -4(2)ⁿ + 5(3)ⁿ – 2

Using the initial conditions a₀ = 1 and a₁ = -1, we can find the values of the constants:

a₀ = 1 = -4 + 5 – 2

a₁ = -1 = -8 + 15 – 2

Therefore, the solution to the recurrence relation aₙ₊₂ – 5aₙ₊₁ + 6aₙ = 2 with initial condition a₀ = 1 and a₁ = -1 is:

aₙ = -4(2)ⁿ + 5(3)ⁿ – 2

**(c) Use generating function to solve a recurrence relation** **aₙ = 3aₙ₋₁ + 2 with** **a₀ = 1.**

To solve the recurrence relation aₙ = 3aₙ₋₁ + 2 with a₀ = 1 using generating functions, we define the generating function A(x) as:

A(x) = a₀ + a₁x + a₂x² + …

Multiplying both sides of the recurrence relation by xⁿ and summing over all n, we get:

∑ aₙ xⁿ = ∑ 3aₙ₋₁ xⁿ + ∑ 2xⁿ

Shifting the index of the first sum on the right-hand side, we get:

∑ aₙ xⁿ = x(∑ 3aₙ₋₂ xⁿ⁻¹) + ∑ 2xⁿ

Multiplying both sides by x and subtracting the two sums on the right-hand side, we get:

A(x) – a₀ = 3x(A(x) – a₀) + 2/(1-x)

Solving for A(x), we get:

A(x) = (2/(1-x) + a₀) / (1-3x)

Substituting a₀ = 1, we get:

A(x) = 1 / (1-3x) + 2 / (1-x)

Using partial fractions, we can rewrite this as:

A(x) = (-1/2) / (1-3x) + (3/2) / (1-x)

Using the formula for the geometric series, we know that:

1 / (1-ax) = ∑ aⁿ xⁿ

Substituting a = 3x and a = x, respectively, we get:

A(x) = (-1/2) ∑ (3x)ⁿ + (3/2) ∑ xⁿ

Simplifying, we get:

A(x) = (-1/2) ∑ 3ⁿ xⁿ + (3/2) ∑ xⁿ

Therefore, the generating function A(x) can be written as:

A(x) = (-1/2) (1 / (1-3x)) + (3/2) (1 / (1-x))

Using the formula for the geometric series again, we get:

A(x) = (-1/2) ∑ 3ⁿ xⁿ + (3/2) ∑ xⁿ

Comparing this with the definition of A(x), we can see that:

aₙ = (-1/2)3ⁿ + (3/2)

Therefore, the solution to the recurrence relation aₙ = 3aₙ₋₁ + 2 with a₀ = 1 is:

aₙ = (-1/2)3ⁿ + (3/2)

** (a) Define Partition of a Set. LetA = {1,2,3,4,5} and R ={(1,2) , (1,1) , (2,1) , (2,2) , (3,3) , (4,4) , (5,5**)}

be an equivalence relation on A.

be an equivalence relation on A.

**Determine the partition for R⁻¹,if it an equivalence relation.**

A partition of a set A is a collection of non-empty subsets of A such that every element of A belongs to exactly one subset in the collection.

In this case, the equivalence relation R on A = {1, 2, 3, 4, 5} is given by:

R = {(1, 2), (1, 1), (2, 1), (2, 2), (3, 3), (4, 4), (5, 5)}

To find the partition of R⁻¹, we need to first find R⁻¹:

R⁻¹ = {(2, 1), (1, 1), (1, 2), (2, 2), (3, 3), (4, 4), (5, 5)}

Note that R⁻¹ is also an equivalence relation, since it is the inverse relation of an equivalence relation. To find the partition of R⁻¹, we can group together the elements that are related by R⁻¹.

Starting with the element 1, we can see that it is related to both 1 and 2 under R⁻¹, so we group them together:

{1, 2}

Next, we move on to 3, which is only related to itself under R⁻¹, so we put it in its own subset:

{3}

We continue with the remaining elements, which are only related to themselves under R⁻¹:

{4}

{5}

Therefore, the partition of R⁻¹ is:

{{1, 2}, {3}, {4}, {5}}

Note that this is a valid partition of A, since each element belongs to exactly one subset in the collection.

** (b) Draw Hasse Diagram for the lattice** (S₃₀, D)

**S₃₀**

**where**

is the set of divisors of 30 and D is the relation divides.is the set of divisors of 30 and D is the relation divides.

To draw the Hasse diagram for the lattice (S₃₀, D), we start by listing out all the divisors of 30:

S₃₀ = {1, 2, 3, 5, 6, 10, 15, 30}

Next, we draw a node for each element in S₃₀ and draw a line between two nodes if one of them divides the other. We also draw the nodes in such a way that higher nodes are drawn higher up on the page. The resulting Hasse diagram is shown below:

```
30
/ \
15 10
/ \ / \
5 3 6 2
| |
1 1
```

In this diagram, the element 30 is at the top, since it is the greatest element in the lattice. The element 1 is at the bottom, since it is the least element. The diagram also shows that each element is connected to its divisors, and that there are no other connections between elements.

**(c) Show that the set S of all matrices of the form[ a b][-b a] where a b ∈**

**R ,**

**is a field with respect to matrix addition and matrix multiplication.**To show that the set S of all matrices of the form

```
[ a b]
[-b a]
```

where a, b ∈ R is a field with respect to matrix addition and matrix multiplication, we need to prove the following properties:

- S is closed under matrix addition: For any two matrices

```
[ a₁ b₁] [ a₂ b₂]
[-b₁ a₁] [-b₂ a₂]
```

in S, their sum is

```
[ a₁ + a₂ b₁ + b₂]
[-(b₁ + b₂) a₁ + a₂]
```

which is also a matrix of the required form. Therefore, S is closed under matrix addition.

- S is an abelian group under matrix addition: This is clear from the definition of matrix addition, since it is commutative, associative, and has the zero matrix as an identity element. Moreover, every matrix in S has an additive inverse in S, given by

```
[ -a -b]
[ b -a]
```

- S is closed under matrix multiplication: For any two matrices

```
[ a₁ b₁] [ a₂ b₂]
[-b₁ a₁] [-b₂ a₂]
```

in S, their product is

```
[ a₁a₂ - b₁b₂ a₁b₂ + b₁a₂]
[-a₁b₂ - b₁a₂ a₁a₂ - b₁b₂]
```

which is also a matrix of the required form. Therefore, S is closed under matrix multiplication.

- Matrix multiplication is associative: This is true for any matrices, including those in S.
- Matrix multiplication is distributive over matrix addition: For any matrices

```
[ a₁ b₁] [ a₂ b₂] [ a₃ b₃]
[-b₁ a₁] [-b₂ a₂] [-b₃ a₃]
```

in S, we have

```
[ a₁ b₁] [ a₂ b₂] [ a₃ b₃] [ a₁a₂ - b₁b₂ a₁b₂ + b₁a₂] [ a₁a₂a₃ - b₁b₂a₃ - a₁b₂b₃ - b₁a₂b₃ a₁a₂b₃ - b₁b₂b₃ + a₁b₂a₃ + b₁a₂a₃]
[-b₁ a₁] [-b₂ a₂] [-b₃ a₃] = [-a₁b₂ - b₁a₂ -a₁b₃ - b₁a₃ + a₂b₁ + b₂a₁ -a₁a₂ - b₁b₂ - a₁a₃ + b₁b₃ + a₂a₁ + b₂b₁]
```

and

`[ a₁ b₁] [ a₃ b₃] [ a₂ b₂] [ a₁a₃ - b₁b₃ a₁b₃ + b₁a₃] [ a₁a₃a₂ - b₁b₃a₂ - a₁b₃b₂ - b₁a₃b₂ a₁a₃b₂ - b₁b₃b₂ + a₁b₃`

]

OR

**(a)** Define Semi Group, Monoid. Give an example of an algebraic structure

which is semi group but not monoid.

A semigroup is an algebraic structure consisting of a set and an associative binary operation defined on it. Formally, a semigroup is denoted as (S, ∗), where S is a non-empty set and ∗ is an associative binary operation on S.

A monoid is a semigroup with an identity element. Formally, a monoid is denoted as (S, ∗), where S is a non-empty set, ∗ is an associative binary operation on S, and there exists an identity element e ∈ S such that for any element a ∈ S, e ∗ a = a ∗ e = a.

An example of an algebraic structure that is a semigroup but not a monoid is the set of all positive integers under addition. Addition is an associative operation, but there is no identity element in this set.

**(b) Consider the a relation R defined on A ={1,2,3}, whose matrixrepresentation is given below. Determine its inverse**

**R⁻¹**

and complement R’.

[1 0 0]

M(R) = [1 1 1]

[0 0 1]

and complement R’.

[1 0 0]

M(R) = [1 1 1]

[0 0 1]

To determine the inverse of R, we need to find the matrix M(R⁻¹) such that M(R) · M(R⁻¹) = I, where I is the identity matrix. That is:

[M(R) · M(R⁻¹)]ᵀ = M(R⁻¹) · M(R)ᵀ = I

Using the matrix M(R), we can write the equations:

M(R⁻¹)[1 1 0] = [1 0 0] M(R⁻¹)[0 1 0] = [0 1 0] M(R⁻¹)[0 1 1] = [0 1 1]

Solving these equations, we get:

M(R⁻¹) = [1 0 0] [1 1 0] [0 0 1]

To find the complement R’, we need to find the matrix M(R’) such that M(R) + M(R’) = J, where J is the matrix of all 1’s. That is:

M(R’) = J – M(R)

Using the matrix M(R), we get:

M(R’) = [0 1 1] [0 0 0] [1 1 0]

**(c) Define free variable and bound variable.Rewrite the following argument using quantifiers, variables and predicatesymbols. Prove the validity of the argument.**

“All healthy people eat an apple a day.

Ram does not eat apple a day.

Ram is not a healthy person.”“All healthy people eat an apple a day.

Ram does not eat apple a day.

Ram is not a healthy person.”

A free variable is a variable in a logical formula that is not bound by a quantifier. A bound variable is a variable in a logical formula that is bound by a quantifier.

Using quantifiers, variables, and predicate symbols, we can rewrite the argument as follows:

Let H(x) denote “x is a healthy person.” Let E(x) denote “x eats an apple a day.” Let R denote “Ram.”

∀x (H(x) → E(x)) (All healthy people eat an apple a day) ¬E(R) (Ram does not eat an apple a day) ∴ ¬H(R) (Ram is not a healthy person)

To prove the validity of the argument, we need to show that if the premises are true, then the conclusion must be true. We can do this using a proof by contradiction:

Assume that the premises are true, but the conclusion is false, i.e., assume that Ram is a healthy person.

Then, by the first premise, Ram eats an apple a day, which contradicts the second premise.

Therefore, the conclusion must be true, and Ram is not a healthy person.

**(a)** Define Abelian group and prove that the set {0,1,2,3,4} is a finite abelian group under addition modulo 5 as binary operation.

An Abelian group is a set G together with a binary operation + such that the following conditions are satisfied:

- Closure: For all a, b in G, a + b is in G.
- Associativity: For all a, b, and c in G, (a + b) + c = a + (b + c).
- Identity: There exists an element e in G such that for all a in G, a + e = e + a = a.
- Inverse: For every element a in G, there exists an element b in G such that a + b = b + a = e.
- Commutativity: For all a and b in G, a + b = b + a.

Now, let’s prove that the set {0,1,2,3,4} is a finite Abelian group under addition modulo 5.

- Closure: For any two elements a and b in {0,1,2,3,4}, a + b is also in {0,1,2,3,4}. This is because if we add any two numbers in {0,1,2,3,4} and take the result modulo 5, the result will still be in {0,1,2,3,4}.
- Associativity: Addition modulo 5 is associative, meaning that (a + b) + c = a + (b + c) for all a, b, and c in {0,1,2,3,4}.
- Identity: The element 0 is the identity element of the group, since for any element a in {0,1,2,3,4}, a + 0 = 0 + a = a.
- Inverse: For every element a in {0,1,2,3,4}, there exists an element b in {0,1,2,3,4} such that a + b = b + a = 0. For example, 1 + 4 = 4 + 1 = 0.
- Commutativity: Addition modulo 5 is commutative, meaning that a + b = b + a for all a and b in {0,1,2,3,4}.

Therefore, the set {0,1,2,3,4} under addition modulo 5 is a finite Abelian group.

** (b) Define even permutation. Show that the permutation**)

(1 2 3 4 5 6) (1 2 3 4 5 6)

(5 6 2 4 1 3

**is odd and****)**

**(6 3 4 5 2 1**

**is even.**An even permutation is a permutation that can be obtained by a finite sequence of swaps of two elements starting from the identity permutation. On the other hand, an odd permutation is a permutation that cannot be obtained by an even number of swaps starting from the identity permutation.

Let’s first count the number of inversions for the permutation (1 2 3 4 5 6) (5 6 2 4 1 3). An inversion is a pair of elements (a,b) such that a appears before b in the permutation, but a > b. We can count the inversions by comparing each element with the ones that come after it.

(1 2 3 4 5 6)

(5 6 2 4 1 3)

- 5 has no inversions
- 6 has no inversions
- 2 has two inversions: (2,1) and (2,1)
- 4 has no inversions
- 1 has four inversions: (1,2), (1,3), (1,4), (1,5)
- 3 has three inversions: (3,2), (3,1), (3,2)

Therefore, the total number of inversions is 2 + 4 + 3 = 9, which is odd. Hence, the permutation (1 2 3 4 5 6) (5 6 2 4 1 3) is odd.

Now let’s count the number of inversions for the permutation (6 3 4 5 2 1).

(6 3 4 5 2 1)

- 6 has no inversions
- 3 has one inversion: (3,2)
- 4 has one inversion: (4,2)
- 5 has two inversions: (5,2), (5,3)
- 2 has no inversions
- 1 has three inversions: (1,2), (1,3), (1,4)

Therefore, the total number of inversions is 1 + 1 + 2 + 3 = 7, which is odd. Hence, the permutation (6 3 4 5 2 1) is even.

**(c) **Define Principal Ideal. Find all the principal Ideal of the ring

**[{0,1,2,3,4,5},+₆,x₆]**.

To find all the principal ideals of the ring [{0,1,2,3,4,5},+₆,x₆], we need to find all the possible ideals generated by a single element of the ring.

Let a be an element of the ring [{0,1,2,3,4,5},+₆,x₆]. Then the principal ideal generated by a is the set

{ra | r ∈ [{0,1,2,3,4,5},+₆]}

where ra denotes the product of r and a under multiplication x₆.

For example, let a = 3. Then the principal ideal generated by a is

{0, 3, 6, 9, 12, 15}

which can be simplified as

{0, 3, 0, 3, 0, 3} (mod 6)

Similarly, we can find the principal ideals generated by all other elements of the ring:

{0} (generated by 0) {0, 1, 2, 3, 4, 5} (generated by 1) {0, 2, 4} (generated by 2) {0, 3} (generated by 3) {0, 4, 2} (generated by 4) {0, 5, 4, 3, 2, 1} (generated by 5)

Therefore, the principal ideals of the ring [{0,1,2,3,4,5},+₆,x₆] are

{0}, {0, 1, 2, 3, 4, 5}, {0, 2, 4}, {0, 3}, {0, 4, 2}, {0, 5, 4, 3, 2, 1}.

OR

**(a)** Define cut vertex. List out all the cut vertices of the graph given in Figure 1.

A cut vertex is a vertex of a graph whose removal would disconnect the graph. In other words, if we remove a cut vertex from a graph, the graph would become disconnected.

To find the cut vertices of the given graph, we can use the following algorithm:

- For each vertex v in the graph, remove v and check if the resulting graph is disconnected.
- If the graph is disconnected, then v is a cut vertex.

Using this algorithm, we can see that the cut vertices of the given graph in Figure 1 are:

- Vertex 1
- Vertex 3
- Vertex 5

**(b) Define adjacency matrix and path matrix of a graph. Find out adjacencymatrix for the graph given in Figure 1. **

The adjacency matrix of a graph is a square matrix that represents the connections between vertices in a graph. The entry in row i and column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

The path matrix of a graph is another square matrix that represents the existence of paths between vertices in a graph. The entry in row i and column j is 1 if there is a path from vertex i to vertex j, and 0 otherwise.

For the graph given in Figure 1, the adjacency matrix can be represented as:

```
| 1 2 3 4 5
--|---------
1 | 0 1 1 0 0
2 | 1 0 1 1 1
3 | 1 1 0 1 0
4 | 0 1 1 0 1
5 | 0 1 0 1 0
```

The path matrix can be obtained by raising the adjacency matrix to the power of 2:

```
| 1 2 3 4 5
--|---------
1 | 0 1 1 1 1
2 | 1 0 1 1 1
3 | 1 1 0 1 1
4 | 1 1 1 0 1
5 | 1 1 1 1 0
```

**(c) Define the terms: Simple Graph, Multi – Graph, Weighted Graph, Degreeof a vertex, in degree and out degree of a vertex. Illustrate each with anexample. **

- Simple Graph: A simple graph is a graph that does not have multiple edges or self-loops. In other words, it is a graph where only one edge can exist between any two vertices, and a vertex cannot have an edge connecting it to itself. Example: The graph below is a simple graph.

```
A --- B
| |
C --- D
```

- Multi-Graph: A multi-graph is a graph that can have multiple edges between the same pair of vertices. Self-loops are allowed in a multi-graph. Example: The graph below is a multi-graph.

```
A --- B
| |
C --- D
| / |
E ----F
```

- Weighted Graph: A weighted graph is a graph where each edge has a weight or cost associated with it. Example: The graph below is a weighted graph.

```
4
A --- B
2/ | /|3
/ | / |
C | / |
\ | / |1
1\ |/ |/
D --- E
2
```

- Degree of a vertex: The degree of a vertex in a graph is the number of edges that are incident to the vertex. Example: In the simple graph below, vertex A has degree 2.

```
A --- B
| |
C --- D
```

- In-degree and Out-degree of a vertex: In a directed graph, a vertex has an in-degree and an out-degree. The in-degree of a vertex is the number of edges that are incoming to the vertex, while the out-degree of a vertex is the number of edges that are outgoing from the vertex. Example: In the directed graph below, vertex A has an in-degree of 2 and an out-degree of 1.

```
A --> B
| |
v v
C <-- D
```

OR

**(a)** State Lagrange’s theorem and find out all possible subgroups of group

**[{1,-1,i,-i},x]. **

Lagrange’s theorem states that for any finite group G and any subgroup H of G, the order of H divides the order of G.

In the group [{1,-1,i,-i},x], there are several subgroups:

- {1}: This is the trivial subgroup, consisting only of the identity element.
- [{1,-1},x]: This subgroup consists of the identity element and the two elements -1 and 1.
- [{1,-1,i,-i},x]: This is the full group, consisting of all four elements.
- [{1,-1},x], [{1,i},x], [{1,-i},x], [{1,i,-1,-i},x]: These are the four subgroups of order 2, each consisting of the identity element and one other element.

Note that Lagrange’s theorem applies to each of these subgroups, since each subgroup has an order that divides the order of the full group [{1,-1,i,-i},x], which is 4.

**(b) Define Eulerian graph, Planar Graph.Justify whether the graph given in Figure 1 is Planer or not using Euler’sformula. **

Euler’s formula states that for a planar, connected graph with no loops or multiple edges, the number of vertices plus the number of faces minus the number of edges is equal to 2.

In the given graph in Figure 1, we have 7 vertices, 9 edges, and 4 faces (the outer region and the 3 inner regions). Using Euler’s formula, we have:

7 + 4 – 9 = 2

Therefore, the graph is planar as it satisfies Euler’s formula.

**(c) Define Binary tree, Spanning tree, Minimal Spanning tree, Find theminimal spanning tree for the weighted graph given in Figure 2. **

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A spanning tree of a connected, undirected graph is a subgraph that is a tree which includes all the vertices of the graph. A minimal spanning tree of a weighted, connected, undirected graph is a spanning tree with the smallest possible sum of edge weights.

To find the minimal spanning tree of the weighted graph given in Figure 2, we can use Kruskal’s algorithm:

- Sort the edges by weight in ascending order.
- Initialize an empty graph with the same vertices as the original graph.
- For each edge in the sorted list: a. If the edge connects two different components in the current graph, add the edge to the graph. b. Otherwise, discard the edge.
- Repeat step 3 until all vertices are in the same connected component.

The resulting minimal spanning tree for the given graph is shown below:

```
3 1
A-----B-------C
| / \ |
4| 6/ \5 |2
| / \ |
D--------E--F
7 8
```

This tree has a total weight of 13, which is the smallest possible sum of edge weights for any spanning tree of the graph.

OR

**(a)** Define Cyclic group, Normal subgroup. Illustrate with an example.

A cyclic group is a group generated by a single element. That is, a group G is cyclic if there exists an element a in G such that every element of G can be written as a power of a.

For example, the group of integers under addition is cyclic, generated by the element 1. That is, every integer can be written as a power of 1. Similarly, the group of nth roots of unity under multiplication is cyclic, generated by the element e^(2πi/n).

A normal subgroup H of a group G is a subgroup that is invariant under conjugation by elements of G. That is, for any g in G and h in H, the element g⁻¹hg is also in H.

For example, in the group of integers under addition, any subgroup is normal. In the group of 2×2 invertible matrices under matrix multiplication, the subgroup of matrices with determinant 1 is normal.

**(b) Form a binary search tree for the data 16,24,7,5,8,20,40,3. **

Starting with an empty binary search tree, we can add the elements one by one according to the rule that smaller elements go to the left and larger elements go to the right. Here are the steps:

- Add 16 to the root.

```
16
/ \
None None
```

- Add 24 to the right of 16.

```
16
\
24
/ \
None None
```

- Add 7 to the left of 16.

```
16
/ \
7 24
/ / \
None None None
```

- Add 5 to the left of 7.

```
16
/ \
7 24
/ \
5 None
/ \
None None
```

- Add 8 to the right of 7.

```
16
/ \
7 24
/ \
5 8
/ \
None None
```

- Add 20 to the right of 24.

```
16
/ \
7 24
/ \ / \
5 8 None 20
/ \
None None
```

- Add 40 to the right of 20.

```
16
/ \
7 24
/ \ / \
5 8 None 20
/ \ \
None None 40
```

The resulting binary search tree is shown above.

**(c) Explain Post order traversal. Given the postorder and inorder traversal ofa binary tree, draw the unique binary tree.Postorder: d e c f b h i g aInorder: d c e b f a h g i. **

Postorder traversal is a way to traverse a binary tree where we visit the left subtree, right subtree, and then the root. So, in postorder traversal, we first visit the left child of a node, then its right child and finally the node itself.

To construct a binary tree from its postorder and inorder traversal, we need to follow these steps:

- The last element of postorder traversal will be the root of the tree.
- Find the root element in inorder traversal. All elements to the left of the root in inorder traversal will form the left subtree of the root and all elements to the right of the root in inorder traversal will form the right subtree of the root.
- Recursively repeat step 1 and 2 for each subtree.

Using the given postorder and inorder traversal, we can construct the following binary tree:

```
a
/ \
/ \
/ \
b g
/ \ / \
c f h i
/ \
d e
```

Here, the postorder traversal is `d e c f b h i g a`

and the inorder traversal is `d c e b f a h g i`

.

“Do you have the answer to any of the questions provided on our website? If so, please let us know by providing the question number and your answer in the space provided below. We appreciate your contributions to helping other students succeed.”