12: Moving Through Graphs
- Page ID
- 60132
\( \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}}\)
- 12.1: Directed Graphs
- Some networks include connections that only allow travel in one direction. These can be modeled using directed graphs. When drawing a digraph, we draw an arrow on each arc so that it points from the first vertex of the ordered pair to the second vertex. Like multigraphs, we will not study digraphs in this course, but you should be aware of the basic definition. Many of the results we will cover in this course, generalise to the context of digraphs.
- 12.2: Walks and Connectedness
- Graphs can be connected or disconnected. Intuitively, this corresponds to the network being connected or disconnected – is it possible to travel from any node to any other node? When a graph (or network) is disconnected, it has broken down into some number of separate connected components - the pieces that still are connected. Since this is mathematics, we require more formal definitions, to ensure that the meanings are not open to misunderstanding.
- 12.3: Paths and Cycles
- Recall the definition of a walk. As we saw in Example 12.2.1, the vertices and edges in a walk do not need to be distinct. There are many circumstances under which we might not want to allow edges or vertices to be re-visited. Efficiency is one possible reason for this. We have a special name for a walk that does not allow vertices to be re-visited.
- 12.4: Trees
- A special class of graphs that arise often in graph theory, is the class of trees. If a mathematician suspects that something is true for all graphs, one of the first families of graphs for which s/he will probably try to prove it, is the family of trees because their strong structure makes them much easier to work with than many other families of graphs.
- 12.5: Summary
- This page contains the summary of the topics covered in Chapter 12.