Author:
Kenneth DeMason
Subject:
Mathematics
Material Type:
Lesson
Level:
Academic Lower Division
Provider:
University of Texas at Austin
Tags:
  • D2S2
  • Mindset
  • License:
    Creative Commons Attribution
    Language:
    English
    Media Formats:
    Text/HTML, Video

    Education Standards

    5.4 Universal Towns - Introduction and Ideas

    5.4 Universal Towns - Introduction and Ideas

    Overview

    TCCNS CourseMATH 1332: Contemporary Mathematics
    UT Austin CourseM 302: Introduction to Mathematics

    Introduction

    Overview and Student Objectives

    Lesson Length: 50 minutes

    Overview: This activity expands on Lesson 5.1 by introducing new kinds of graphs -- the complete and directed graphs -- which allow for the study of so-called universal towns.

    Lesson Objectives:

    Students will understand that:

    • The introduction of new kinds of graphs is conducive to the study of new properties, and;
    • In a meta-mathematical sense, the correct framework is paramount to the development of new, tractable problems.

    Students will be able to:

    • Identify complete graphs, directed graphs, and universal towns and;
    • Form simple conjectures through a trial-and-error process. 

    Suggested Resources and Preparation

    Materials and Technology:

    • N/A

    Prerequisite Assumptions: Lesson 5.1: Graphs and Circuits

    Suggested Instructional Plan

    Frame the Activity (5 minutes)

    • Begin by summarizing our survery of graphs in Lessons 5.1 and 5.2, ask students what they've learned about graphs so far.
    • Emphasize how the rigid (as demonstrated by e.g. the Euler characteristic) yet simple structure of graphs is conducive to the study of their properties (e.g. existence of an Euler circuit). You don't need much information to say a lot about a graph.
    • Transition to lesson -- we will focus on a special kind of graph which provides just enough structure to deduce meaningful information.  

    Activity Flow (30 minutes)

    • Instructor is advised to follow the body as presented in subsequent sections. Italicized questions provide opportunities for student engagement.
    • Additional examples may be illuminating. 

    Wrap-up/Transition (15 minutes)

    • Conclude by providing context for the lesson as exposited in the "Thinking Mathematically" section.
    • Time permitting, either have students complete quiz questions in class followed by discussion as a means of formative assessment or guide students through the quiz questions to further solidify understanding.
    • Foreshadow Lesson 5.5 by introducing the homework. 

    Overview

    This activity expands on Lesson 5.1 by introducing new kinds of graphs -- the complete and directed graphs -- which allow for the study of so-called universal towns.

    Lesson Objectives

    You will understand that:

    • The introduction of new kinds of graphs is conducive to the study of new properties, and;
    • In a meta-mathematical sense, the correct framework is paramount to the development of new, tractable problems.

    You will be able to:

    • Identify complete graphs, directed graphs, and universal towns and;
    • Form simple conjectures through a trial-and-error process. 

    Complete and Directed Graphs

    There are some special types of graphs we can study. One such example are the complete graphs. For these graphs every vertex is connected to all others by exactly one edge. So if you pick any two different vertices, there will always be one edge connecting them. The three graphs on the left, pictured below, are complete graphs, whereas the graph on the right is not a complete graph (so, we do not connect vertices to themselves and form loops). 

    Example 1

     four graphs, left is complete graph on three vertices, second is complete graph on four vertices, third is complete graph on five vertices. Fourth graph has three vertices, three edges forming a triangle amongst the vertices, and three loops, one off each vertex.
    The three graphs to the left are all complete graphs, but the graph to the right is not complete because it has loops.

    We can also talk about directed graphs. These are formed by taking any graph, and marking each edge with exactly one arrow. The two graphs on the left, pictured below, are directed graphs whereas the graph on the right is not (one edge is missing an arrow and one edge has two arrows, neither is allowed).

    Example 2

     three graphs. Left graph: three vertices A, B, C. Edges are A to B, B to A, C to B, C to C (a loop). Second graph has three vertices A, B, C. Edges are A to B, C to B, A to C. Third graph has four vertices A, B, C, D. Edges are B to A, C to B, C to D, D to A, A to C. There is also an edge between A and C with two arrows on it, and an undirected edge between B and D.
    The left and center graphs are directed graphs but the right one is not.

    Since any graph can be turned into a directed graph (simply by labelling all the edges with arrows), we can turn complete graphs into directed graphs. The middle graph in the above figure is a so-called complete directed graph since it is both complete and directed. A good way to think about these is to imagine a country where all the towns are vertices and roads are edges. A complete directed graph in this setting means that every pair of towns is connected by a one-way road.

    Terms

    • A complete graph is a graph where every pair of different vertices are connected -- no loops allowed!
    • directed graph is a graph where every edge is assigned exactly one arrow.
    • A complete directed graph is a graph which is both complete and directed.

    Universal Towns

    Let's stick with the analogy that directed graphs represent road systems and imagine any directed graph (so, all the roads are one-way, towns are vertices and roads are edges). Call a town universal if, starting at that town, you can follow the roads and get to any other town. ​​​​​​You are allowed to use as many roads as you need, you can go over them several times, and you can go through the same town multiple times. You do not need to reach every town with one route -- you can restart at the original town, and choose another path. The only thing you cannot do is go against the direction of any road. For example, in the directed graph below town A is a universal town. 

    Example 3

     directed graph with vertices A, B, C, D. Edges are A to B, B to D, A to C, C to D.
    A directed graph where the vertex labelled town A is a universal town.

    Question: Why is town A universal?

    We can start by going to town B, then go to town D. So both town B and town D are accessible from town A. We just need to check if town C is. We cannot travel there from town D though. Starting a new route from town A, we take the other path and reach town C. Hence, all the towns are accessible from town A!

    Terms

    • A universal town is a vertex on a directed graph from which you can travel to every other vertex.

    Thinking Mathematically

    With respect to the connection to the quiz, the first question explicitly has students construct directed graphs for which no universal towns exist, all towns are universal, and exactly one exists. There is no consistent answer you can give to the qustion "How many universal towns are there?" since it is possible that none exist. And even if at least one exists, the fact that you can go from both extremes (exactly one and all) suggests that any amount in-between can occur.

    Throughout this lesson we have defined different some new graphs, e.g. complete directed graphs, and identified special vertices on these graphs, i.e. universal towns. You may be wondering why we're doing any of this. The answer is that math is all about solving problems. Taking a math course is less about the actual math being taught than it is the development of critical thinking and problem solving abilities. In order to solve problems, we need to have problems to start with! From a mathematical point of view the purpose of this lesson is to establish a framework conducive to generating (solvable) problems.

    The quiz questions explore this idea. For example, we can ask "In a given directed graph, how many universal towns does it have?" Question 1 tells us that our framework (a generic directed graph) does not have enough structure to give a single answer. Question 2 tells us that if we work with a complete directed graph, then we can give an answer.

    Quiz Questions

    Solutions

    Question 1

    Left: No universal towns, Center: All three are universal towns, Right: Only one is a universal town.

    Question 2

    Part A

    three directed graphs. Left graph has three vertices A, B, C. Edges are A to B, C to B, A to C. A is circled. Second graph has four vertices A, B, C, D. Edges are A to B, C to B, C to D, D to A, A to C, D to B. A, C, and D are circled. Third graph has five vertices and is a complete graph. All five vertices are circled.

    Part B

    Since it is a conjecture, any answer is acceptable as long as it is backed up by evidence (with their three complete, directed graphs). The "correct" conjecture is "Every complete directed graph has at least one universal town."  

    Teaching Tips

    It may be daunting as a student to write a conjecture, which is why a template is given. Have them complete the first part and identify any universal towns. Conjectures do not necessarily have to be correct (this is sometimes the case in math!), so encourage them to describe their results without worrying if it is actually correct in general. 

     

    Question 1

     left graph: three vertices A, B, C. Two edges, A directed to B and C directed to B. Second graph three vertices A, B, C. Three edges A directed to B, B directed to C, C directed to A. Third graph two vertices. One edge A directed to B.

    How many universal towns do each of the above graphs have?

    Question 2

    Draw three complete directed graphs, one with three vertices, one with four, and one with five.

    Part A

    Can you find any universal towns?

    Part B

    Write a conjecture of the form "_____ complete directed graph has _____ universal town(s)" (example words for the first blank include "every, none, some", for the second blank include "none, at least one, many," etc.)

    Homework Questions

    Solutions

    Question 1

    Yes, you can create new universal towns.

    Question 2

    Any answer is fine so long as they counted correctly. You can make every universal town universal.

    Question 3

    Again, any answer is fine. The point is for the student to create a conjecture. In reality you only need at most one road change to make all towns universal.

    Three directed graphs, left graph has three vertices A, B, C. Edges are B to A, C to B, A to C. B to A has been switched. Second graph has four vertices A, B, C, D. Edges are A to B, C to B, C to D, D to A, A to C, B to D. B to D has been switched. Third graph is a complete graph on five vertices. All towns were universal so no edges were switched.
    Thickened edges indicate changed directions.

    Teaching Tips

    The first part of this question is basically asking "is this even a good idea?" It could be that by changing road directions, you destroy previous universal towns at the same time as creating new ones, and there is zero overall effect. It actually turns out to be a good idea, and it should be pretty intuitive which directions they need to change. In particular, any town which has a road leading to a universal town is universal. 

    Answers for the second and third parts may vary depending on what students do. The point is they should try to increase the number of universal towns as much as possible (say they get half of them to be universal). Now, while doing that they've been changing road directions. Maybe you can do better, and get the same number of universal towns with less road changes. In fact you can, and you only need one change. 

    A road system like this -- formed from a directed complete graph -- is awful since there are some towns that you might not be able to even leave! An engineer is hired to try and fix this issue. First they think about adding new roads, but that's expensive. The engineer comes up with another idea -- why not just change the directions on some of the roads and see what happens. Try this yourself with your example graphs from the Quiz questions. Then, answer the following questions:

    Question 1

    By changing road directions, are you able to create new universal towns? 

    Question 2

    How many universal towns were you able to create? Try to maximize this number. (e.g., can you ensure that there is at least one universal town? About half are universal? All are universal?) 

    Question 3

    How many road directions did you need to change in Question 2? Can you minimize this number? Write your results.