15-344/Classnotes for Tuesday September 15

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

DBN: Classes: 2015-16: 15-344 / Navigation

#	Week of...	Notes and Links
Welcome to Math 344!
Edits to the Math 344 web sites no longer count for the purpose of good deed points.
1	Sep 14	About This Class, Day One Handout, Tuesday, Hour 3 Handout, Thursday, Tutorial 1 Handout
2	Sep 21	Tuesday, Tutorial 2 Page 1, Tutorial 2 Page 2, Thursday, HW1
3	Sep 28	Tuesday, Class Photo, Tutorial 3 Page 1, Tutorial 3 Page 2, Thursday, HW2
4	Oct 5	Tuesday, Drawing $n$ -cubes, Thursday, HW3
5	Oct 12	Tuesday, Tutorial Handout, Thursday, HW4
6	Oct 19	Tuesday, Tutorial Handout, Thursday
7	Oct 26	Term Test on Tuesday, Dijkstra Handout,Thursday,HW5
8	Nov 2	Tuesday, Tutorial Handout, Thursday, HW6, Sunday November 8 is the last day to drop this class
9	Nov 9	Monday-Tuesday is UofT Fall Break, Thursday, HW7
10	Nov 16	Tuesday, Thursday, HW8
11	Nov 23	Tuesday, Thursday, HW9
12	Nov 30	Tuesday, Thursday, HW10
13	Dec 7	Tuesday, FibonacciFormula.pdf, semester ends on Wednesday - no class Thursday
F	Dec 11-22	The Final Exam
Register of Good Deeds
Add your name / see who's in!

We mostly went over Day One Handout today.

Dror's notes above / Students' notes below

Lecture Note for September 15

DEFINITION 1 Graph A graph $G=(V,E)$ is a set $V=\{a,b,...\}$ (usually finite, "vertices") along with a set $E=\{(ab),(bc),(bd),...\}$ ("edges") of unordered pairs of distinct elements of $V$ .

DEFINITION 2 Incident If an edge $e=(ab)\in {E}$ , we say that $e$ is incident to $a$ and $b$ .

DEFINITION 3 N-valent In a graph $G=(V,E)$ , a vertex $u\in {V}$ is called bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where $n=0,1,2,..$ .

DEFINITION 4 Edge Cover An edge cover for graph $G=(V,E)$ is a subset $C\subset {V}$ such that every edge of $G$ incident to at least one vertex in $C$ .

DEFINITION 5 Independent Let $G=(V,E)$ be a graph. A subset $I\subset {V}$ is called independent if whenever $a,b\in {I}$ , then $(ab)\notin {E}$ .

THEOREM 1 Edge covers are complementary to independent sets. In other words, $C\subset {V}$ is an edge cover if and only if the complementary subset $V-C$ is an independent set.

Proof $(\rightarrow )$ Assume $C$ is an edge cover. I assert that $I=V-C$ is independent. Indeed, if $e=(ab)\in {E}$ , then since $C$ is an edge cover, either $a\in {C}\implies a\notin {I}$ or $b\in {C}\implies b\notin {I}$ , which implies $e$ does not connect any two elements of $I$ .

$(\leftarrow )$ Assume $I=V-C$ is independent. Pick any edge $e=(ab)\in {E}$ . As $I$ is independent, $(ab)$ does not connect any two members of $I$ . Hence, either $a\notin {I}\implies a\in {C}$ or $b\notin {I}\implies b\in {C}$ , which implies $e$ is incident to an element of $C$ . QED

DEFINITION 6 Matching is a subset of edges of a graph where no two edges share a common vertex. A matching is said to be perfect if all edges in a graph are matched.