Set Theory and Graph Concepts Explained

Posted on Sep 11, 2025 in Computers

Question 1: Set Operations

Given the universal set U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, and sets A = {2, 4, 6}, B = {1, 3, 5, 7}, C = {6, 7}.

(a) A’ ∩ B

(b) (A ∪ B) – C

(c) (A ∪ C)’

(d) (A ∩ U) ∩ (B ∪ C)

Types of Sets

1. Null Set (∅ or {}): A set containing no elements. Also called an empty set. Example: The set of students in a class who are 200 years old → ∅
2. Singleton Set: A set containing exactly one element. Example: The set of the capital of India → {“New Delhi”}
3. Finite Set: A set with a definite, countable number of elements. Example: The set of vowels in the English alphabet → {a, e, i, o, u}
4. Infinite Set: A set with an unlimited number of elements. Example: The set of natural numbers → {1, 2, 3, 4, …}
5. Countable Set: A set whose elements can be listed sequentially, even if it takes infinitely long. Includes all finite sets and some infinite sets. Example: The set of all even numbers → {2, 4, 6, 8, …}
6. Uncountable Set: A set with so many elements that they cannot be listed or counted. Example: The set of all real numbers between 0 and 1 → (0, 1)
7. Universal Set: The set containing all elements relevant to a specific context, denoted by U. Example: U={0,1,2,3,4,5,6,7,8,9} for digits.
8. Power Set: The set of all possible subsets of a given set, including the empty set and the set itself. Example: If A={1,2}, then P(A)={∅,{1},{2},{1,2}}
9. Equivalent Set: Two sets with the same number of elements, regardless of the elements themselves. Example: A={1,2,3}, B={a,b,c} are equivalent.
10. Equal Set: Two sets with exactly the same elements, irrespective of order. Example: A={2,3,4}, B={4,3,2} are equal.
11. Subset: Set A is a subset of Set B if all elements of A are in B (A⊆B). Example: A={1,2}, B={1,2,3} → A⊆B.
12. Proper Subset: A subset that does not contain all elements of the original set (A⊂B). Example: A={1,2}, B={1,2,3} → A⊂B.
13. Superset: Set B is a superset of Set A if B contains all elements of A (B⊇A). Example: A={2,3}, B={1,2,3,4} → B⊇A.

Question 2: Set Partitions

Rules to create Partitions:

• No empty set.
• The union of all sets in the partition must equal the original set.
• The intersection of any two distinct sets in the partition must be empty.

(a) Partitions of A = {1, 2, 3}:

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

(b) Partitions of B = {a, b, c, d}:

1. {{a}, {b}, {c}, {d}}
2. {{a, b}, {c}, {d}}
3. {{a, c}, {b}, {d}}
4. {{a, d}, {b}, {c}}
5. {{b, c}, {a}, {d}}
6. {{b, d}, {a}, {c}}
7. {{c, d}, {a}, {b}}
8. {{a, b, c}, {d}}
9. {{a, b, d}, {c}}
10. {{a, c, d}, {b}}
11. {{b, c, d}, {a}}
12. {{a, b}, {c, d}}
13. {{a, c}, {b, d}}
14. {{a, d}, {b, c}}
15. {{a, b, c, d}}

Types of Relations

1. Empty Relation: No elements are related. Example: R = {} on set A = {1, 2, 3}.
2. Universal Relation: Every element is related to every other element. Example: R = A × A for set A = {1, 2}.
3. Reflexive Relation: Every element is related to itself. Example: (1,1), (2,2), (3,3) must be in R for A = {1, 2, 3}.
4. Irreflexive Relation: No element is related to itself. Example: (1,1), (2,2) should not be in R.
5. Symmetric Relation: If (a, b) ∈ R, then (b, a) ∈ R. Example: If (2,3) ∈ R, then (3,2) must also ∈ R.
6. Asymmetric Relation: If (a, b) ∈ R, then (b, a) ∉ R, and no element is related to itself. Example: If (1,2) ∈ R, then (2,1) must not ∈ R.
7. Antisymmetric Relation: If (a, b) ∈ R and (b, a) ∈ R, then a = b. Example: If (2,3) and (3,2) are both in R, it’s not antisymmetric.
8. Transitive Relation: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. Example: If (1,2) and (2,3) are in R, then (1,3) must be in R.
9. Equivalence Relation: A relation that is reflexive, symmetric, and transitive. Example: “is equal to”.
10. Partial Order Relation: A relation that is reflexive, antisymmetric, and transitive. Example: “less than or equal to” (≤) on numbers.

Question 5: Quadratic Function Evaluation

Given f(x) = ax² + bx + 2:

f(1) = 3 implies a(1)² + b(1) + 2 = 3, so a + b = 1.

f(4) = 42 implies a(4)² + b(4) + 2 = 42, so 16a + 4b = 40, which simplifies to 4a + b = 10.

Subtracting the first equation (a + b = 1) from the second (4a + b = 10) gives 3a = 9, so a = 3.

Substituting a = 3 into a + b = 1 gives 3 + b = 1, so b = -2.

Therefore, f(x) = 3x² – 2x + 2.

Algebraic Structures

1. Semigroup

A non-empty set with an associative binary operation. For all a, b, c in the set, (a * b) * c = a * (b * c). Example: Natural numbers under addition.

2. Monoid

A semigroup with an identity element (e) such that a * e = e * a = a. Satisfies closure, associativity, and identity. Example: Non-negative integers under addition (identity is 0).

3. Group

A monoid where every element has an inverse. Satisfies closure, associativity, identity, and inverse. Example: Integers under addition (identity is 0, inverse of 5 is -5).

4. Subgroup

A subset of a group that is itself a group under the same operation. Example: Multiples of 3 under addition is a subgroup of integers under addition.

5. Ring

A set with two binary operations (addition and multiplication) where the set is an abelian group under addition, a semigroup under multiplication, and multiplication distributes over addition. Example: Integers under addition and multiplication.

Graph Theory Fundamentals

3. Definition of a Graph

A graph consists of vertices (nodes) and edges (lines) representing relationships between objects. Example: Vertices = {A, B, C}, Edges = {(A, B), (B, C)}.

2. Types of Graphs

• Simple Graph: No loops or multiple edges between the same pair of vertices.
• Multigraph: Allows multiple edges between the same pair of vertices.
• Loop Graph: Contains edges that start and end at the same vertex.
• Complete Graph: Every pair of distinct vertices is connected by a unique edge.
• Null Graph: A graph with no edges.
• Connected Graph: There is a path between every pair of vertices.
• Disconnected Graph: Not all vertices are connected by a path.
• Weighted Graph: Edges have associated numerical values (weights).

3. Directed and Undirected Graphs

• Directed Graph (Digraph): Edges have a direction (e.g., A → B).
• Undirected Graph: Edges have no direction (e.g., (A, B) means A is connected to B and vice versa).

4. Walk

A sequence of vertices and edges where each edge connects the preceding and succeeding vertices. Vertices and edges can be repeated. Example: A-B-C-B-D.

5. Path

A walk where no vertex or edge is repeated (except possibly the start/end vertex in a cycle). Example: A-B-C-D.

6. Circuit

A closed path that starts and ends at the same vertex, with no repeated vertices or edges (except the start/end vertex). Example: A-B-C-A.

7. Regular Graph

A graph where all vertices have the same degree (number of edges connected to them). A k-regular graph has all vertices with degree k. Example: A graph where every vertex connects to exactly 3 others.

8. Tree

A connected graph with no cycles. There is exactly one path between any two vertices. Example: Family tree, file system structure.