b) (i) Show that the following graphs are isomorphic.

Also give the correspondence between edges

and vertices of the two graphs.

Showing Isomorphism:
Two graphs are isomorphic if there's a one-to-one correspondence (bijection) between their vertices
that preserves adjacency. In simpler terms, you can "redraw" one graph to look exactly like the other
by just renaming the vertices.

Correspondence:

• Vertices:

o A -> 1

o B -> 2

o C -> 3

o D -> 4

o E -> 5

Why this shows isomorphism:

• One-to-one mapping: Each vertex in the first graph is paired with exactly one unique vertex
in the second graph, and vice versa.

• Adjacency preserved: If two vertices are connected in the first graph, their corresponding
vertices are connected in the second graph. For example, A is connected to B in the first
graph, and 1 is connected to 2 in the second graph.
(a) Constructing a Binary Search Tree (BST)

The given sequence: 32, 56, 47, 28, 30, 45, 15, 72, 25

Step-by-step construction:

1. Insert 32 → Root node.

2. Insert 56 → Goes to the right of 32.

3. Insert 47 → Goes to the left of 56.

4. Insert 28 → Goes to the left of 32.

5. Insert 30 → Goes to the right of 28.

6. Insert 45 → Goes to the left of 47.

7. Insert 15 → Goes to the left of 28.

8. Insert 72 → Goes to the right of 56.

9. Insert 25 → Goes to the right of 15.

BST Representation:
Steps to Search for 25:

1. Start at root (32) → Move left (since 25 < 32).

2. At 28 → Move left (since 25 < 28).

3. At 15 → Move right (since 25 > 15).

4. Found 25!

Q.6. a) Definitions

(1) Abelian Group

An abelian group is a set A with a binary operation * that satisfies the following properties:

• Closure: For all a, b in A, a * b is in A.

• Associativity: For all a, b, c in A, (a * b) * c = a * (b * c).

• Identity: There exists an element e in A such that for all a in A, a * e = e * a = a.

• Inverse: For each a in A, there exists an element a⁻¹ in A such that a * a⁻¹ = a⁻¹ * a = e.

• Commutativity: For all a, b in A, a * b = b * a.

(2) Monoid

A monoid is a set M with a binary operation * that satisfies the following properties:

• Closure: For all a, b in M, a * b is in M.

• Associativity: For all a, b, c in M, (a * b) * c = a * (b * c).

• Identity: There exists an element e in M such that for all a in M, a * e = e * a = a.

(3) Ring

A ring is a set R with two binary operations, + and *, such that:

• (R, +) is an abelian group.

• (R, *) is a monoid.

• Distributivity: For all a, b, c in R,

 o a * (b + c) = (a * b) + (a * c)

o (b + c) * a = (b * a) + (c * a).

(a) Construct Hasse Diagram

The given set is:

X={2,3,6,12,24,36}X = \{2, 3, 6, 12, 24, 36\}X={2,3,6,12,24,36}
The relation RRR is defined as (x,y)(x, y)(x,y) such that xxx divides yyy.

To construct the Hasse diagram, follow these steps:

1. Draw elements in increasing order.

 2. Connect elements if xxx divides yyy directly (without any intermediate element).

3. Remove transitive edges.

The Hasse Diagram will look like this:

Connections:

• 2 divides 6

• 3 divides 6

• 6 divides 12

• 6 divides 24

• 12 divides 36

• 24 divides 36

(b) Find Maximal and Minimal Elements

• Minimal Element: The smallest elements that are not divisible by any other element.
Minimal = {2, 3}

• Maximal Element: The largest element that does not divide any other element.
Maximal = {36}

(c) Is the Poset a Lattice? Justify

A poset is a lattice if for every pair of elements, their Least Upper Bound (LUB, also called Join) and
Greatest Lower Bound (GLB, also called Meet) exist.

• GLB (Meet): The greatest common divisor (GCD) of any two elements in XXX.

• LUB (Join): The least common multiple (LCM) of any two elements in XXX.

For all pairs in XXX, the GCD and LCM exist within XXX, meaning the poset is a lattice.

Final Answer:

(a) Hasse Diagram constructed.

