Difference between revisions of "15-344/Classnotes for Thursday September 17"
(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>") |
(→Scanned Lecture Note for September 17) |
||
(8 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{15-344/Navigation}} | {{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. | ||
− | == Scanned Lecture Notes for September 17 == | + | *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> | ||
+ | |||
+ | == Scanned Tutorial Notes for September 17 == | ||
<gallery> | <gallery> | ||
− | + | 15-344 Tutorial 1.jpg|Page 1 | |
− | + | ||
− | + | ||
</gallery> | </gallery> |
Latest revision as of 23:18, 8 October 2015
Lecture Notes for September 17
DEFINITION 7 Isomorphism A graph is called isomorphic to a graph whenever there exists a bijection such that we have if and only if . 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: A graph is isomorphic to itself
2. Symmetric: In other words, for every we have
3. Transitive:
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
- Complement means
DEFINITION 8 Subgraph A subgraph of a graph is a graph such that and .
- Checking if two graphs are isomorphic is a hard problem