Welcome to Math 344!

Edits to the Math 344 web sites no longer count for the purpose of good deed points.

#

Week of...

Notes and Links

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

MondayTuesday 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 1122

The Final Exam

Register of Good Deeds

Add your name / see who's in!



Lecture Notes for September 17
DEFINITION 7 Isomorphism A graph $G_{1}=(V_{1},E_{1})$ is called isomorphic to a graph $G_{2}=(V_{2},E_{2})$ whenever
there exists a bijection $\phi :V_{1}\rightarrow V_{2}$ such that $\forall a,b\in V_{1}$ we have $(ab)\in E_{1}$ if and
only if $(\phi (a)\phi (b))\in E_{2}$. $G_{1}\sim G_{2}$ means they are isomorphic to each other.
 Isomorphism does not mean two things are identical but means they are mathematically the same.
The relationship of isomorphisms:
1. Reflexive: $G\sim G$ A graph is isomorphic to itself
2. Symmetric: $G_{1}\sim G_{2}\implies G_{2}\sim G_{1}$ In other words, for every $\phi :V_{1}\rightarrow V_{2}$ we have
$\phi ^{1}:V_{2}\rightarrow V_{1}$
3. Transitive: $G_{1}\sim G_{2},G_{2}\sim G_{3}\implies G_{1}\sim G_{3}$
CLAIM If two graphs are isomorphic, then they have:
1. same number of vertices
2. same number of edges
3. vertex degrees (valencies) are the same between the two. For example, if one graph has 3 vertices of degree 2, and 2 vertices of degree 1,
then the other graph should have the same
4. same number of subgraphs
5. same number of complements denoted by $G^{c}=(V,E^{c})$
 Complement means $(ab)\in E^{c}\Longleftrightarrow (ab)\notin E$
DEFINITION 8 Subgraph A subgraph of a graph $G=(V,E)$ is a graph $G'=(V',E')$ such that $V'\subset V$ and
$E'\subset E$.
 Checking if two graphs are isomorphic is a hard problem
Scanned Lecture Note for September 17
Answers of sample question
Scanned Tutorial Notes for September 17