Skip to main content
Engineering LibreTexts

9.4: Walk Relations

  • Page ID
    48347
    • Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
    • Google and Massachusetts Institute of Technology via MIT OpenCourseWare
    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    A basic question about a digraph is whether there is a way to get from one particular vertex to another. So for any digraph, \(G\), we are interested in a binary relation, \(G^*\), called the walk relation on \(V(G)\) where

    \[u G^* v ::= \text{ there is a walk in }G \text{ from } u \text{ to } v. \]

    Similarly, there is a positive walk relation

    \[u G^+ v ::= \text{ there is a positive length walk in }G \text{ from } u \text{ to } v. \]

    Definition \(\PageIndex{1}\)

    When there is a walk from vertex \(v\) to vertex \(w\), we say that \(w\) is reachable from \(v\), or equivalently, that \(v\) is connected to \(w\).

    Composition of Relations

    There is a simple way to extend composition of functions to composition of relations, and this gives another way to talk about walks and paths in digraphs.

    Definition \(\PageIndex{2}\)

    Let \(R : B \rightarrow C\) and \(S : A \rightarrow B\) be binary relations. Then the composition of \(R\) with \(S\) is the binary relation \((R \circ S) : A \rightarrow C\) defined by the rule

    \[a \circ (R \circ S) c ::= \exists b \in B. (a S b) \text{ AND } (b R c).\]

    This agrees with the Definition 4.3.1 of composition in the special case when \(R\) and \(S\) are functions.2

    Remembering that a digraph is a binary relation on its vertices, it makes sense to compose a digraph \(G\) with itself. Then if we let \(G^n\) denote the composition of \(G\) with itself \(n\) times, it’s easy to check (see Problem 9.9) that \(G^n\) is the length-\(n\) walk relation:

    \[\nonumber a G^n b \text{ iff there is a length } n \text{ walk in } G \text{ from } a \text{ to }b.\]

    This even works for \(n = 0\), with the usual convention that \(G^0\) is the identity relation \(Id_{V(G)}\) on the set of vertices.3 Since there is a walk iff there is a path, and every path is of length at most \(|V(G)| - 1\), we now have4

    \[G^* = G^0 \cup G^1 \cup G^2 \cup \ldots \cup G^{|V(G) - 1|} = (G \cup G^0)^{|V(G)| - 1}. \]

    The final equality points to the use of repeated squaring as a way to compute \(G^*\) with \(\log n\) rather than \(n - 1\) compositions of relations.

    2The reversal of the order of \(R\) and \(S\) in (9.8) is not a typo. This is so that relational composition generalizes function composition. The value of function \(f\) composed with function \(g\) at an argument, \(x\), is \(f(g(x))\). So in the composition, \(f \circ g\), the function \(g\) is applied first.


    This page titled 9.4: Walk Relations is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer (MIT OpenCourseWare) .