15-344/Classnotes for Thursday September 17

2015-09-19T23:48:54Z

LizElle: /* Scanned Lecture Note for September 17 */

{{15-344/Navigation}}
== Lecture Notes for September 17 ==
'''DEFINITION 7 Isomorphism''' A graph <math>G_1 = (V_1, E_1)</math> is called ''isomorphic'' to a graph <math>G_2 = (V_2, E_2)</math> whenever
there exists a bijection <math>\phi:V_1 \rightarrow V_2</math> such that <math>\forall a,b\in V_1</math> we have <math>(ab)\in E_1</math> if and
only if <math>( \phi (a) \phi (b))\in E_2</math>. <math>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>G \sim G</math> A graph is isomorphic to itself

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

3. '''Transitive:''' <math>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>G^c = (V,E^c)</math>

*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math>

'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and
<math>E'\subset E</math>.

*Checking if two graphs are isomorphic is a hard problem

== Scanned Lecture Note for September 17 ==

<gallery>
Image:15-344_Note_2.jpg|Answers of sample question
Image:15-344-Sept17-1.jpg|Class notes page 1
Image:15-344-Sept17-2.jpg|Class notes page 2
Image:15-344-Sept17-3.jpg|Class notes page 3
</gallery>

File:15-344-Sept17-3.jpg

2015-09-19T23:46:35Z

LizElle:

File:15-344-Sept17-2.jpg

2015-09-19T23:46:04Z

LizElle:

File:15-344-Sept17-1.jpg

2015-09-19T23:44:42Z

LizElle:

15-344/Classnotes for Thursday September 17

2015-09-17T19:36:23Z

LizElle: Created page with "{{15-344/Navigation}} == Scanned Lecture Notes for September 17 == <gallery> Image:Pg001.jpg|Page 1 Image:Pg002.jpg|Page 2 Image:Pg003.jpg|Page 3 </gallery>"

{{15-344/Navigation}}

== Scanned Lecture Notes for September 17 ==

<gallery>
Image:Pg001.jpg|Page 1
Image:Pg002.jpg|Page 2
Image:Pg003.jpg|Page 3
</gallery>

Drorbn - User contributions [en]

15-344/Classnotes for Thursday September 17

File:15-344-Sept17-3.jpg

File:15-344-Sept17-2.jpg

File:15-344-Sept17-1.jpg

15-344/Classnotes for Thursday September 17