Mathematical Foundations of Computer Science by Satyanarayana Bhavanari; Kumar T. V. Pradeep; Shaw Shaik Mohiddin

Author:Satyanarayana, Bhavanari; Kumar, T. V. Pradeep; Shaw, Shaik Mohiddin
Language: eng
Format: epub
Publisher: Taylor & Francis Group
Published: 2020-07-15T00:00:00+00:00

(En = E, E, E, … E, the composition of n copies of E).

Proof: Let G = (V, E) be a diagraph.

Now we shall prove the theorem by mathematical induction on ‘n’.

Case I: For n = 1

Then En = E

By the definition of path that (u, v) ∈ E if there is a path of length 1, from u to v. Since a path of length 1 is an edge of G.

Case II: For n > 1.

Assume that the theorem is true for n−1. Now we shall prove the theorem into two parts.

Part I: Let (v0, v1), (v1, v2), …, (vn−1, vn) be a directed path from v0 to vn.

Then (v0, vn−1) ∈ En−1, (by induction).

By the definition En = En−1, E and (vn−1, vn) ∈ E so that (v0, vn) ∈ En.

Part II: Suppose (v0, vn) ∈ En.

Since En = En−1.E, there exists some vn−1 such that (v0, vn−1) ∈ En−1 and (vn−1, vn) ∈ E.

By the inductive hypothesis, there is a directed path (v0, v1), (v1, v2), …, (vn−2, vn−1) of length n−1, from v0 to vn−1.

Adding (vn−1, vn) to this path gives the path of length n.

The proof is complete.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.