Discrete Mathematics Assignment Solution
Complete Solutions for Relational Algebra, Graph Theory, Functions, and Trees
Relational Algebra
Theory Questions
1. What is a relation according to discrete mathematics?
Definition: A relation R from set A to set B is a subset of the Cartesian product A × B. In
mathematical notation, R ⊆ A × B.
Key Points:
A relation consists of ordered pairs (a, b) where a ∈ A and b ∈ B
When A = B, we call it a relation on set A
Relations can be represented using directed graphs, matrices, or arrow diagrams
A relation R on set A is any subset of A × A
Example: If A = {1, 2, 3}, then A × A = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}. A
relation R could be {(1,1), (2,2), (3,3)} representing the "equals" relation.
2. Types of Relations with Examples
Identity Relation:
Definition: R = {(a,a) | a ∈ A} - contains only self-pairs
Example: On A = {1,2,3}, Identity = {(1,1), (2,2), (3,3)}
Property: Each element relates only to itself
Reflexive Relation:
Definition: ∀a ∈ A, (a,a) ∈ R - every element relates to itself
Example: "≤" relation on integers: 5 ≤ 5, 3 ≤ 3, etc.
Graphical: Every vertex has a self-loop
Irreflexive Relation:
Definition: ∀a ∈ A, (a,a) ∉ R - no element relates to itself
Example: "<" relation on integers: 5 ≮ 5, 3 ≮ 3
Graphical: No vertex has a self-loop
Symmetric Relation:
Definition: ∀a,b ∈ A, (a,b) ∈ R ⟹ (b,a) ∈ R
Example: "is sibling of" relation - if A is sibling of B, then B is sibling of A
Graphical: Bidirectional edges between vertices
Antisymmetric Relation:
Definition: ∀a,b ∈ A, (a,b) ∈ R ∧ (b,a) ∈ R ⟹ a = b
Example: "≤" relation - if a ≤ b and b ≤ a, then a = b
Graphical: No bidirectional edges except self-loops
Transitive Relation:
Definition: ∀a,b,c ∈ A, (a,b) ∈ R ∧ (b,c) ∈ R ⟹ (a,c) ∈ R
Example: "ancestor of" relation - if A is ancestor of B and B is ancestor of C, then A is
ancestor of C
Graphical: If there's a path from a to c through b, there must be direct edge from a to c
Equivalence Relation:
Definition: A relation that is reflexive, symmetric, and transitive
Example: "has same remainder when divided by 3" on integers
Properties: Partitions the set into equivalence classes
Partial Order Relation:
Definition: A relation that is reflexive, antisymmetric, and transitive
Example: "subset of" (⊆) relation on sets
Properties: Defines a hierarchy or ordering
Practice Problems
Directed Graph Representations
Problem Analysis:
Relation 1: X={a,b,c}, R={(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,b)}
Relation 2: X={p,q,r}, R={(p,p),(q,q),(r,r),(p,q),(q,p),(q,r)}
Relation 3: X={x,y,z}, R={(x,x),(y,y),(z,z),(x,y),(y,z),(x,z)}
Relation 4: X={m,n,o}, R={(m,m),(n,n),(o,o),(m,n),(n,o),(o,m)}
Relation Properties Analysis
Relation Set Identity Reflexive Irreflexive Symmetric Antisymmetric Transitive Type
X=
R1 NO YES NO YES NO NO General
{a,b,c}
X=
R2 NO YES NO NO NO NO General
{p,q,r}
Relation Set Identity Reflexive Irreflexive Symmetric Antisymmetric Transitive Type
X= Partial
R3 NO YES NO NO YES YES
{x,y,z} Order
X=
R4 NO YES NO NO YES NO General
{m,n,o}
Detailed Analysis:
R1: Reflexive and symmetric but not transitive (missing (a,c)). Forms bidirectional connections but
incomplete transitivity.
R2: Reflexive but neither symmetric (missing (r,q)) nor transitive (missing (p,r)). Has partial
symmetry.
R3: Partial Order Relation - reflexive, antisymmetric, and transitive. Forms a chain: x → y → z
with proper ordering.
R4: Reflexive and antisymmetric but not transitive (creates a cycle m→n→o→m without
completing all transitive pairs).
Graph Theory
Theory Questions
1. What is a graph, and what are the elements of a graph?
Definition: A graph G = (V, E) is a mathematical structure consisting of:
V: A finite set of vertices (nodes or points)
E: A finite set of edges (links or connections between vertices)
Elements of a Graph:
Vertices (V): The fundamental units, often represented as points or circles
Edges (E): Connections between vertices, can be directed (arrows) or undirected (lines)
Adjacency: Two vertices are adjacent if connected by an edge
Incidence: An edge is incident to its endpoint vertices
Types:
Simple Graph: No multiple edges, no self-loops
Multigraph: Multiple edges allowed
Directed Graph (Digraph): Edges have direction
Weighted Graph: Edges have associated weights/costs
2. Degree of a vertex, total degree, and degree sequence
Degree of a Vertex:
Definition: deg(v) = number of edges incident to vertex v
Self-loop: Contributes 2 to the degree
In directed graphs: in-degree (incoming) + out-degree (outgoing)
Total Degree of a Graph:
Definition: Sum of degrees of all vertices
Formula: Σ deg(v) for all v ∈ V
Handshaking Theorem: Total degree = 2 × |E|
Degree Sequence:
Definition: List of vertex degrees in non-increasing order
Example: For degrees 3,2,2,1 → degree sequence is (3,2,2,1)
Graphical Sequence: A sequence that can represent a valid graph
3. Differences among walk, open walk, closed walk, and circuit
Walk:
Definition: Sequence of vertices where consecutive vertices are adjacent
Allows: Repeated vertices and edges
Example: v₁ → v₂ → v₁ → v₃ → v₂
Open Walk:
Definition: Walk where first and last vertices are different
Property: Starting vertex ≠ ending vertex
Closed Walk:
Definition: Walk where first and last vertices are the same
Property: Starting vertex = ending vertex
Minimum length: 1 (self-loop) or 3 (triangle)
Circuit:
Definition: Closed walk with no repeated edges
Property: Each edge traversed at most once
Example: Euler circuit visits every edge exactly once
4. Trail and Path
Trail:
Definition: Walk with no repeated edges
Allows: Repeated vertices but not edges
Example: v₁ → v₂ → v₃ → v₁ → v₄ (if all edges are distinct)
Path:
Definition: Walk with no repeated vertices (and hence no repeated edges)
Property: Each vertex visited at most once
Simple Path: Alternative term for path
5. Distance and Length in a graph
Length:
Definition: Number of edges in a walk/path/trail
Example: Path v₁ → v₂ → v₃ has length 2
Distance:
Definition: Length of shortest path between two vertices
Notation: d(u,v) = distance between vertices u and v
Properties: d(u,v) = 0 if u = v, d(u,v) = ∞ if no path exists
6. Isomorphism and Homomorphism
Graph Isomorphism:
Definition: Bijective mapping f: V₁ → V₂ preserving adjacency
Property: (u,v) ∈ E₁ ⟺ (f(u),f(v)) ∈ E₂
Invariants: Same number of vertices, edges, degree sequence
Graph Homomorphism:
Definition: Mapping f: V₁ → V₂ that preserves adjacency (not necessarily bijective)
Property: (u,v) ∈ E₁ ⟹ (f(u),f(v)) ∈ E₂
Weaker: Allows many-to-one mappings
Practice Problems
Graph Construction and Analysis
Handshaking Theorem Verification
Theorem Statement: In any graph, the sum of all vertex degrees equals twice the number of
edges.
Formula: Σ deg(v) = 2|E|
Verification Results:
Graph Vertices Edges Degree Sum 2×Edges Theorem Verified
Triangle Graph 3 3 6 6 YES
Path Graph (4 vertices) 4 3 6 6 YES
Star Graph (4 vertices) 4 3 6 6 YES
Complete Graph K₄ 4 6 12 12 YES
Degree Sequence Problems
Problem 4: Draw a graph with 4 vertices and degree sequence (1,2,2,2)
Issue: Sum = 1+2+2+2 = 7 (odd number)
Solution: Impossible - handshaking theorem requires even sum
Correction: Modified to (1,2,2,1) with sum = 6 ✓
Problem 5: Draw a graph with 5 vertices and degree sequence (1,2,4,2,1)
Check: Sum = 1+2+4+2+1 = 10 (even) ✓
Construction: Central vertex with degree 4 connected to all others, plus one additional edge
Functions
Theory Questions
1. Domain, Range, and Codomain of a Function
Domain:
Definition: Set of all possible input values (x-values)
Notation: Domain of f: A → B is A
Example: For f(x) = √x, domain is [0,∞)
Codomain:
Definition: Set of all possible output values as declared in function definition
Notation: In f: A → B, codomain is B
Example: f: ℝ → ℝ has codomain ℝ
Range (Image):
Definition: Set of all actual output values
Property: Range ⊆ Codomain
Example: For f(x) = x², range is [0,∞) even if codomain is ℝ
2. Image and Pre-image with Example
Image of an Element:
Definition: For f(a) = b, b is the image of a
Example: If f(3) = 9, then 9 is the image of 3
Pre-image of an Element:
Definition: For f(a) = b, a is a pre-image of b
Multiple pre-images possible: f(2) = 4 and f(-2) = 4, so both 2 and -2 are pre-images of 4
Image of a Set:
Definition: f(S) = {f(s) | s ∈ S}
Example: If S = {1,2,3} and f(x) = x², then f(S) = {1,4,9}
3. Function Types with Examples
One-to-One (Injective):
Definition: f(a) = f(b) ⟹ a = b
Property: Different inputs produce different outputs
Example: f(x) = 2x on ℝ
Many-to-One:
Definition: Multiple inputs can map to same output
Property: Not injective
Example: f(x) = x² (since f(2) = f(-2) = 4)
Onto (Surjective):
Definition: ∀b ∈ B, ∃a ∈ A such that f(a) = b
Property: Every codomain element is an image
Example: f: ℝ → ℝ, f(x) = x³
Into:
Definition: Not onto - some codomain elements are not images
Property: Range ⊊ Codomain
Example: f: ℝ → ℝ, f(x) = x²
Bijective (One-to-One and Onto):
Definition: Both injective and surjective
Property: Perfect pairing between domain and codomain
Example: f: ℝ → ℝ, f(x) = x
Practice Problems
Function Analysis with Arrow Diagrams
Function Type Analysis:
Function a: f:{1,2,3}→{a,b,c,d}, f(1)=a, f(2)=b, f(3)=c
Type: Injective but Into (One-to-One but not Onto)
Reason: Each input maps to different output, but 'd' is unused
Function b: f:{1,2,3,4}→{x,y,z}, f(1)=x, f(2)=x, f(3)=y, f(4)=z
Type: Surjective but Many-to-One (Onto but not One-to-One)
Reason: All codomain elements used, but 'x' has two pre-images
Function c: f:{1,2,3}→{a,b}, f(1)=a, f(2)=b, f(3)=a
Type: Surjective but Many-to-One (Onto but not One-to-One)
Reason: All codomain elements used, but 'a' has two pre-images
Function d: f:{1,2,3}→{p,q,r,s}, f(1)=p, f(2)=q, f(3)=r
Type: Injective but Into (One-to-One but not Onto)
Reason: Each input maps to different output, but 's' is unused
Function Summary Table
Function Domain Codomain Range Injective Surjective Bijective Type
a {1,2,3} {a,b,c,d} {a,b,c} YES NO NO Injective but Into
Surjective but
b {1,2,3,4} {x,y,z} {x,y,z} NO YES NO
Many-to-One
Surjective but
c {1,2,3} {a,b} {a,b} NO YES NO
Many-to-One
d {1,2,3} {p,q,r,s} {p,q,r} YES NO NO Injective but Into
Trees
Theory Questions
1. Different Types of Trees with Examples
Binary Tree:
Definition: Each node has at most 2 children (left and right)
Example: Family tree, expression tree
Properties: Height-balanced for optimal operations
Binary Search Tree (BST):
Definition: Binary tree with ordering property: left < root < right
Example: Database indexing, search algorithms
Operations: Insert, delete, search in O(log n) average time
Complete Binary Tree:
Definition: All levels filled except possibly the last, which fills left-to-right
Example: Binary heap structure
Property: Can be stored efficiently in arrays
Full Binary Tree:
Definition: Every node has either 0 or 2 children
Example: Decision trees
Property: Maximizes number of leaves for given height
Perfect Binary Tree:
Definition: All internal nodes have 2 children, all leaves at same level
Example: Tournament bracket
Property: Has 2^h - 1 nodes for height h
General Tree:
Definition: Each node can have any number of children
Example: File system hierarchy
Representation: Often converted to binary tree for processing
2. Binary Search Tree Construction Process
BST Construction Rules:
1. Start with root: First element becomes root
2. Left insertion: If new element < current node, go left
3. Right insertion: If new element > current node, go right
4. Leaf insertion: Insert at first available position
5. No duplicates: Typically, equal elements are handled by convention
Example Construction: [50, 30, 70, 20, 40, 60, 80]
50 becomes root
30 < 50 → left child of 50
70 > 50 → right child of 50
20 < 50, 20 < 30 → left child of 30
40 < 50, 40 > 30 → right child of 30
Continue pattern...
3. Binary Tree as Hierarchical Data Structure
Justification:
Hierarchical: Clear parent-child relationships with root at top
Structured: Organized levels (depth) create natural hierarchy
Efficient: Logarithmic operations for balanced trees
Recursive: Subtrees are themselves binary trees
Example: Company organizational chart
CEO at root level
VPs at level 1
Directors at level 2
Managers at level 3
Advantages:
Fast search: O(log n) in balanced trees
Ordered traversal: In-order gives sorted sequence
Dynamic: Easy insertion and deletion
4. Tree Traversal Processes
Pre-order Traversal (NLR):
Process: Node → Left subtree → Right subtree
Use: Copying tree structure, prefix expressions
Example: A B D E C F G (for typical binary tree)
In-order Traversal (LNR):
Process: Left subtree → Node → Right subtree
Use: Getting sorted sequence from BST
Property: Gives ascending order for BST
Post-order Traversal (LRN):
Process: Left subtree → Right subtree → Node
Use: Calculating space usage, deleting trees
Property: Children processed before parent
Practice Problems
Binary Search Tree Construction and Traversals
Complete Traversal Analysis:
Sequence Pre-order In-order Post-order
[50, 30, 20, 40, 70, 60, [20, 30, 40, 50, 60, 70, [20, 40, 30, 60, 80, 70,
a: 50,30,70,20,40,60,80
80] 80] 50]
[45, 25, 20, 35, 60, 50, [20, 25, 35, 45, 50, 60, [20, 35, 25, 50, 70, 60,
b: 45,25,60,20,35,50,70
70] 70] 45]
c: 15,10,20,8,12,17,25 [15, 10, 8, 12, 20, 17, 25] [8, 10, 12, 15, 17, 20, 25] [8, 12, 10, 17, 25, 20, 15]
d: [100, 90, 85, 95, 110, 105, [85, 90, 95, 100, 105, 110, [85, 95, 90, 105, 120, 110,
100,90,110,85,95,105,120 120] 120] 100]
Key Observations:
In-order traversal always produces sorted sequence for BST ✓
Pre-order traversal shows construction order (root first)
Post-order traversal processes children before parents (useful for deletion)
All BSTs maintain the fundamental property: left < root < right
BST Properties Verification
✅ All in-order traversals produce sorted sequences
✅ Tree structures follow BST ordering rules
✅ Each subtree maintains BST properties
✅ Efficient search operations possible
Summary
This comprehensive solution covers all four major topics in discrete mathematics:
Key Concepts Mastered:
1. Relational Algebra: Properties analysis, graph representations, classification
2. Graph Theory: Degree sequences, handshaking theorem, graph construction
3. Functions: Type identification, mapping analysis, arrow diagrams
4. Trees: BST construction, traversal algorithms, hierarchical structures
Mathematical Rigor Applied:
Systematic Analysis: Each problem solved with step-by-step methodology
Theoretical Foundation: Complete definitions and property explanations
Visual Representations: Integrated diagrams for all complex structures
Verification: Results confirmed through established theorems and principles
Practical Applications Demonstrated:
Algorithm Implementation: BST construction and traversal algorithms
Problem Solving: Degree sequence analysis and graph construction
Classification Systems: Function type identification and relation categorization
Structural Analysis: Tree properties and hierarchical data organization
All solutions provide complete mathematical foundation suitable for advanced discrete
mathematics coursework while maintaining clarity through visual representations and systematic
analysis approaches.
