UTPA STEM/CBI Courses/Calculus/Networks

Course Title: Discrete Mathematics

Lecture Topic: Networks

Instructor: Paul-Hermann Zieschang

Institution: University of Texas at Brownsville

Backwards Design

Course Objectives

• Primary Objectives- By the next class period students will be able to:
  • give explicitly the definition of a function (with domain, codomain, etc.)
  • give the definition of a network (with source, sink, lower and upper capacity)
  • distinguish the difference between directed and undirected graphs

• Sub Objectives- The objectives will require that students be able to:
  • know the definition of a binary relation
  • see the three different ways to define graphs (pictorial, 0-1-matrix, binary relation)

• Difficulties- Students may have difficulty:
  • changing between the different features of a graph
  • identifying the domain of the lower and upper capacity

• Real-World Contexts- There are many ways that students can use this material in the real-world, such as:

• • transportation problems (railways, air traffic)
  • energy supply (water, electricity)
  • any other kind of logistic problems

Model of Knowledge

• Concept Map
  • Foundations such as binary relations, functions, injectivity, surjectivity
  • Specific relations such as equivalence relations, posets
  • Graphs, weighted graphs
  • Network, source, sink, lower and upper capacity
  • Kirchhoff's Law, flow, value of flow
  • Admissible flow, maximal admissible flow
  • Cut, capacity of a cut
  • Value of a flow ≤ capacity of a cut
  • Convergency, limites, suprema

• Content Priorities
  • Enduring Understanding
    • Kirchhoff's Law for subsets
  • Why is Kirchhoff's Law important in examples?
  • What is the difference between integral valued and real valued weight functions?
  • Important to Do and Know
    • Being familiar with convergence
    • Being familiar with limites
    • Being familiar with suprema
  • Worth Being Familiar with
    • Adding and subtracting real numbers
    • Being familiar with sigma notation
    • Being familiar with set theoretic notation

Assessment of Learning

• Formative Assessment
  • In Class (groups)
    • Calculate the value of given flows and compare with your neighbor
    • Checking if flows are admissible
  • Homework (individual)
    • Check flows if they are admissible
    • Check admissible flows if they are maximal and compare with your neighbor
• Summative Assessment
  • Compare admissible flows
  • Compare maximal admissible flows

Legacy Cycle

OBJECTIVE

By the next class period, students will be able to:

• understand the proof of the Max-Flow Min-Cut Theorem
• appreciate the value of the Max-Flow Min-Cut Theorem

The objectives will require that students be able to:

• understand the notion of an admissible flow
• understand the notion of an maximal admissible flow
• understand the notion of a cut
• understand the notion of the capacity of a cut

THE CHALLENGE

An entertainment park needs to be designed. There are n points of interest (poi), places where visitors stop to be entertained. Paths need to be built between the pois. You are responsible for logistic and security. Design the (physical) topography for the park. One of the logistic challenges is to over the service to as many visitors as possible. A security measure is to avoid too many visitors at the same time at the same poi.

GENERATE IDEAS

Students should discuss which mathematical objects are of interest in order to attack the problem. They also should come up with small examples. In general, students need to be ready to see what the formal (abstract) sceleton of the problem is. They need to be able to distinguish between content and model. (There are many webpages discussing the Max-Flow Min-Cut Theorem.)

MULTIPLE PERSPECTIVES

Students should discuss how to give an interpretation to the points of interest, what logistic and security means in their model, and what flows, cuts, and capacity means.

RESEARCH & REVISE

At this point, students should have identified source, sink, lower capacity, upper capacity, the relevance of Kirchhoff's Law, the meaning of a flow, the value of a flow, admissibility of flows, maximality of flows.

TEST YOUR METTLE

Students design a network and share their design with their neighbors.

GO PUBLIC

Students come up with a network representing an entertainment park with about 6 to 10 points of interest. The model should include a couple of admissible ows, a couple of cuts, show the value of the ows, the capacities of the cuts, and give an example of the Max-Flow Min-Cut Theorem.