Task number: 3838

The relation “an oriented path from \( u \) to \( v \) exists” on the vertices of the following oriented graph is

  • symmetric but not transitive;
  • transitive but not symmetric;
  • symmetric and transitive.
  • Solution

    In the above graph, there is an oriented path between every two vertices, so both properties are satisfied.

    In the general case, transitivity always applies (by concatenation ob paths and omitting unnecessary subpaths), byt symmetry may not hold.

  • Answer

    The correct answer is c.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email