(b) Maximal Element = {36}, Minimal Elements = {2, 3}
(c) Yes, it is a lattice because every pair of elements has a least upper bound and greatest lower
bound.

Q. Given A = {1, 2, 3, 4} and B = {x, y, z}. Let R be the following relation from A to B:

R = {(1, y), (1, z), (3, y), (4, x), (4, z)}

(a) Determine the matrix of the relation.

(b) Find the inverse relation R−1 of R.

(c) Determine the domain and range of R.

Given Data:

Set:

A={1,2,3,4}A = \{1, 2, 3, 4\}A={1,2,3,4}

Relation RRR on AAA:

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

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

(a) Draw the Directed Graph of RRR

A directed graph (digraph) consists of nodes representing elements of AAA and directed edges based
on the relation RRR.

• Self-loops at 111, 222, and 444 because of (1,1)(1,1)(1,1), (2,2)(2,2)(2,2), and (4,4)(4,4)(4,4).

• Directed edges between:

Graph Representation:
(b) Is R (i) reflexive, (ii) symmetric, (iii) transitive, or (iv) antisymmetric?
(i) Reflexive:
• Definition: A relation is reflexive if for every element 'a' in A, (a, a) is in R.
• Check: We need (1, 1), (2, 2), (3, 3), and (4, 4) to be in R.
• Result: R is NOT reflexive because (3, 3) is missing.
(ii) Symmetric:
• Definition: A relation is symmetric if for every (a, b) in R, (b, a) is also in R.
• Check:
o (2, 3) is in R, and (3, 2) is also in R.
o (4, 2) is in R, but (2, 4) is NOT in R.
• Result: R is NOT symmetric because (2, 4) is missing.
(iii) Transitive:
• Definition: A relation is transitive if for every (a, b) and (b, c) in R, (a, c) is also in R.
• Check:
o (2, 3) and (3, 2) are in R. If R is transitive, (2, 2) should be in R, which it is.
o (4, 2) and (2, 3) are in R. If R is transitive, (4, 3) should be in R.
• Result: R is NOT transitive because (4, 3) is missing.
(iv) Antisymmetric:
• Definition: A relation is antisymmetric if for every (a, b) and (b, a) in R, a must equal b.
• Check:
o We have (2, 3) and (3, 2) in R, and 2 ≠ 3.
• Result: R is NOT antisymmetric.
The roots are r₁ = 2 and r₂ = -1.

The general solution is of the form:

aₙ = A(2)ⁿ + B(-1)ⁿ, where A and B are constants.

Definition of Isomorphic Graphs:

Two graphs GGG and HHH are isomorphic if there exists a one-to-one correspondence between their
vertices and edges such that the adjacency relationships are preserved. That is, if there is a mapping
of vertices from GGG to HHH where edges between vertices in GGG correspond to edges between
the mapped vertices in HHH.

Checking Isomorphism for (a)

• The two graphs in figure (a), GGG and HHH, have the same number of vertices and edges.

• Examining the degree of each vertex:

o In both graphs, there are three vertices with degree 2 and two vertices with degree
3.

o The adjacency relationships match if the labels are renamed correctly.

• Since there is a one-to-one correspondence preserving adjacency, Graphs G and H are

isomorphic.

Checking Isomorphism for (b)

• Both graphs in figure (b) have 8 vertices and 12 edges.

• The degree of each vertex in both graphs is exactly 3.

• Both graphs appear to have a cylindrical structure where vertices are connected in a similar
way.

• Since their connectivity and adjacency relationships are preserved, the graphs in (b) are
isomorphic.
(a) Draw the graph K2, 5. (draw graph )

(a) Draw the graph K2,5K_{2,5}K2,5:

K2,5K_{2,5}K2,5 is a complete bipartite graph, meaning it has two sets of vertices, one with 2
vertices and the other with 5 vertices, with edges between every pair of vertices from different sets.
I'll generate an image of this graph.

(b) Define the following terms: (i) Planar Graph (ii) Bipartite Graph (iii) Complete graph

(b) Definitions:

1. Planar Graph: A graph is planar if it can be drawn on a plane without any edges crossing
each other.

