Ex.
<aside> 🔖 Def.
A path of length $n$ from $u$ to $v$ in an undirected graph is a sequence of $n$ edges ($e_1,e_2,e_3,…,e_n$) together with a list of $n+1$ vertices ($u=v_0,v_1,v_2,…,v_n$)
</aside>
such that the ends of $e_i$ are $v_{i-1}$ and $v_i$.
Such a path describes how to get from $u$ to $v$.
We previously discussed paths in directed graphs when talking about transitive relations.(there’s an added condition that $v_i$ is at the end of $e_1$ and $v_{i-1}$ is at the start)
A path is simple if no edge is used more than once.
In some texts, the term path also means no vertex is repeated.
<aside> 🔖 Def.
A graph is connected if there is a path from $u$ to $v$ for every pair of vertices $u$ and $v$.
i.e We can always get from here to there.
</aside>
<aside> 🔖 Theorem.
If a graph is connected, then it is also connected if we only allow simple paths, and also if we don’t allow repeated vertices on our paths.
</aside>
Observation
Say $uRv$($R$ depends on a graph) iff there is a path from $u$ to $v$ in our graph.
On the assignment $9B$, you show $R$ is an equivalence relation.
The equivalence classes of this relation describe the components of the graph.
A component can also be described as a connected subgraph that is not a proper subgraph of any other connected subgraph.
Ex.
There is an algorithmic way to identify components:
One such way is to build a spanning tree.
There can be chosen with various properties, depending on what other questions we want to be able to answer.
Ex.
Start with the smallest labelled vertex we haven’t visited and find all its neighbours.
$1,2,9,10,6$ unvisited
Then continue with the neighbours of each vertex in the order they were odded.
Repeat:
