15-344/Classnotes for Thursday September 17

DBN: Classes: 2015-16: 15-344 / Navigation 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 [math]\displaystyle{ n }[/math]-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!

Lecture Notes for September 17

DEFINITION 7 Isomorphism A graph [math]\displaystyle{ G_1 = (V_1, E_1) }[/math] is called isomorphic to a graph [math]\displaystyle{ G_2 = (V_2, E_2) }[/math] whenever there exists a bijection [math]\displaystyle{ \phi:V_1 \rightarrow V_2 }[/math] such that [math]\displaystyle{ \forall a,b\in V_1 }[/math] we have [math]\displaystyle{ (ab)\in E_1 }[/math] if and only if [math]\displaystyle{ ( \phi (a) \phi (b))\in E_2 }[/math]. [math]\displaystyle{ G_1\sim G_2 }[/math] means they are isomorphic to each other.

• A bijection is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

• Isomorphism does not mean two things are identical but means they are mathematically the same.

The relationship of isomorphisms:

1. Reflexive: [math]\displaystyle{ G \sim G }[/math] A graph is isomorphic to itself

2. Symmetric: [math]\displaystyle{ G_1 \sim G_2 \implies G_2 \sim G_1 }[/math] In other words, for every [math]\displaystyle{ \phi:V_1 \rightarrow V_2 }[/math] we have [math]\displaystyle{ \phi ^{-1} :V_2 \rightarrow V_1 }[/math]

3. Transitive: [math]\displaystyle{ G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 }[/math]

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 [math]\displaystyle{ G^c = (V,E^c) }[/math]

• Complement means [math]\displaystyle{ (ab)\in E^c \Longleftrightarrow (ab)\notin E }[/math]

DEFINITION 8 Subgraph A subgraph of a graph [math]\displaystyle{ G = (V,E) }[/math] is a graph [math]\displaystyle{ G' = (V',E') }[/math] such that [math]\displaystyle{ V'\subset V }[/math] and [math]\displaystyle{ E'\subset E }[/math].

• Checking if two graphs are isomorphic is a hard problem

Scanned Lecture Note for September 17

• 

  Answers of sample question