2. Bipartite Graph: A graph is bipartite if its vertices can be divided into two disjoint sets such
that no two vertices within the same set are adjacent.

3. Complete Graph: A graph is complete (denoted as KnK_nKn) if every pair of distinct vertices
is connected by exactly one edge.

4.

c) Draw the 2-regular graph with 5 vertices

(c) Draw a 2-regular graph with 5 vertices:

A 2-regular graph means that every vertex has exactly two edges. One common example of a 2-
regular graph with 5 vertices is a cycle (C₅), where each vertex connects to exactly two others,
forming a closed loop.
C) Write the Euler’s Formula. Prove that in planar graph G with p vertices and q edges, where

p ≥ 3 then q ≥ 3p – 6.
Construct a Binary Search Tree by inserting the following sequence of numbers:

10, 12, 5, 4, 20, 8, 7, 15, 13.

Also Find Preorder, Inorder and Postorder traversal of Binary Search Tree.
Consider the group G = {1, 2, 3, 4, 5, 6} under multiplication modulo 7.

(a) Find the multiplication table of G.

(b) Find the 2-1, 3-1, 6-1.

(c) Find the orders and subgroups generated by 2 and 3.

Rooted Tree

A rooted tree is a tree in which one vertex is designated as the root. The root is the ancestor of all other
nodes in the tree, and all other nodes can be reached by traversing the edges from the root.

Example:
In this example, "A" is the root, and all other nodes (B, C, D, E, F) can be reached from "A".

Balanced Tree

A balanced tree is a tree in which the heights of the two subtrees of any node differ by at most one. This
ensures that the tree remains balanced and optimizes search and insertion operations.

Example:

In this example, the heights of the subtrees of each node differ by at most one, ensuring the tree is balanced.

Binary Search Tree (BST)

A Binary Search Tree is a tree in which each node has at most two children, and the left child has a value less
than the parent node, while the right child has a value greater than the parent node.

Example:

In this example, the left child of node 10 is 5 (less than 10), and the right child is 15 (greater than 10). This
property holds true for all nodes in the BST.
Let's prove that the algebraic system (G, ⊕) forms a group, where G = {1101, 0000, 1001, 0100} and ⊕
represents the bitwise XOR operation.

1. Closure:
We need to show that for any two elements a, b in G, a ⊕ b is also in G.

• 1101 ⊕ 0000 = 1101 (in G)

• 1101 ⊕ 1001 = 0100 (in G)

• 1101 ⊕ 0100 = 1001 (in G)

• 0000 ⊕ 1001 = 1001 (in G)

• 0000 ⊕ 0100 = 0100 (in G)

• 1001 ⊕ 0100 = 1101 (in G)

Since all possible combinations result in elements within G, the closure property is satisfied.

2. Associativity:

Bitwise XOR is associative. For any binary strings a, b, and c:

(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

This holds true for all elements in G.

3. Identity Element:

The identity element for XOR is 0000.

• For any element a in G: a ⊕ 0000 = a 0000 ⊕ a = a

4. Inverse Element:

For each element in G, we need to find its inverse such that when XORed with the element, it results in the
identity element (0000).

• 1101: 1101 ⊕ 1101 = 0000 (Inverse of 1101 is itself)

• 0000: 0000 ⊕ 0000 = 0000 (Inverse of 0000 is itself)

• 1001: 1001 ⊕ 1001 = 0000 (Inverse of 1001 is itself)

• 0100: 0100 ⊕ 0100 = 0000 (Inverse of 0100 is itself)

Since each element has an inverse within G, the inverse property is satisfied.

Conclusion:

Since (G, ⊕) satisfies all four group axioms (closure, associativity, identity, and inverse), we conclude that (G,
⊕) is a group. It is also an example of a commutative (Abelian) group because the XOR operation is
commutative (a ⊕ b = b ⊕ a).

A ring is an algebraic structure consisting of a set RR equipped with two binary operations: addition (++) and
multiplication (⋅·)
Explain with example, notation used and mathematical pression to describe following terms

1)Membership 2) Subset 3) Equality of two sets

Q>Constructor a truth table for each of these compound propositions and identify type of compound
statements
a. (p ⋀ q) → (p ⋁ q)

