(a) Let G = (V, E) be the directed graph where V = {1, 2, 3, 4,...
Question:
(i) How many edges are there for this graph?
(ii) Four of the directed paths in G from 1 to 7 may be given as:
1) (1, 7);
2) (1, 3), (3, 5), (5, 6), (6, 7);
3) (1, 2), (2, 3), (3, 7); and
4) (1, 4), (4, 7).
How many directed paths (in total) exist in G from 1 to 7?
(b) Now let n ∈ Z+ where n ≥ 2, and consider the directed graph G = (V, E) with V = {1, 2, 3, ..., n} and E = {(i, j)| 1 ≤ i ≤ j ≤ n}.
(i) Determine |E|.
(ii) How many directed paths exist in G from 1 to n?
(iii) If a, b ∈ Z+ with 1 ≤ a ≤ b ≤ n, how many directed paths exist in G from a to b?
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Question Posted: