In a directed graph, node A has no self-loop and no directed path from A back to A (no cycles involving A). Which statement is correct?
AA R* A is false, because there is no self-loop at A
BA R⁺ A is true, because every node trivially reaches itself
CA R* A is true, because R* includes zero-step reachability via the identity relation
DBoth A R* A and A R⁺ A are false, because there is no directed path from A to A
R* is defined to include the identity relation (the diagonal), so a R* a is always true for every element — even when no self-loop or cycle exists. R* captures 'reachable in zero or more steps,' and zero steps trivially connects every element to itself. R⁺ by contrast captures 'one or more steps,' so A R⁺ A is only true if there is a directed cycle back to A.
Question 2 Multiple Choice
A compiler models variable influence: the relation holds when variable x influences variable y. The system needs x to trivially influence itself (any assignment to x affects x). Should the compiler use R⁺ or R* to represent this influence relation?
AR⁺, because a genuine one-step connection from x to itself must be established first
BR*, because it includes the identity relation and thus captures zero-step self-influence as a built-in property
CEither — they produce the same result when self-loops are explicitly added to the input relation
DNeither — variable influence is not a closure relation in the mathematical sense
R* is the right choice because it includes the diagonal (identity) by definition, making x R* x true for every x without requiring an explicit self-loop in the input relation. R⁺ would require that a cycle exist back to x for self-influence to hold, which is the wrong model here. The point of R* is precisely that 'reaching yourself in zero steps' is always trivially true.
Question 3 True / False
In R*, two elements a and b are related if and mainly if there exists a directed path of one or more edges from a to b.
TTrue
FFalse
Answer: False
R* requires zero or more steps, not one or more. The identity relation (zero steps) is included, so a R* a is always true even with no edges. R⁺ is the 'one or more' closure. This is the essential distinction: R* = R⁰ ∪ R¹ ∪ R² ∪ …, where R⁰ is the identity relation, while R⁺ = R¹ ∪ R² ∪ …
Question 4 True / False
For an acyclic directed graph, R* and R⁺ produce identical results, because there are no cycles to create self-loops in either closure.
TTrue
FFalse
Answer: False
They differ by the diagonal (identity relation). In an acyclic graph, R⁺ contains no self-loops because there are no cycles returning to any node. But R* always contains a R* a for every element a by definition — the identity relation is included regardless of graph structure. So even in a completely acyclic graph, R* has self-loops for every node and R⁺ has none. The difference is not about cycles but about whether zero-step reachability is included.
Question 5 Short Answer
In one or two sentences, explain why 'zero or more steps' correctly describes R* but not R⁺, and give a context where this distinction matters.
Think about your answer, then reveal below.
Model answer: R⁺ requires at least one edge traversal, so a R⁺ a holds only if there is a cycle back to a; R* adds the identity relation (zero steps), making a R* a always true for every element. This matters in compiler variable-influence analysis or reachability queries where you need 'a can reach b' to include the trivial case a = b without requiring an actual edge.
The formal expression is clean: R* = R⁰ ∪ R¹ ∪ R² ∪ … and R⁺ = R¹ ∪ R² ∪ …, where R⁰ is the identity. The practical choice is: use R* when 'a reaches itself trivially' should be true; use R⁺ when you require at least one genuine step.