b. (q → ¬ p) ↔ (p ↔ q)

Final Answer

• (p∧q)→(p∨q)(p \land q) \to (p \lor q)(p∧q)→(p∨q) is a Tautology.

• (q→¬p)↔(p↔q)(q \to \neg p) \leftrightarrow (p \leftrightarrow q)(q→¬p)↔(p↔q) is a

Contingency.
Q>Test the validity of following statement: If there is strike by student, then exam will be postponed. Exam
was not postponed. Therefore, there were no strikes by students.

Step 1: Define Propositions

Let:

• p = "There is a strike by students"

• q = "The exam will be postponed"

since the argument follows the Modus Tollens rule, the reasoning is logically valid.
Thus, the conclusion "There were no strikes by students" is valid based on the given premises.
Q> Let A= {1,2,3,4,6,8,12} and R be the partial order on A defined by aRb if a divides b.
Determine the relational matrix for R. Construct directed graph G on A. Draw Hasse diagram of
Poset (A, R).
Q> State Pigeon hole principle. If five colors are used to paint 26 doors show that at least Six doors will have
the same door

Q>Let f(x) =2x+3, g(x) =3x+4, h(x) =4x for x ∈ R, where R is set of real num-bers. Find gof, fog, foh and hof.
Define Euler graph and Hamiltonian graph

1) For a given graph G1

a) Find a Hamiltonian path that begins at A and ends at E.

b) Find a Hamiltonian circuit that starts at A and ends with the pair of vertices E, A

c) Find a Hamiltonian path that begins at F and ends at G.

Euler Graph: An Euler graph (or Eulerian graph) is a graph where there exists a closed trail that visits every
edge exactly once. For a graph to be Eulerian, every vertex must have an even degree.

Hamiltonian Graph: A Hamiltonian graph is a graph where there exists a closed path (cycle) that visits every
vertex exactly once. This path is known as a Hamiltonian circuit. A Hamiltonian path visits every vertex
exactly once but doesn't need to end where it started.

For the given graph G1:

a) Find a Hamiltonian path that begins at A and ends at E.

A Hamiltonian path that begins at A and ends at E is: A -> D -> G -> C -> B -> F -> E

b) Find a Hamiltonian circuit that starts at A and ends with the pair of vertices E, A.

A Hamiltonian circuit that starts at A and ends with the pair of vertices E, A is: A -> B -> F -> E -> C -> G -> D ->
A

c) Find a Hamiltonian path that begins at F and ends at G.

A Hamiltonian path that begins at F and ends at G is: F -> B -> A -> D -> C -> E -> G

Q> For a given graph G2 find Eulerian path and Eulerian cycle
Graph G2G2

The vertices and their connections are:

• Vertex 0 is connected to vertices 1, 3, and 4.

• Vertex 1 is connected to vertex 2.

• Vertex 2 is connected to vertex 0.

• Vertex 3 is connected to vertex 4.

Degrees of Vertices

• Vertex 0: Degree 3

• Vertex 1: Degree 1

• Vertex 2: Degree 2

• Vertex 3: Degree 2

• Vertex 4: Degree 2

Eulerian Path and Eulerian Cycle Conditions:

• Eulerian Path: Exists if exactly 0 or 2 vertices have an odd degree.

• Eulerian Cycle

• : Exists if all vertices have an even degree.

Analysis for G2G2:

• Eulerian Path: There are 2 vertices (0 and 1) with an odd degree. Therefore, an Eulerian path exists.

• Eulerian Cycle: Since not all vertices have even degrees, an Eulerian cycle does not exist.

Eulerian Path Example:

One possible Eulerian path in G2G2 is: 0 -> 1 -> 2 -> 0 -> 3 -> 4

Summary:

• Eulerian Path: Exists. Example path: 0 -> 1 -> 2 -> 0 -> 3 -> 4

• Eulerian Cycle: Does not exist.

q> Find a shortest path between vertices a and z in the given graph using Dijkstra

shortest path algorithm

Q?Define the following with reference to tree with example

a) Level and Height of a tree

b) M-ary tree

c) Fundamental Cut Sets

