CS 39: Symmetry & Topology
Lecture #7 -- Mon. 3/18, 2019.

PREVIOUS <- - - - > CS 39R HOME < - - - - > CURRENT < - - - - > NEXT

Preparation:

Prepare the one-page, double-sided fact sheet.
Give me two proposals of what you might want to do as a course project.

Warm-up:

Discuss your genus-2 surface with your neighbors.
What is its Euler Characteristic ?

Try to settle fundamental issues that are still unclear.

Discuss solutions to the last Homework on Surface Classification

Introduction to Graph Theory

Elements of a graph (G):
a set of Vertices (Points, Nodes): V(G) = {U, V, W, X, Y, Z ...}. [these are their names].
a set of Edges (Links, Connections between Vertices): E(G) = {(U,V), (V,W), (X,Y), (X,Z) ... }. [defined by their end points].
-- Loops are OK, e.g.: (U,U).
-- Multiple edges between vertices are OK, e.g.: {... (V,W), (V,W), ...}.
{Typically NOT OK: isolated vertices; free floating lines not anchored by nodes.}

What could be represented by the vertices/nodes and by the edges/links ?
Think of a few things in your domain of interest where a graph-representation may be useful.

Some Definitions:

A planar graph is one that can be drawn crossing-free into the plane.

A complete graph, K#, has exactly one edge between every possible pair of vertices.
K2 has 1 edge; K3 has 3 edges; K4 has 6 edges; K5 has 10 edges; K6 has 15 edges; Kn has n(n-1)/2 edges ...
Which of these are planar?

An Illustrating Exercise:

Pat, Bob, and Alice live in three adjacent locations as indicated at the bottom of this slide.

They all have spiffy cars and use them to go to Safeway, Blockbuster, and the local gas station.

They don’t like each other and therefore want their individual private roads to the three shopping places.
And these roads must not cross each other!

Draw a possible road map!

The graph that you are trying to construct here is called the "Utility Graph":
Given 3 utility sources {water, gas, electricity}; the owners of 3 houses in a district with under-grounding
want individual (crossing-free) trenches from the 3 utilities to their homes.
It is also known as the "Bipartite Graph K_3,3"

Preparing for your Project Presentation (about 4 weeks from now):

I will collect your one-line proposals and give you feedback by e-mail.
With this feedback start planning the outline of a brief story that you think will be of interest to your audience -- and fits into 15 minutes!
Prepare a 1-minute summary of the main point(s) of your presentation.
Ask yourself: What does the audience already know, and what do you need to tell them, so that they can understand your story?
What supporting material can make the presentation more interesting -- or easier to understand?

Structure your presentation:
Introduction: Outline the main focal point of your presentation.
Main Part: Tell your story; use supporting props.
Wrap Up: Repeat the main point(s) that you want your audience to remember.

Knowing that you are well prepared: be confident in your presentation.
Speak slowly, loudly, clearly!

THE QUIZ ! Chart of Cylinder Symmetries

New Homework Assignment:

Due: Monday, April 1, 2019, before 10am.

Solidify your Course Project Proposal based on my feedback to you (by e-mail):
Look up on Google what information various permutations of your project title may bring forward.
Define some explicit questions that you want to answer in your project,
and explain how you plan to analyze your findings and results.

Also bring six small objects or models that demonstrate these symmetries:
D1=C2; D2; S2; D1d=C2h; C1h=C1v; D1h=C2v.

Have a good Spring Break!