1. Define set with a Example ?

Concept Definition Example

A collection of distinct
Set elements, represented by A={1,2,3}.
curly braces.
A set B is a subset of A if all
{1},{2},{1,2}are subsets of
Subset elements of B are also
A={1,2,3}.
elements of A.
A set B is a proper subset of A {1} is a proper subset of
Proper
if B contains some but not all {1,2,3}, but {1,2,3} is not a
Subset
elements of A, and B≠A. proper subset of itself.
The set of all subsets of A,
including the empty set and A
Power For A={1,2},
itself. The number of subsets
Set P(A)={∅,{1},{2},{1,2}.
is 2n {2^n} for A with n
elements.

2. What is relation provide a example ?

A relation is a connection or association between elements of two sets.
Formally, a relation R from set A to set B is a subset of the Cartesian
product A×B, meaning that it consists of ordered pairs (a,b)(a, b)(a,b),
where a∈A and b∈B. In other words, a relation relates each element of
set A to an element in set B based on a specific rule or condition.
Notation:
If a is related to b, we write:
aRb
Alternatively, this is represented as an ordered pair (a,b)∈R.
Types of Relations:
1. Reflexive: A relation R on a set A is reflexive if, for every element
a∈A, the pair (a,a) is in R.
2. Symmetric: A relation R on a set A is symmetric if, whenever
(a,b)∈R, then (b,a)∈R.
3. Transitive: A relation R on a set A is transitive if, whenever (a,b)∈R
and (b,c)∈R, then (a,c)∈R.
4. Antisymmetric: A relation R on a set A is antisymmetric if,
whenever (a,b)∈R(a, b) \in R(a,b)∈R and (b,a)∈R(b, a) \in R(b,a)∈R,
then a=ba = ba=b.
Example of a Relation:
Consider two sets:
• A={1,2,3}
• B={a,b,c}
Now, let's define a relation R from set A to set B, where each element
of A is related to some element in B.
• Let R={(1,a),(2,b),(3,c)}.
This means:
• The element 1 in set A is related to the element A in set B.
• The element 2 in set A is related to the element B in set B.
• The element 3 in set A is related to the element C in set B.
Visualization of the Relation:
You can visualize the relation as a set of ordered pairs:
R={(1,a),(2,b),(3,c)}.
Or as a diagram:
 • A={1,2,3}
• B={a,b,c}
1a2b3c\begin{array}{c|c} 1 & a \\ 2 & b \\ 3 & c \\ \end{array}123abc
This diagram shows how elements from A are associated with elements
from B through the relation R.
Another Example:
Let’s take the relation "is greater than" between two sets of integers:
• Let A={1,2,3}
• Let B={2,3,4}
Define the relation R as "is greater than":
• 2 is greater than 1, so (2,1)∈R.
• 3 is greater than 2, so (3,2)∈R.
• 3 is greater than 1, so (3,1)∈R.
• 4 is greater than 3, so (4,3)∈R.
Hence, the relation can be written as:
R={(2,1),(3,2),(3,1),(4,3)}

3. Define asymptotic notation and give

example?
Asymptotic notation is a mathematical framework used to describe
the behavior of functions as their inputs grow large. In the context of
computer science, asymptotic notations are commonly used to
describe the time complexity or space complexity of algorithms,
providing an approximation of their behavior in the worst-case, best-
case, or average-case scenario.
Common Types of Asymptotic Notation:
There are several common types of asymptotic notations:
1. Big O Notation ( O(f(n)):
o Definition: Big O notation describes the upper bound of an
algorithm's complexity. It provides an upper limit on the
growth rate of a function.
o Usage: It gives the worst-case scenario, representing the
maximum amount of time or space that an algorithm will
take as the input size increases.
o Example: If an algorithm's time complexity is O(n2)it means
the algorithm's running time increases at most in proportion
to the square of the input size.
Example:
If f(n)=3n2+5n+2, then f(n)=O(n2).

4. What is a graph ? mention one example of a

multigraph?
A graph is a collection of vertices (or nodes) and edges (or arcs) that
connect pairs of vertices. Mathematically, a graph G is defined as a pair
G=(V,E), where:
• V is the set of vertices (also called nodes),
• E is the set of edges, where each edge is a pair of vertices.
Types of Graphs:
1. Undirected Graph: In an undirected graph, edges have no
direction. That is, if there is an edge between vertex A and vertex
B, it can be traversed in both directions.
2. Directed Graph (Digraph): In a directed graph, edges have a
direction. An edge from vertex A to vertex B is different from an
edge from B to A.
 3. Weighted Graph: In a weighted graph, each edge has an
associated weight or cost.
4. Unweighted Graph: In an unweighted graph, all edges are
considered equal, with no specific weight or cost.
5. Cyclic Graph: A graph that contains at least one cycle (a closed
loop of edges).
6. Acyclic Graph: A graph that contains no cycles

Multigraph example :-
A multigraph is a type of graph where multiple edges (more than one)
can exist between the same pair of vertices. In a multigraph, it is
allowed to have multiple edges (also called parallel edges) between
the same pair of nodes.
Example of a Multigraph:
Let’s consider a multigraph with the following vertices and edges:
• Vertices: V={A,B,C}.
• Edges: E={{A,B},{A,B},{B,C}.
In this multigraph:
• There are two edges between A and B, indicating multiple
connections between these two vertices.
• There is one edge between B and C.
This can be visually represented as:
css
Copy code
A —— B —— C
| |
 ----

5. Define a Degree in vertex in graph ?

The degree of a vertex in a graph is the number of edges that are
incident to (connected to) that vertex. In other words, the degree
represents how many direct connections (or neighbors) a vertex has in
the graph.
• For undirected graphs, the degree of a vertex v, denoted as
deg⁡(v), is the total number of edges connected to vertex v.
• For directed graphs (digraphs), there are two types of degrees:
o In-degree: The number of edges directed towards the vertex.
o Out-degree: The number of edges directed away from the
vertex.
Degree in Undirected Graphs:
In an undirected graph, each edge connects two vertices, and the
degree of a vertex is simply the count of how many edges are attached
to it. The degree is always a non-negative integer.
Example:
Consider the following undirected graph:
A —— B —— C
\ /
\ /
D
• Degree of vertex A: There are two edges connected to A (one with
B and one with D), so deg⁡(A)=2.
• Degree of vertex B: There are two edges connected to B (one with
A and one with C), so deg⁡(B)=2.
 • Degree of vertex C: There are two edges connected to C (one with
B and one with D), so deg⁡(C)=2.
• Degree of vertex D: There are two edges connected to D (one
with A and one with C), so deg⁡(D)=2.
Degree in Directed Graphs (Digraphs):
In a directed graph (digraph), edges have a direction, so we distinguish
between in-degree and out-degree.
• In-degree: The number of incoming edges to the vertex (edges
pointing to the vertex).
• Out-degree: The number of outgoing edges from the vertex
(edges pointing away from the vertex).
Example:
Consider the following directed graph:
Copy code
A→B
↑ ↓
D←C
• In-degree of vertex A: 0 (no edges point to A).
• Out-degree of vertex A: 1 (1 edge points from A to B).
• In-degree of vertex B: 1 (1 edge points to B from A).
• Out-degree of vertex B: 1 (1 edge points from B to C).
• In-degree of vertex C: 1 (1 edge points to C from B).
• Out-degree of vertex C: 1 (1 edge points from C to D).
• In-degree of vertex D: 1 (1 edge points to D from C).
• Out-degree of vertex D: 0 (no edges point from D).
6. What is cartesian product of two sets ?
provide an example ?

The Cartesian product of two sets A and B, denoted by A×B, is the set
of all possible ordered pairs where the first element of each pair comes
from set A and the second element comes from set B.
Mathematically, the Cartesian product A×B is defined as:
A×B={(a,b)∣a∈A and b∈B}.
• Here, A is any element of set A, and B is any element of set B.
• Each element of the Cartesian product is an ordered pair,
meaning the order of elements matters (i.e., (a,b)≠(b,a) .
Example of Cartesian Product
Let’s consider two sets:
• Set A={1,2}
• Set B={a,b}
The Cartesian product A×B consists of all possible ordered pairs where
the first element is from A and the second element is from B.
A×B={(1,a),(1,b),(2,a),(2,b)}.
What is Difference between subset and proper set?
1. Subset ( A⊆B ):
A set A is called a subset of a set B if every element of A is also an
element of B. This is written as:
A⊆B
In other words, if all elements of A are contained in B, then A is a
subset of B.
 • Note: A set is always a subset of itself. That is, A⊆A.
• A subset can either be equal to the original set B or a smaller set
with fewer elements than B.
Example:
Let:
A={1,2},B={1,2,3,4}
• Subset: A⊆B because all elements of A (1 and 2) are also in B.

2. Proper Subset ( A⊂B):

A set A is called a proper subset of a set B if every element of A is in B,
and there is at least one element in B that is not in A. This is written as:
A⊂B
In other words, A is a proper subset of B if A is contained within B, but
A is not equal to B. There must be at least one element in B that is not
in A.
• Note: A set cannot be a proper subset of itself. That is, A⊂A is not
true.
Example:
Let:
A={1,2},B={1,2,3,4}
• Proper Subset: A⊂B because all elements of A (1 and 2) are in B,
and B has additional elements (3 and 4) that are not in A.
However:
B⊂Ais false, becauseB≠A.

Key Differences:
Property Subset Proper Subset
Every element of A is in B (can Every element of A is in B,
Definition
be equal to B) and A≠B
Notation A⊆B A⊂B
Equality A can be equal to B A cannot be equal to B
Example A={1,2},B={1,2}⇒A⊆B A={1,2},B={1,2,3}⇒A⊂B
Self- A set is always a subset of A set is never a proper
subset itself subset of itself

7. Explain graph coloring and its applications?

Graph coloring is a technique used in graph theory to assign labels (or
colors) to the vertices or edges of a graph in such a way that certain
conditions are met. The most common form of graph coloring is vertex
coloring, where colors are assigned to the vertices of a graph such that
no two adjacent vertices share the same color.
Formally, a vertex coloring of a graph G=(V,E) is a function f:V→C ,
where C is a set of colors and f(u)≠f(v) for every edge (u,v)∈E . This
means that adjacent vertices must have different colors.
The chromatic number of a graph is the smallest number of colors
needed to color the graph.
Types of Graph Coloring:
1. Vertex Coloring:
o The objective is to assign colors to the vertices of the graph
such that no two adjacent vertices share the same color.
o The chromatic number χ(G) is the smallest number of colors
required for the coloring.
 2. Edge Coloring:
o In this case, the colors are assigned to the edges of the graph,
and no two edges incident on the same vertex can share the
same color.
3. Face Coloring (for planar graphs):
o This involves assigning colors to the faces (regions) of a
planar graph such that no two adjacent faces share the same
color.
Example of Graph Coloring:
Consider the following simple graph:

A —— B
| |
D —— C
This satisfies the condition, as no two adjacent vertices share the same
color.
Applications of Graph Coloring:
Graph coloring has many applications in real-world problems,
particularly in scenarios involving resource allocation, scheduling, and
optimization. Some of the key applications include:

8. What is Tautology?
In logic, a tautology is a statement that is always true, regardless of
the truth values of the individual components or variables involved. It
is a formula or proposition that is true in every possible interpretation.
Tautologies are often used in logical proofs and reasoning to
demonstrate that a conclusion is universally valid. In simple terms, no
matter what values you assign to the components of a tautology, the
overall result is always true.
Example of a Tautology:
Consider the logical statement:
P∨¬P
Where:
• P is a logical variable (it can be true or false),
• ¬P represents the negation of P (if P is true, ¬P is false, and vice
versa),
• ∨ represents the logical OR operation.
This statement says "P OR not P."
Truth Table for P∨¬P :
P ¬P P∨¬P
True False True
False True True
• When P is True, ¬P is False, and P∨¬P evaluates to True.
• When P is False, ¬P is True, and P∨¬P evaluates to True.
In both cases, P∨¬P is True, so the statement is a tautology.
Why is it a Tautology?
A tautology is a logical expression that is always true, and P∨¬PP \vee
\neg PP∨¬P is true regardless of whether PPP is true or false. The key is
that, in any case, either PPP is true, or ¬P\neg P¬P (not PPP) is true, so
the whole statement is always true. This makes it a tautology.
Another Example:
Consider the logical expression:
P→(Q∨¬Q)
Where:
• P is a proposition,
• Q is another proposition,
• → represents logical implication (if-then),
• ∨ represents logical OR, and
• ¬Q represents the negation of Q.
This expression says: "If P is true, then Q OR not Q is true."
Since Q∨¬Q is a tautology (as shown above, it's always true), the entire
statement P→(Q∨¬Q) is always true, regardless of the truth value of P.
Truth Table for P→(Q∨¬Q):
P Q Q∨¬ P→(Q∨¬Q)

True True True True

True False True True

False True True True

False False True True

In all cases, P→(Q∨¬Q) is True, making it a tautology.