We will be using the rest of the course to provide an overview of some of the most important topics in graph theory. We began discussing sections 10.1 and 10.2 last Tuesday, but they were not previously listed in Pre-reading. Please read sections 10.1–10.5. Section 10.1 (Graphs and Graph Models). Graphs will form the basis of many computational problems throughout your studies. Here we introduce some of the terminology associated with the subject. The table on page 676 lists several variations of graphs, and section 10.1.1 describes many instances where graphs occur in reall applications. When you’re reading the applications, try to think about how the choices in table 1 affect the usefulness of the graph.
Section 10.2 (Graph Terminology and Special Types of Graphs). In order to properly discuss graphs, we give names to several features that can apply to parts of a graph. The ideas of adjacency, neighbours, neighbourhoods, and vertex degree should all be added to your list of definitions. We discuss several useful families of graphs, including complete graphs, cycles, and cubes, so we can have a basis for later examples. Hall’s matching theorem describes the solution to one of the most common problems arising for bipartite graphs.
Section 10.3 (Representing Graphs and Graph Isomorphism). The problem of graph isomorphism is how to tell when two graphs encoded the same information. A complete answer to this problem is beyond the scope of this course, but an initial discussion brings us to the idea of how to represent graphs, so that we can describe them to other people.
Section 10.4 (Connectivity). Graphs are often used to describe networks around which goods (or information) are transported. The question of connectivity deals with figuring out when it is possible to get from an initial vertex to a desired destination.
Section 10.5 (Euler and Hamilton Paths). Given a graph, we sometimes want to know whether it is possible to visit all parts of the graph efficiently. Euler paths correspond to the situation where we desire to visit every edge and harken back to some of the earliest applications of graph theory, while Hamilton paths correspond to the situation where it is desireable to efficiently visit every vertex. Efficiently searching for Hamilton Paths forms the basis of a wide range of applications in Computer Science
Suppose that a travel agency hires you to help people find the best way to travel by air from one city to another. You think that some form of graph might be useful to represent the data you need for this project.
(a) Should the vertices of your graph be airports or cities? What requirements by the travel agency could make you change your mind?
<aside> 💡 The vertices of the graph should be airports, not cities. This is because airports are the physical locations where flights depart from and arrive at. If we choose cities as vertices, we may have multiple airports in the same city, and this would make it harder to represent flight routes between airports.
However, if the travel agency requires information about travel between cities and not just airports, we may need to add additional vertices to the graph to represent city-to-city connections.
</aside>
(b) Should the edges of your graph be directed or undirected? Explain your choice.
<aside> 💡 The edges of the graph should be directed. This is because flights are one-way and do not necessarily have a return route. Directed edges allow us to represent this fact.
</aside>
(c) List some questions you could answer for the agency if you do not record parallel edges in your graph?
<aside> 💡 What is the shortest route from one airport to another?
What is the longest route from one airport to another?
</aside>
(d) List some questions you could only answer if your graph does have parallel edges.
<aside>
💡 How many direct flights are there from one airport to another?
(e) Should your graph be finite or infinite?
<aside> 💡 The graph should be finite, as there are a finite number of airports and flight routes.
</aside>
This questions considers some of the properties of cube graphs (see page 689 for terminology).