Graph Isomorphism and Minimum Spanning Tree (Kruskal's Algorithm)

STEP 1 - EXTRACT: Given Data

Part 1: Define graph isomorphism with an example. [5 marks]

Part 2: Generate the MST using Kruskal's algorithm "from following graph." [5 marks]

Missing data: The actual graph (vertices, edges, and edge weights) referenced by "following graph" is not provided in the text. No image, adjacency list, or weight matrix was included. Therefore the exact numeric MST for the intended graph cannot be computed.

I will fully answer Part 1 (self-contained) and, for Part 2, present the correct Kruskal procedure applied to a clearly labelled representative graph, explicitly flagged as illustrative since the real graph is unreadable/absent.

STEP 2 - SOLVE

(a) Graph Isomorphism

Definition

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping)

$$f : V_1 \rightarrow V_2$$

such that for all vertices $u, v \in V_1$:

$$(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$$

Informally, two graphs are isomorphic if one can be obtained from the other by relabelling the vertices, preserving the adjacency structure. We write $G_1 \cong G_2$.

Necessary Conditions

These are necessary but not sufficient.

Example

Graph $G_1$: $V_1 = {1,2,3,4}$, $E_1 = {(1,2),(2,3),(3,4),(4,1)}$

Graph $G_2$: $V_2 = {a,b,c,d}$, $E_2 = {(a,b),(b,d),(d,c),(c,a)}$

Both are 4-cycles with degree sequence ${2,2,2,2}$.

Bijection: $f(1)=a,\ f(2)=b,\ f(3)=d,\ f(4)=c$

Verification:

• $(1,2) \to (a,b)$ ✓
• $(2,3) \to (b,d)$ ✓
• $(3,4) \to (d,c)$ ✓
• $(4,1) \to (c,a)$ ✓

All edges map to edges, so $G_1 \cong G_2$.

(b) MST using Kruskal's Algorithm

Note: The specific graph in the question was not available in the provided text. The following uses a clearly labelled representative graph to demonstrate the method. Substitute the actual edge weights if the graph is available.

Algorithm

1. Sort all edges in non-decreasing order of weight.
2. Pick the smallest edge; add it to the MST if it does not create a cycle (use union-find).
3. Repeat until the MST contains $V - 1$ edges.

Illustrative Graph

Vertices ${A,B,C,D,E,F}$ with edges:

Sorted Edges

$$A\text{-}F(2),\ D\text{-}E(2),\ C\text{-}D(3),\ A\text{-}B(4),\ B\text{-}F(5),\ B\text{-}C(6),\ B\text{-}E(7),\ C\text{-}F(8),\ E\text{-}F(9)$$

Selection

Now MST has $V-1 = 5$ edges. Stop.

Result

MST edges: A-F, D-E, C-D, A-B, B-C

$$\text{Total weight} = 2 + 2 + 3 + 4 + 6 = 17$$

        A ---4--- B ---6--- C ---3--- D ---2--- E
        |
        2
        |
        F

Minimum Spanning Tree total cost = 17 (for the illustrative graph).

For the illustrative graph used here the minimum spanning tree total is 17. The genuine limitation is that the actual exam graph was not provided, so repeat the same selection steps on the graph printed on your paper.

Uses of Randomized Algorithms [2 marks]

A randomized algorithm uses random choices during its execution to influence its behavior. Common uses include:

1. Primality Testing - Fast probabilistic tests such as Miller-Rabin and Solovay-Strassen for very large numbers.
2. Randomized Quicksort - Random pivot selection gives expected $O(n\log n)$ time and avoids adversarial worst cases.
3. Cryptography - Generating random keys, nonces, salts, and initialization vectors.
4. Approximation / Monte Carlo Methods - Quick approximate solutions to hard (NP-hard) or numerical problems.
5. Load Balancing / Distributed Systems - Randomly assigning tasks to balance load.
6. Hashing - Universal and cryptographic hashing to reduce collisions.

Solving the Recurrence Relation [8 marks]

Given data

• Recurrence: $a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}$
• $a_0 = 2,\quad a_1 = 5,\quad a_2 = 15$

Step 1: Characteristic Equation

Assume $a_n = r^n$: $$r^3 = 6r^2 - 11r + 6$$ $$r^3 - 6r^2 + 11r - 6 = 0$$

Step 2: Roots

Test $r=1$: $1 - 6 + 11 - 6 = 0$ ✓

$$r^3 - 6r^2 + 11r - 6 = (r-1)(r^2 - 5r + 6) = (r-1)(r-2)(r-3)$$

Roots: $r_1 = 1,\ r_2 = 2,\ r_3 = 3$ (distinct).

Step 3: General Solution

$$a_n = A(1)^n + B(2)^n + C(3)^n = A + B\cdot 2^n + C\cdot 3^n$$

Step 4: Apply Initial Conditions

$$n=0:\ A + B + C = 2 \quad (1)$$ $$n=1:\ A + 2B + 3C = 5 \quad (2)$$ $$n=2:\ A + 4B + 9C = 15 \quad (3)$$

Step 5: Solve

$(2)-(1):\ B + 2C = 3 \quad (4)$ $(3)-(2):\ 2B + 6C = 10 \Rightarrow B + 3C = 5 \quad (5)$ $(5)-(4):\ C = 2$ From $(4):\ B = 3 - 4 = -1$ From $(1):\ A = 2 - (-1) - 2 = 1$

So $A=1,\ B=-1,\ C=2$.

Final Answer

$$\boxed{a_n = 1 - 2^n + 2\cdot 3^n}$$

Verification

