15-344/Classnotes for Thursday September 17: Difference between revisions
| (6 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{15-344/Navigation}} |
{{15-344/Navigation}} |
||
| ⚫ | |||
(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 |
|||
| ⚫ | |||
<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 22:18, 8 October 2015
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
Class notes page 1
Class notes page 2
Class notes page 3
Scanned Tutorial Notes for September 17
Page 1
