Graphs have varying degrees of connection. The higher the ratio of edges to vertices, the more connected the graph.
This graph represents a social network; people are vertices and edges are friendships. Ted
is adjacent to Patty
, Ron
, and Alice
because an edge directly connects them.
We use a single line for an edge, but these friendships are bi-directional. Patty
is friends with Ron
and Ron
is friends with Patty
.
A path is vertices which are connected by any number of intermediate edges. The paths from Alice
to Patty
could go Alice
to Ted
to Patty
or, Alice
to Ted
to Ron
to Patty
.
No path exists between Sally
and Ted
. When no path exists between two vertices, a graph is disconnected.
Instructions
What are the paths that connect Ron
to Ted
?
What edge could we add that would change this into a connected graph?