Question

Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________

(a) A’ ⊂ A and R’ = R ∩ (A’ x A’)

(b) A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)

(c) R’ = R ∩ (A’ x A’)

(d) A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)

The question was posed to me at a job interview.

My enquiry is from Graphs topic in section Graphs of Discrete Mathematics

Answer 1

Correct answer is (a) A’ ⊂ A and R’ = R ∩ (A’ x A’)

The best explanation: A directed graph or digraph is an ordered pair D<A, R> where A(is a set of nodes of D) is a set and R(the elements of R are the arcs of D) is a binary relation on A. The relation R is called the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’  D, D’ is a proper subgraph of D.