$Characterizing the Infinitely Visited Intersections in a Ride-Forever Path on a Directed Graph$

Question

$Characterizing the Infinitely Visited Intersections in a Ride-Forever Path on a Directed Graph$

A neighborhood is a set of one-way and two-way streets connected by intersections. Let our home be the starting point of an infinite route. This could also be seen as a directed graph $G= (V, E)$ with a start vertex s. Let a ride-forever $p$ of $G$ be an infinite sequence of intersections (or vertices), beginning at s and never-ending. Clearly, since $V$ is finite, there must be some vertices that are visited an infinite number of times in $p$.

If a neighborhood has a ride-forever, let $RF(p) \subset V$ be the set of intersections that occur infinitely often in $p$. Explain/Show why $RF(p)$ is a subset of a single strongly connected component of $G$.

Graph Theory Logic

Ava Smith

31

Report

Answer

The answer is accepted.

Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.

Answer 1

Answers can only be viewed under the following conditions:

The questioner was satisfied with and accepted the answer, or
The answer was evaluated as being 100% correct by the judge.

View the answer

Let $v, w \in RF(p)$. All we need to do is to show that there is a path from $v$ to $w$: since we chose an arbitrary pair of vertices, this means that any vertex of $RF(p)$ can be reached by any other vertex of $RF(p)$, thus $RF(p)$ is strongly connected.

Let $N \in \mathbb{N}$ arbitrary. Since $v \in RF(p)$, we visit $v$ an infinite amount of times, so there exists $n > N$ such that after $n$ steps we are on $v$. Since $w$ is also visited an infinite amount of times, there exists $m > n$ such that after $m$ steps we are on $v$. But since $m > n$, there must be a path from $v$ to $w$, otherwise we couldn't get to $w$ after visiting $v$. It follows that $RF(p)$ is strongly connected.

Daniel90

443

$Characterizing the Infinitely Visited Intersections in a Ride-Forever Path on a Directed Graph$

Answer

Related Questions

Search