We will finish the course with a whirlwind tour of some of the kinds of problems that can be modelled with graphs. Note that sections 10.4 and 10.5 were included in last week’s reading, but will be discussed in this week’s lectures. Review them again if you did not get to them last week. The only new reading for this week is section 11.1, in which we look at some of the special properties of a class of graphs known as trees.
We previously encountered trees as an example of recursive structures in chapter 5, but now we return to them as a special kind of graph. Trees are connected graphs without any circuits. This lack of circuits makes them particularly well suited as the basis for several important data structures, and you will reencounter trees several times before you finish studying computer science.
We will use the topic of graph coloring (which generalizes the idea of a bipartition) as an opportunity to review several of the concepts of propositional logic and equivalence relations.
We will incorporate a brief discussion of spanning trees into our discussion of connectivity.
Give an example of a graph that has a Hamilton circuit, but does not have an Euler circuit.
Give an example of a graph that has an Euler circuit, but does not have a Hamilton circuit.
Give an example of a graph that is connected, but is not 2-edge connected.
Give an example of a graph that has an Euler path, but does not have an Euler circuit.