Q? Construct a minimum spanning tree (MST) for the given graph using Kruskal’s.
Show that a tree with n vertices has n-1 edges

Proof by Induction:

1. Base Case:

o For n=1n = 1 (a tree with one vertex), the tree has 0 edges, which satisfies n−1=0n - 1 = 0.

2. Inductive Step:

o Assume the statement is true for a tree with kk vertices, i.e., it has k−1k - 1 edges.

o Consider a tree with k+1k + 1 vertices. Adding one vertex to a tree with kk vertices involves
connecting it with an edge to any existing vertex in the tree.

o This new tree now has k+1k + 1 vertices and kk edges (since k−1k - 1 edges in the original
tree plus one new edge).

By induction, we have shown that a tree with n vertices has n−1n - 1 edges.

Q> Define the following terms

1. Algebraic structures 2. Semi Group 3. Monoids

4. Ring 5. Field 6. Group

1. Algebraic Structures

Definition: Algebraic structures are mathematical sets equipped with one or more operations that satisfy a
given set of axioms. Examples of algebraic structures include groups, rings, fields, semigroups, and monoids.

2. Semigroup

Definition: A semigroup is an algebraic structure consisting of a non-empty set along with an associative
binary operation. The operation combines any two elements of the set to form another element of the same
set.

Example: The set of natural numbers with addition (++) is a semigroup because addition is associative:
(a+b)+c=a+(b+c)(a + b) + c = a + (b + c).

3. Monoids

Definition: A monoid is a semigroup with an identity element. An identity element is an element in the set
that, when combined with any other element using the binary operation, leaves the other element
unchanged.

Example: The set of natural numbers including zero with addition (++) is a monoid. The identity element is 0:
a+0=0+a=aa + 0 = 0 + a = a.

4. Ring

Definition: A ring is an algebraic structure consisting of a set equipped with two binary operations: addition
and multiplication. The set must satisfy certain properties such as closure, associativity, distributivity, and
having an additive identity and inverses.

Example: The set of integers Z\mathbb{Z} with the usual addition and multiplication operations forms a ring.

5. Field
Definition: A field is an algebraic structure where addition, subtraction, multiplication, and division (except
by zero) are defined and satisfy certain properties such as associativity, commutativity, distributivity, identity
elements, and inverses.

Example: The set of rational numbers Q\mathbb{Q} with the usual addition, subtraction, multiplication, and
division operations forms a field.

6. Group

Definition: A group is an algebraic structure consisting of a set equipped with a single binary operation that
satisfies four properties: closure, associativity, identity, and inverses.

Example: The set of integers Z\mathbb{Z} with the operation of addition (++) forms a group. The identity
element is 0, and the inverse of a is −a.

Q> For each of following, determine whether the binary operations * is commutative or associative?

i) N is the set of natural numbers and a*b=a+b+2 for all a,b from N

ii) on N where a*b=min (a, b+2)

iii) on R where a*b=ab

Determine whether (Z, +, *) is a ring with the binary operations x + y = x + y-7 And x*y =x + y -3xy for all x, y
∈Z
Q> Let P(x), Q(x), and R(x) be the statements “x is a professor,” “x is ignorant,” and “x is vain,” respectively.
Express each of these statements using quantifiers; logical connectives; and P(x), Q(x), and R(x), where the
domain consists of all people.

(a) No professors are ignorant. (b) All ignorant people are vain.

(c) No professors are vain. (d) Does (c) follows (a) and (b)?

Q? Show that if n is a positive integer, then 1+2+3+.......+n=n(n+1)2 by using mathematical induction.

Use De Morgan’s laws to find the negation of each of the following statements.

(a) Kwame will take a job in industry or go to graduate school.

(b) Yoshiko knows Java and calculus.

(c) James is young and strong.

(d) Rita will move to Oregon or Washington

(a) Find the maximal elements.

• Maximal elements are the elements with no outgoing edges going upwards. In other words, no
other element is greater than them.

• Answer: l and m

(b) Find the minimal elements.

 • Minimal elements are the elements with no incoming edges from below. No other element is
smaller than them.

• Answer: a, b, and c

(c) Is there a greatest element?

