Difference between revisions of "15-344/Classnotes for Thursday September 17"

From Drorbn
Jump to: navigation, search
(Scanned Lecture Notes for September 17)
(Scanned Lecture Note for September 17)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{15-344/Navigation}}
 
{{15-344/Navigation}}
 
== Scanned Lecture Notes for September 17 ==
 
 
(Files not beginning with "15-344" were deleted).
 
 
 
 
== Lecture Notes for September 17 ==
 
== 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
 
'''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
Line 13: Line 7:
 
*A ''bijection'' is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection
 
*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 mathematically the same.  
+
*Isomorphism does not mean two things are identical but means they are mathematically the same.  
  
 
The relationship of isomorphisms:
 
The relationship of isomorphisms:
Line 23: Line 17:
  
 
3. '''Transitive:'''  <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </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>
 +
 +
== Scanned Tutorial Notes for September 17 ==
 +
 +
<gallery>
 +
15-344 Tutorial 1.jpg|Page 1
 +
</gallery>

Latest revision as of 23:18, 8 October 2015

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

Scanned Tutorial Notes for September 17