Skip to main content

Chapter 12
Moving through graphs

We have some basic concepts and terminology now, but it is important to remember that graphs are models of networks. Networks are all about moving things around, whether those things are cars, data, or whatever. So if graphs are going to be useful models, routes in the network need to correspond to routes in the graph, and we need to be able to describe these routes, and to learn about them.

Summary.

  • many definitions and results about graphs can be generalised to the context of digraphs.

  • trees can be characterised in a variety of ways.

  • Important definitions:

    • digraph

    • arc

    • walk

    • length of a walk

    • connected

    • connected component

    • path, cycle

    • tree, forest, leaf

    • automorphism

  • Notation:

    • \(\displaystyle P_n\)

    • \(\displaystyle C_n\)