Boolean Function, Exponential Function, Partial Ordering & Computer Representation of Sets

STEP 1 - EXTRACT (Given Data)

• Universal set: $U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ (10 elements)
• Required definitions: Boolean function, exponential function, partial ordering.
• Sets to represent as bit strings over $U$:
  • (a) even numbers
  • (b) multiples of 5
  • (c) numbers greater than 7
  • (d) prime numbers

All data present.

STEP 2 - SOLVE

(a) Definitions

Boolean Function

A Boolean function of $n$ variables is a function

$$f: {0,1}^n \rightarrow {0,1}$$

that assigns to each combination of $n$ Boolean inputs (0 or 1) a single output value in ${0,1}$. It is built from the operations AND ($\cdot$), OR ($+$), and complement ($\overline{\phantom{x}}$).

Example: $f(x,y,z) = x\cdot y + \overline{z}$.

Exponential Function

An exponential function has the form

$$f(x) = a^x, \quad a > 0,\ a \neq 1$$

where $a$ is the base and $x$ the exponent. Domain $=\mathbb{R}$, range $=(0,\infty)$.

Example: $f(x)=2^x$; occurs in complexity analysis such as $O(2^n)$.

Partial Ordering

A relation $R$ on a set $S$ is a partial ordering if it is:

The pair $(S,R)$ is a partially ordered set (poset).

Example: $\leq$ on $\mathbb{Z}$, and $\subseteq$ on a power set.

(b) Computer Representation of Sets

Convention: Order the elements of $U$ as $0,1,2,3,4,5,6,7,8,9$. Bit = 1 if the element is present, 0 otherwise.

$$\text{Positions: } 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9$$

(a) Even numbers

$A = {0,2,4,6,8}$

$$\boxed{1010101010}$$

(b) Multiples of 5

$B = {0,5}$

$$\boxed{1000010000}$$

(c) Numbers greater than 7

$C = {8,9}$

$$\boxed{0000000011}$$

(d) Prime numbers

$D = {2,3,5,7}$ (1 is not prime)

$$\boxed{0011010100}$$

Summary

Proposition and Predicate Logic

Definition of Proposition

A proposition is a declarative statement that is either true or false, but not both simultaneously. It has a definite truth value (T or F).

Examples:

• "2 + 2 = 4" (True proposition)
• "The sky is green" (False proposition)
• "Close the door!" (NOT a proposition - it is a command)

Converting Sentences to Predicate Logic

(a) Some kind hearted people do still exist.

Identify the components:

• Let K(x) = "x is kind hearted"
• Let E(x) = "x still exists" (or "x is a person who still exists")
• The quantifier "Some" maps to the Existential Quantifier (∃)

Predicate Form:

$$\exists x ; [K(x) \land E(x)]$$

Reading: "There exists some x such that x is kind hearted and x still exists."

(b) Students who study hard and do the homework get good marks in exam.

Identify the components:

• Let S(x) = "x is a student"
• Let H(x) = "x studies hard"
• Let D(x) = "x does the homework"
• Let G(x) = "x gets good marks in exam"
• The quantifier "All/Every" (implied) maps to the Universal Quantifier (∀)

Predicate Form:

$$\forall x ; [S(x) \land H(x) \land D(x) \Rightarrow G(x)]$$

Reading: "For all x, if x is a student and x studies hard and x does the homework, then x gets good marks in the exam."

Note: The existential quantifier (∃) uses conjunction (∧) with its conditions, while the universal quantifier (∀) typically uses implication (⇒) to express conditional relationships.

Proof by Mathematical Induction

Claim

$$1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2$$

This is a perfect square for all positive integers $n$.

Step 1: Base Case ($n = 1$)

LHS: $1^3 = 1$

RHS: $\left[\frac{1(1+1)}{2}\right]^2 = \left[\frac{1 \cdot 2}{2}\right]^2 = [1]^2 = 1$

Since LHS $=$ RHS $= 1$, the base case holds. $\checkmark$

Step 2: Inductive Hypothesis

Assume the statement is true for $n = k$, i.e., assume:

$$1^3 + 2^3 + 3^3 + \cdots + k^3 = \left[\frac{k(k+1)}{2}\right]^2$$

Step 3: Inductive Step

We must prove the statement holds for $n = k + 1$, i.e., we must show:

$$1^3 + 2^3 + \cdots + k^3 + (k+1)^3 = \left[\frac{(k+1)(k+2)}{2}\right]^2$$

Starting from the LHS:

$$1^3 + 2^3 + \cdots + k^3 + (k+1)^3$$

Applying the inductive hypothesis:

$$= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3$$

$$= \frac{k^2(k+1)^2}{4} + (k+1)^3$$

Factor out $(k+1)^2$:

$$= (k+1)^2 \left[\frac{k^2}{4} + (k+1)\right]$$

$$= (k+1)^2 \left[\frac{k^2 + 4(k+1)}{4}\right]$$

$$= (k+1)^2 \left[\frac{k^2 + 4k + 4}{4}\right]$$

$$= (k+1)^2 \cdot \frac{(k+2)^2}{4}$$

$$= \frac{(k+1)^2(k+2)^2}{4}$$

$$= \left[\frac{(k+1)(k+2)}{2}\right]^2$$

This is exactly the RHS for $n = k+1$. $\checkmark$

Conclusion

By the Principle of Mathematical Induction, the formula holds for all positive integers $n$:

$$\boxed{1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2}$$

Since $\dfrac{n(n+1)}{2}$ is always a positive integer (as $n(n+1)$ is always even), the sum is always a perfect square. $\blacksquare$