Construct a physical model of a surface of genus 2,
and then draw onto this surface TWO closed loops
that together still leave the surface fully connected
(just ONE domain).
Warm-up: A graph-embedding
problem:
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!
Think of a
few things in your domain of interest where a
graph-representation may be useful.
Elements of a graph (G):
a set of Vertices: V(G) = {U, V, W, X, Y, Z ...}.
[these are their names].
a set of Edges: 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), ...).
What would be represented by the
vertices/nodes and by the edges/links ?
A planar graph is one that can be drawn
crossing-free into the plane.
The graph that you tried to construct in the warm-up
exercise 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.
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?
What are
surfaces of higher genus good for?
--
among other things: to embed complex graphs without
any crossings. What are the surfaces of
lowest genus that allow to embed each of the complete
graphs?
Revisiting EC and Genus
Surfaces with Holes and Boundaries -- Review of
some Key Concepts:
If we allow surfaces to have "punctures" or "holes" --
which then have "borders" or "rims"
-- things get a little more complicated.
But a topologist can still classify all the possible surfaces of
that kind by only three characteristics:
ORIENTABILITY: Is the surface two-side (orientable)
or single-sided (non-orientable)?
NUMBER OF BORDERS: How many "disks" have been
removed from a closed surface;
or, how many individual rims or hole
contours are there?
EULER CHARACTERISTIC, EC (or alternatively,
its GENUS, g): How "connected" is the
surface? EC = #Vertices - #Edges +
#Facets of a mesh approximating the surface.
Paper-strip constructions of ever more complex surfaces.
Prepare for an In-Class Quiz on Monday, October 16, 2017.
Next lecture we will have an
in-class quiz. To prepare for this, look through all the course material
and write a condensed fact sheet:
One two-sided, letter-sized sheet of paper, which you may then
use to assist your memory during the quiz.
(I have kept
such sheets for many years after finishing some courses,
and they have come in handy often, when I quickly wanted to
refresh my memory of some of the things I had learned in that
course.)
New Homework Assignments:
Due: October 16, 2017
1.) Prepare
for the In-Class Quiz on Monday,
October 16, 2017:
Review all course materials.
Prepare the one-page, double-sided fact sheet.
2.) Think about your individual course project: Give me two proposals of what you might want to study
concerning: "The role of symmetry and/or topology in the field
of <your special interest>"
Here is a list
of possible titles to jump-start your imagination . .
. Send
your proposals to me by e-mail before 9am on Monday,
October 16, 2017.