• A greatest element is an element that is greater than or equal to all other elements in the set. There
can be only one greatest element.

• Answer: No. 'l' and 'm' are both maximal, but neither is greater than the other.

(d) Is there a least element?

• A least element is an element that is less than or equal to all other elements in the set. There can be
only one least element.

• Answer: No. 'a', 'b', and 'c' are all minimal, but none is smaller than the others.

(e) Find all upper bounds of {a, b, c}.

• An upper bound of a set is an element that is greater than or equal to every element in the set.

• Answer: d, e, h, i, j, k, l, m. (All elements above a, b, and c are upper bounds).

(f) Find all lower bounds of {f, g, h}.

• A lower bound of a set is an element that is less than or equal to every element in the set.

• Answer: a, b, c. (No other elements are below all three elements f, g, and h).

B)

Let f(x) = x + 2, g(x) = x – 2, and h(x) = 3x for x ∈ R where R = set of real numbers. Find

i) gof ii) fohog iii) foh

Q>
Q> Draw the following graphs.
a) K7 b) K1,8 c) K4,4 d) C7 e) W7 f ) Q4
Graph Isomorphism Analysis:

• Both Graphs:

o 8 vertices

o Same number of edges

o All vertices have degree 3

Path Comparison:

• Graph G:

o Paths around the perimeter without revisiting vertices (Hamiltonian cycle)

o Example path: u1 -> u2 -> u3 -> u4 -> u5

• Graph H:

o Due to interior cross-connections, paths must use interior edges

o No Hamiltonian cycle

Conclusion:

• Graph G has a Hamiltonian cycle.

• Graph H does not have this property due to its interior cross-connections.

Result: Graphs are not isomorphic.

Let's track:

• Distances from vertex 1 (we'll use ∞ for unvisited nodes)

• Previous vertices in shortest path

• Set of unvisited vertices

Step 1: Initial state

• Distance to 1: 0 (starting point)

• All other distances: ∞

• Unvisited: {0,1,2,3,4,5,6,7,8}

Step 2: Update distances from vertex 1 From vertex 1 to:

• 0: 4

• 2: 8

• 7: 11 Current shortest unvisited: vertex 0 (4)

Step 3: From vertex 0

• Can reach 7 with distance 4 + 8 = 12 (via 0) Current shortest unvisited: vertex 2 (8)

Step 4: From vertex 2

• Can reach 3: 8 + 7 = 15

• Can reach 5: 8 + 4 = 12

• Can reach 8: 8 + 2 = 10 Current shortest unvisited: vertex 8 (10)

Step 5: From vertex 8

• Can reach 6: 10 + 6 = 16 Current shortest unvisited: vertex 7 (11)

Step 6: From vertex 7

 • Can reach 6: 11 + 1 = 12 Current shortest unvisited: vertex 5 (12)

Step 7: From vertex 5

• Can reach 3: 12 + 14 = 26

• Can reach 4: 12 + 10 = 22

• Can reach 6: 12 + 2 = 14 Current shortest unvisited: vertex 6 (14)

Step 8: From vertex 6 No new shorter paths found Current shortest unvisited: vertex 3 (15)

Step 9: From vertex 3

• Can reach 4: 15 + 7 = 22 (no improvement)

Final result: The shortest path from vertex 1 to vertex 4 has length 22.

The actual path is: 1 → 2 → 5 → 4 with total distance: 8 + 4 + 10 = 22

Use Huffman’s algorithm to provide an optimal average-bit-length code for the probability distribution a: 0.2,
b: 0.2, c: 0.15, d: 0.15, e: 0.15, f: 0.1, and g: 0.05. Draw a binary tree to find the prefix code for for each
probability distribution
Q> (i) What is the value of each of the prefix expressions + − ↑ 3 2 ↑ 2 3 / 6 − 4 2?

(ii) What is the value of each of the postfix expressions 3 2 ∗ 2 ↑ 5 3 − 8 4 / ∗ −?

Consider the group G = {1, 2, 4, 7, 8, 11, 13, 14} under multiplication modulo 15.
i) Find multiplication table of G.
ii) Find 2-1, 7-1.
iii) Find the orders and subgroups generated by 7 and 11.