Bifalgorithm post · Brisk · Chapter 1

What are the two notions of connectedness for directed graphs?

What are the two notions of connectedness for directed graphs? (Brisk · Chapter 1) — "Depends on what we mean. There are two different notions of “connectednes…

Ideas in this flowchart

  • Connectedness in directed graphs depends on the definition used.
  • There are two different notions of connectedness.
  • Strong connectedness
  • Every vertex must be reachable from every other vertex by following the arrows in their specified directions.
  • The graph is not strongly connected because H cannot be reached from J.
  • Weak connectedness
  • Weak connectedness ignores arrowheads and treats the graph as undirected.
  • Under this definition, the graph is connected.
Bifalgorithm
Sign up
Feed/

What are the two notions of connectedness for directed graphs?

Channel

Brisk

1 page

U
USR292600b83e2a
Ebook3w

"Depends on what we mean. There are two different notions of “connectedness” for directed graphs. One is strongly connected, which means every vertex is reachable from any other by following the arrows in their specified directions. By that definition, this graph is not connected: there’s no way to get to H from J, for example. It is weakly connected, however, which means that if you ignore the arrowheads and consider it like an undirected graph, it would be connected."

Flowchart preview
Series cover
👍
0
0 comments0 shares

Sign in to view and post comments.